11.5 GRAPH

Purpose:

Two graph representations are available: DIRECT_GRAPH for directed graphs, and SINGLE_GRAPH for undirected graphs. A graph consists of a set of nodes connected by edges. All nodes are of one type, all edges of another type.

Both graphs preserve the direction of edges. However, the difference between the two organizations is that, for the SINGLE_GRAPH, you can traverse the graph in either direction, while for the DIRECT_GRAPH you can proceed only in the direction of the edges.

For example, for a given edge, SINGLE_GRAPH gives you access to both adjacent nodes, while DIRECT_GRAPH gives you only the target node. Or when traversing edges adjacent to a given node, for SINGLE_GRAPH, the iterator returns edges both starting and ending at the given node, while the DIRECT_GRAPH iterator returns only the nodes starting at the given node.

DIRECT_GRAPH is less expensive in memory; nodes have the same size, but the edge uses only half as many pointers as for SINGLE_GRAPH.

In both models the edge rings are singly linked, and therefore the DELETE operation is slow in topologies with many edges per node. If you have to deal with situations where edges are deleted frequently, add a doubly-linked version of the graph to the library.

Order of objects:

Edges on a node are currently treated as an unordered collection. However, the order of nodes for each edge is maintained, and determines the direction of the edge. This applies for both directed and undirected graphs. The first of the two nodes is always the from node, the second is the to node.

Adding edges and nodes:

When you want to add a new edge to the graph, you have to provide two nodes and the edge. If your application uses the direction of the edge, then np[0] must be the from node, and np[1] must be the to node:

Node *np[2]; Edge *ep;
...
np[0]= ... ; // 'from' node|
np[1]= ... ; // 'to' node
ep=new Edge;
myGraph.add(np,ep);

Deleting edges and nodes:

del() deletes a given edge from the graph. If you want to disconnect a node, you have to traverse all its edges, and delete them. This is not easily done for a DIRECT_GRAPH. If you want to perform such operations, use a SINGLE_GRAPH, and monitor the direction of the edges.

Getting from an edge to adjacent nodes:

For a given edge function nodes(twoNodes,edge) returns two adjacent nodes. When calling this function, you give it an array of two pointers; it sets the pointers to the two adjacent nodes. The direction of the edge is preserved (always from np[0] to np[1]).

ZZ_HYPER_SINGLE_GRAPH(myGraph,Node,Edge);
Node *np[2]; Edge *ep;
... /* edge is given */
myGraph.nodes(np,ep); /* returns np */

For a directed graph, the use of nodes() is exactly the same, except that the function fills in only the target node (np[1]). In a directed graph, you cannot reach the source node from the edge.

Moving around the GRAPH:

The iterator traverses the edges adjacent to a given node and, through the function adj(), provides the adjacent node for each edge. The adjacent node could be found through the function nodes(), but when operating in a loop, adj() is much faster.

id_iterator it(node);
while(edge= ++it){
    adjNode=it.adj();
    ...
};

Edges can be deleted while being traversed. For a directed graph, this command traverses all the edges starting at a given node.

For non-directed graph (SINGLE_GRAPH), the iterator traverses all adjacent edges. If you want to move through the graph in one particular direction, use function nodes() which tells you, for each edge, what is the direction of the edge.

There is no arrangement for easy access to all the edges or all the nodes of the graph. Use a separate RING if you have to visit all the nodes or edges.

Syntax:

Node *n0, *n1; Edge *e;
id_iterator it(n0); // start from n0
while(e= ++it){ // traverse adjacent edges
    n1=it.adj(); // adjacent node
    ...
 }

Node *n0, *n1; Edge *e;
id_iterator it(n0); // start from n0
while(e= ++it){ // traverse adjacent edges
    n1=it.adj(); // adjacent node
    ...
 }

Examples:

1. Two superimposed graphs of highways and airline routes connecting a set of towns (test14a.c).
2. Simple test which creates a small tree, using DIRECT_GRAPH, and then it deletes a subtree is in test49a.c.
3. The same problem as in test49a.c but coded with SINGLE_GRAPH is shown in test49b.c. Note the changes required to the code, because the interators traverse both edges that come to a vertex or leave it.

Previous Section 11.4 TREE

Next Section 11.6 LINK and NAME