class Place::Router::Digraph(N, E)

Overview

Labelled digraph. Holds node labels of type N and edge labels of type E.

Nodes are stored on UInt64 ID's. This provides an interface that should feel similar to Indexable for interacting with nodes labels. Similarly edges can be placed and retrieved by using a dual index of {predescessor, successor}.

OPTIMIZE replace with a sparse matrix and graphBLAS operations.

Defined in:

place/router/digraph.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(initial_capacity = nil) #

[View source]

Instance Method Detail

def [](pred_id, succ_id) #

Retrieves the label attached to the edge that joins pred_id and succ_id.


[View source]
def [](id) #

Retrieves the label attached to node id.


[View source]
def []=(pred_id, succ_id, attr) #

Inserts an edge.


[View source]
def []=(id, attr) #

Insert a new node.


[View source]
def breadth_first_search(from, & : UInt64 -> Bool | Nil) #

Perform a breadth first search across the graph, starting at from.

Each node id is yielded as it's traversed. The search will terminate when this block returns true. If nil is returned the node is skipped, but the traversal continues.

Results are provided as a Hash that includes all reached nodes as the keys, and their predecessor as the associated value.


[View source]
def clear(*args, **options) #

[View source]
def clear(*args, **options, &) #

[View source]
def fetch(pred_id, succ_id, &) : E #

Retrieves the label attached to the edge that joins pred_id and succ_id.


[View source]
def fetch(id, &) : N #

Retrieves the label attached to node id. Yields if it does not exist.


[View source]
def indegree(id) #

The number of incomming edges to id.


[View source]
def insert(pred_id, succ_id, attr : E, &) #

Inserts an edge.


[View source]
def insert(id, attr : N, &) #

Inserts a node. Yields if it already exists.


[View source]
def nodes : Enumerable(UInt64) #

Provides all nodes present within the graph.

NOTE ordering of nodes is not defined.


[View source]
def outdegree(id) #

The outgoing edges from id.


[View source]
def path(from, to, invert = false) : Enumerable(UInt64) | Nil #

Returns a list of node IDs that form the shortest path between the passed nodes or nil if no path exists.


[View source]
def sink?(id) : Bool #

Checks if a node has incoming edges only.


[View source]
def sinks : Enumerable(UInt64) #

Provides all nodes with incoming edges only.


[View source]
def source?(id) : Bool #

Checks if a node has outgoing edges only.


[View source]
def sources : Enumerable(UInt64) #

Provides all nodes with outgoing edges only.

OPTIMIZE this is very slow [O(V * E)], but works for testing purposes. Switching the sparse matrix should assist so not worth optimising for this setup.


[View source]
def subtree(id) : Enumerable(UInt64) #

Provides all nodes reachable from id.


[View source]