class UGRAPH{NTP} < $UGRAPH{NTP} |
---|
**** | For now, call this UGRAPH since we have no other graph implementations. A basic undirected graph implemented with a hash table from nodes to neighbors. This implementation mainly specifies the access routines. |
$UGRAPH{_} | $RO_UGRAPH{_} | $GRAPH{_,_} | $STR |
$ELT{_} | $ELT | UGRAPH_INCL{_} | COMPARE{_} |
add_node(n: NTP) |
---|
**** | Add a node "n".
_ Technical detail: Since the node index for "n" is the same as the node for this particular implementation, there is no need to return a value. Note that this function is not in the graph abstraction |
add_node(n: NTP):NTP |
---|
**** | Replaces an existing node that is the same as "n" This function is guaranteed to return the same node, "n" though this is not true of graph implementations in general |
add_node: NTP |
---|
**** | Add a new node and return the index |
connect(n1,n2: NTP) |
---|
**** | Connect n1 and n2. Add the nodes if they do not exist |
copy: SAME |
---|
create(node_gen: $SUCC_STREAM{NTP}): SAME |
---|
**** | Create a new ugraph. Store "node_gen" as a generator of nodes, so that when "add_node: NTP" is called it can generate unique new nodes. |
create: SAME |
---|
**** | 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(n1,n2: NTP) |
---|
**** | Deletes the edge between n1 and n2 if it exists |
is_identical(g: SAME): BOOL |
---|
**** | Check whether the two graphs have the same nodes, edges in the same order |
n_adjacent(n: NTP): INT |
---|
n_nodes: INT |
---|
new_edge(n1,n2: NTP): UEDGE{NTP} |
---|
permute_nodes(new_positions: $MAP{NTP,INT}) |
---|
**** | Permute the nodes of the graph so that they will be yielded in the order expressed by "new_positions" |
sort |
---|
**** | Reduce the graph to a canonical form based on the sorting order of nodes and edges |
test_edge(s,t: NTP): BOOL |
---|
test_node(n: NTP): BOOL |
---|
adjacent!(once n: NTP): NTP |
---|
edge!: UEDGE{NTP} |
---|
**** | Return all edges in the graph. A problem, since we represent edges in both directions. We might want to either maintain a hash table of edges already seen or generate a matching or something of the sort. Or can use some arbitrary test to choose one or the other. such as lt For now, use a set which holds all nodes for which all edges have been yielded edges yielded |
node!: NTP |
---|
add_neighbor(n1,n2: NTP) |
---|
check_node(n: NTP,routine_name: STR): BOOL |
---|
neighbor_list(n1:NTP):FLIST{NTP} |
---|
attr neighbor_map: FMAP{NTP,FLIST{NTP}}; |
---|
**** | holds mappings from each node to all it's neighbors |
attr neighbor_map: FMAP{NTP,FLIST{NTP}}; |
---|
**** | holds mappings from each node to all it's neighbors |
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}; |
---|
attr node_list: FLIST{NTP}; |
---|