Graph construction

A note on controller objects

Every graph object is assigned to a goblinController object at the time of construction. The controller object supplies with default strategies and values, and with registered callbacks for logging and tracing of methods. A controller object can be specified with default and file constructors, but copy constructors link to the controller object of the original graph.

The examples which follow do not specify controller objects. By that, all constructed objects are assigned to the goblinDefaultContext controller. If you do so also with your application code - and this is adequate if you do not run concurrent jobs - all library configuration must be addressed to the default controller object. For example, goblinDefaultContext.SuppressLogging() would disable the logging event handler.

Construction from existing objects

The first example illustrates how, from a given graph G, its complementary graph H is generated:

    graph H(G.N());
    for (TNode u=0;u<G.N();++u) {
       for (TNode v=u+1;v<G.N();++v) {
          if (G.Adjacency(u,v)==NoArc) H.InsertArc(u,v);

The initial constructor call results in a void graph with an identical node set as G. Then, the procedure iterates on all unordered node pairs u,v and checks if these nodes are adjacent in G. If not, an arc is added to H.

Construction from scratch

The first example illustrates how a triangular graph is generated. The nodes of this graph are the 2-element subsets of an anonymous ground set. Two subsets are adjacent if an ground set element is in common:

    graph G(TNode(0));
    TNode** subset = new TNode*[cardinality];
    for (TNode i=0;i<cardinality;++i) {
       subset[i] = new TNode[cardinality];
       for (TNode j=i+1;j<cardinality;++j) {
          subset[i][j] = G.InsertNode();
          for (TNode k=0  ;k<i;++k) G.InsertArc(subset[i][j],subset[k][j]);
          for (TNode k=i+1;k<j;++k) G.InsertArc(subset[i][j],subset[i][k]);
          for (TNode k=0  ;k<i;++k) G.InsertArc(subset[i][j],subset[k][i]);
    for (TNode i=0;i<cardinality;++i) delete[] subset[i];
    delete[] subset;

Both loops enumerate on the ground set elements which are represented by indices 0, 1, .., cardinality-1. The InsertNode() call returns the index of the added graph node and saves it in a table for convenience. So, the subset[i][j] is an obvious encoding of the subset {i,j}, assuming i<j.

Basically, the sequence of node indices returned by InsertNode() is is 0,1,2,.., and it would be more economic (but less comprehensible) to use a formula in replace of table lookup.

The calls of InsertArc() require indices of already existing nodes, and so the enumeration of arcs still takes some care. Convince yourself that no graph incidence is missed.

This code has been taken from the triangularGraph constructor, to be found in sparseGraph.cpp. This file also defines constructors like openGrid which compute node indices from formula instead of table lookup. The following depicts the special case of constructing a grid graph with quadrangular faces:

    graph G(TNode(numRows*numColumns));
    for (TNode k=0;k<numRows;++k)
       for (TNode l=0;l<numColumns;++l)
          if (l<numColumns-1) InsertArc(k*numColumns + l,  k  *numColumns + (l+1));
          if (k<numRows-1)    InsertArc(k*numColumns + l,(k+1)*numColumns +   l  );

Recursive construction

The next illustrates the recursive build of the incidence structure of a hypercube of arbitrary dimension:

    sparseDiGraph *Hypercube = new sparseDiGraph(TNode(1));
    for (unsigned long i=0;i<dimension;++i) {
       sparseDiGraph *NextCube = new sparseDiGraph(*Hypercube,Hypercube->OPT_CLONE);
       NextCube -> AddGraphByNodes(*Hypercube);
       TNode n0 = Hypercube->N();
       for (TNode j=0;j<n0;++j) {
          NextCube -> InsertArc(j,n0+j);
       delete Hypercube;
       Hypercube = NextCube;

The procedure starts with a one-node digraph, that is the hypercube of dimension zero. To obtain the (d+1)-hypercube from the (d)-hypercube, the digraph copy constructor is used. The OPT_CLONE specifier herein demands that the new sparseDiGraph instance has an identical incidence structure (otherwise arcs with zero upper capacity bounds are not mapped, and the order of arc indices changes).

The AddGraphByNodes() call generates a second, node-disjoint copy of the (d)-hypercube. This has node indices n0, n0+1, .., 2n0-1 in the compound graph. Both (d)-hypercube subgraphs are then connected by explicit InsertArc() method calls which take the end node indices as parameters.

Similar, compilable code is provided by the file testHypercube.cpp.

Derived constructor methods

The following illustrates the recursive build of the incidence structure of a binary tree. Other than in the previous example, a new class is introduced, with only a constructor method:

    class binaryTree : public sparseDiGraph
        binaryTree(TNode depth,goblinController& _CT = goblinDefaultContext);
    binaryTree::binaryTree(TNode depth,goblinController &_CT) :
       managedObject(_CT), sparseDiGraph(TNode(1))
       if (depth==0) return;
       binaryTree TR(depth-1,_CT);
          -> SetCapacity(2*TR.N()+1,2*TR.N()+2);

The managedObject initializer assigns new instances to a goblinController object. The sparseDiGraph initializer lets the constructor start from a singleton node graph. This node serves as the root node. If the specified tree depth is zero, nothing more has to be done. Otherwise, the depth (d+1) binary tree is obtained from two disjoint copies of a depth (d) binary tree, calling abstractMixedGraph::AddGraphByNodes() twice. To obtain the (d) binary tree, the displayed constructor method is called recursively.

The sparseRepresentation::SetCapacity() call is not esssential. But it prevents from reallocations, every time, a node or arc is added. It is directly addressed to the representational object, like most of the methods which manipulate graph instances.

In a final step, the root node of the depth (d+1) binary tree is connected to the root nodes of the depth (d) binary trees by calling InsertArc() with the respective node indices.

Similar, compilable code is provided by the file testBinTree.cpp.

Construction from file

The high-level interface method to load graph objects from file is applied like this:

    managedObject* X =
    if (X && X->IsGraphObject())
       abstractMixedGraph *G = dynamic_cast<abstractMixedGraph*>(X);

This code can load from any file format supported by the library, and construct objects of any target types, as required for the selected formatName. The obvious overhead is that the precise object type must be reconstructed later.

When the input file format is known in advance, the cast operations can be avoided by using a more low-level method:

    sparseDiGraph* G = goblinDefaultContext.Import_DimacsEdge(filename);
    if (G)

or, for the library native formats, like this:

    sparseDiGraph* G = NULL;
    try {
       G = new sparseDiGraph(filename);
    catch (ERParse) {
    catch (ERFile)  {

Note that the first two methods return a NULL pointer in every case of trouble. The third method might throw two different exceptions, for non-existing files and for syntax violations.

Similar, compilable code is provided by the file testPlanarity.cpp.