Graph skeleton

The graph skeleton denotes all information defining the incidence structure of a graph:

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.

Arc orientations

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).

[See API]

Node and arc incidences

From the logical viewpoint, all graph objects - not just those with a sparse representation - own an incidence structure to be investigated by algorithms:

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.

[See API]

Node adjacencies

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.

[See API]

Related topics

Return to main page