A graph object can be manipulated only if it is represented, and manipulation methods are addressed to its representational object. Register atttributes are not attached to representational objects, but are available for every graph object. That is, register attribute value can be set and modified for logical graph instances also.
Both sparse and dense representations allow changes of the representational attributes (capacity bounds, arc lengths, node demands) but the skeleton can be manipulated only for sparsely represented graphs.
A pointer to the representational object is returned by the method abstractMixedGraph::Representation() which is defined for every graph object, but returns a NULL pointer for non-represented graph objects.
In order to manipulate the skeleton of a sparse graph G, the representational object of G must be dereferenced and type-casted like this:
static_cast< sparseRepresentation *>(G.Representation()) .
Sparse representational objects admit the following operations:
- Arc insertions and deletions
- Node insertions and deletions
- Reversion of the (implicit) arc orientations
- Swap the indices of a pair of nodes or of a pair of arcs
- Arc contraction to a single node
- Identification of a pair of nodes
Also, the graph layout code is partially implemented by this class.
In principle, these operations maintain planar representations. For the arc insertions and the node identification operations, this can only work if the two (end) nodes are on a common face, practically the exterior face. If the common face exist, but is not the exterior face, abstractMixedGraph::MarkExteriorFace() must be called to make it temporarily exterior (This sets the First() indices after that new arcs are inserted into the incidence list).
The following operations invalidate existing node and arc indices:
That is, after the call DeleteArc(a), arc indices might address different data before and after the arc deletion. This does not only concern the specified index a. The method DeleteNode() causes even more trouble, since node deletions imply the deletion of all incident arcs.
It is possible to delay these index invalidation effects by using the method sparseRepresentation::CancelArc() instead of DeleteArc(a). Doing so, the edge is deleted from its end nodes incidence lists (so that subsequent graph search won't traverse it), but all arc attributes remain unchanged. After the process of arc deletions has been completed, a call of DeleteArcs() will pack all attributes.
The CancelNode() and DeleteNodes() methods work pretty similar as CancelArc() and DeleteArc(). But observe that programming sparseRepresentation::CancelNode(v) implies a CancelArc() call for every arc incident with v, and that DeleteNode(v) and DeleteNodes() imply a call of DeleteArcs().
[See API]
A node incidence list enumerates all arcs with a given start node. The lists are defined by the method abstractMixedGraph::Right() and are essentially circular. But there is a special list entry abstractMixedGraph::First() to break the circular list at.
Manipulating the incidence order can be done by two means:
- Calling sparseRepresentation::SetRight(): This cuts a circular list in three pieces and relinks the pieces such that a single circular list is maintained. This is a tricky operation if several concurrent calls are necessary, since the relative order of the arcs passed to SetRight() is restricted.
- Calling sparseRepresentation::ReorderIncidences() takes an array of arc indices which specifies for every arc index a1 in [0,1,..,2m-1] another arc index which is set as the return value of Right(a1). So the procedure assigns all right-hand arc indices simultaneously. It is not so difficult to handle, but efficient only if the incidence orders can be assigned in one pass.
Observe that in a planar representation, the incidence lists of exterior nodes (node on the exterior face) start with two exterior arcs (there might be more than two candidates if the node is a cut node). So in the planar case, rather than setting the First() indices directly, it is recommended to call abstractMixedGraph::MarkExteriorFace() which adjusts the planar representation consistently such that the left-hand region of the passed arc becomes the exterior face.
[See API]
Return to main page