The graph skeleton denotes all information defining the incidence structure of a graph:
- Start and end nodes of a given arc
- A node incidence list for every node
- Information which edges are directed
There is a universal interface to retrieve information about the skeleton. That is, dense graphs also have a logical view of incidence lists, but no according memory representation. Only the skeleton of graphs with a sparse representation can be manipulated.
Basically, edges are represented by indices in an interval [0,1,..,m-1]. Technically however, every edge (say with index i) has two directions (2i and 2i+1), and most methods expect edge parameters including the arc direction bit. This is independent of whether the whole graph is directed, undirected or mixed.
Observe that Orientation(2i) and Orientation(2i+1) are the same, and this tells whether the edge i is directed. In that case, Blocking(2i) returns false but Blocking(2i+1) returns true. The latter method is used to generalize optimization methods from directed to mixed graphs (e.g. for minimum spanning arborescence or max-cut). It is not applied by shortest path methods which occasionally operate on implicitly modified digraphs (residual networks).
From the logical viewpoint, all graph objects - not just those with a sparse representation - own an incidence structure to be investigated by algorithms:
- StartNode(i) and EndNode(i) give the two nodes which are connected by the arc i with the identity StartNode(i)==EndNode(i^1).
- First(v) gives either NoArc or an arc index such that StartNode(First(v))==v.
- Right() can be used to enumerate all incidences of a particular node, including the blocking backward arcs. One has StartNode(Right(i))==StartNode(i).
For dense graphs, all these method internally calculate node indices from arc indices or vice versa. Sparse graphs have incidence lists represented in memory.
Node incidence lists cannot only be searched by directly calling First() and Right(). There are proxy objects, called investigators, maintaining an incidence list pointer (i.e. an arc index) for every graph node.
In some situations, it is necessary to decide whether two given nodes are adjacent (that is, if the nodes are joined by an edge) or even to know a connecting arc. By default, there is no data structure for this purpose. For dense graphs, a call to Adjacency() calculates the connecting arc only by using the given node indices. In its general implementation, the method uses a hash table which is build on the first call. Observe that this hash table is invalidated by any maipulation of the graph skeleton.
Return to main page