class DIGRAPH{NTP} < $DIGRAPH{NTP},$SUPPORTS_REHASH |
---|
**** | This is a directed graph which permits arbitrary nodes of type NTP. This is the default graph implementation. NTP is the node type i.e the unique node index The actual nodes of the graph may be supplied by the user of this class, during the add_node. The digraph is implemented by two hash mappings from nodes to parents and nodes to outgoing. There is also a separate list of nodes. |
$SUPPORTS_REHASH | $DIGRAPH{_} | $RO_DIGRAPH{_} | $GRAPH{_,_} |
$STR | $ELT{_} | $ELT | DIGRAPH_INCL{_} |
RO_DIGRAPH_INCL{_} | COMPARE{_} |
LBLD_DIGRAPH{_,_,_} | WTD_DIGRAPH{_,_} |
add_node(n: NTP) |
---|
**** | Short hand for "add_node(n:NTP): NTP" that is only valid for this sort of graph, where the user specifies the node type. |
add_node(n: NTP): NTP |
---|
**** | Add the node "n". In this kind of hash digraph, the node index returned is guaranteed to be the same as the node "n". Note that this is not generally true for graphs |
add_node: NTP |
---|
**** | Add a new node and return the index |
connect(e: DIEDGE{NTP}) |
---|
**** | Connect source to target. No change if the edge already exists Add the nodes if they do not exist |
create(node_gen: $SUCC_STREAM{NTP}): SAME |
---|
**** | Create a new digraph. Store "node_gen" as a generator of nodes, so that when "add_node: NTP" is called it can generate unique new nodes. |
create: SAME |
---|
**** | Create a new digraph and return it. Since a node generator is not specified, it will not be possible to call the "add_node:NTP" function, since the graph will not know how to create new unique nodes. All the data structures can be initialized with void |
delete_node(n: NTP) |
---|
**** | Delete a node from the graph, and all its accompanying edges |
disconnect(e: DIEDGE{NTP}) |
---|
**** | Deletes the edge "e". |
has_edge(e: DIEDGE{NTP}): BOOL |
---|
has_node(n: NTP): BOOL |
---|
is_identical(g: SAME): BOOL |
---|
**** | Check whether the two graphs have the same nodes, edges in the same order |
is_topo_order(n: $ARR{NTP}):BOOL |
---|
**** | Return true if the nodes in "n" do not violate the precedence relations expressed by the graph "self" |
n_edges: INT |
---|
**** | Returns the number of edges in the graph, making sure each edge is only counted once |
n_incoming(n: NTP): INT |
---|
**** | Number of incoming edges from node "n" |
n_neighbors(n: NTP): INT |
---|
**** | Returns the number of neighbors of "n" (nodes are only counted once) |
n_nodes: INT |
---|
n_outgoing(n: NTP): INT |
---|
**** | Number of outgoing edges from node "n" |
rehash |
---|
bf!(once n: NTP): NTP |
---|
**** | Yield all nodes in breadth first order |
df!(once n: NTP): NTP |
---|
**** | Yield all nodes in depth first order |
edge!: DIEDGE{NTP} |
---|
**** | Return all edges in the graph |
incoming!(once n: NTP): NTP |
---|
layer!: SET{NTP} |
---|
**** | Peel off successive layers from the graph, starting with the root set. Stop when no more roots (nodes with no incoming edges) can be found. |
node!: NTP |
---|
outgoing!(once n: NTP): NTP |
---|
sink!: NTP |
---|
**** | Yield all the sink nodes (with n_outgoing = 0) in self |
source!: NTP |
---|
**** | Yield all the source nodes with n_incoming = 0 in self |
topo_order!: NTP |
---|
**** | Yield the nodes of self in some topologically sorted orer |
check_node(n: NTP,routine_name: STR): BOOL |
---|
attr incoming_map: FMULTIMAP{NTP,NTP}; |
---|
attr incoming_map: FMULTIMAP{NTP,NTP}; |
---|
attr node_generator: $SUCC_STREAM{NTP}; |
---|
**** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
attr node_generator: $SUCC_STREAM{NTP}; |
---|
**** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
attr node_list: FLIST{NTP}; |
---|
**** | List of nodes in the graph |
attr node_list: FLIST{NTP}; |
---|
**** | List of nodes in the graph |
attr outgoing_map: FMULTIMAP{NTP,NTP}; |
---|
**** | Keep both around since it is quite expensive to derive one from the other. |
attr outgoing_map: FMULTIMAP{NTP,NTP}; |
---|
**** | Keep both around since it is quite expensive to derive one from the other. |