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.
static_cast< sparseRepresentation *>(G.Representation()) .
Sparse representational objects admit the following operations:
Also, the graph layout code is partially implemented by this class.
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().
Manipulating the incidence order can be done by two means:
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.
Return to main page