Graph manipulation

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.

Manipulating the graph skeleton

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:

Also, the graph layout code is partially implemented by this class.

Planarity issues

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

Invalidation rules

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]

Manipulating node incidence orders

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:

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]

Related topics

Return to main page