The General Graph Class:

We now introduce a useful example that puts to use all of the material on object oriented design that we have discussed so far. We will build a general graph class in this chapter that was sketched out by Joh Lakos in his book on large scale software design (Lakos,  19). We will go through this class carefully here and then modify it to allow for graphical display in the X Window system in Chapter  4 and introduce a graphical interface tool based on this extension in Chapter  5. Finally, since we eventually wish to use these tools to allow very general types of computational objects to be organized in a graph structure of our choosing, we then extend the basic graph model to allow for the use of typeless data (implemented as the typdef Arbent void * in Chater  6. The typeless data graph model is an extension of ideas discussed in Wang's text on Object Oriented Programming (Wang,  31) and is another useful example of proper encapsulation techniques.

The graph class we implement here is built using an idea called levelization. If you think about it, graphs are inherently circular in nature: for example, how can you define nodes without referring to edges? To attempt to decouple these ideas, we design the graph class to separate the node and edge ideas as much as possible. We will use the following classes in our implementation:

class Edge:

We use the Edge class as a parent class.

class Node:

We use the Node class as a parent class.

class Gedge:

We derive the class Gedge from Edge.

class Gnode:

We derive the class Gnode from Node.

class Graph:

The Graph class consists of Gedge and Gnode objects. We all know that the nodes in a graph are connected to each other with edges. We need to collect the information about how the nodes and edges are connected into suitable structures, we need objects to manipulate those structures and we need ways to alter the contents of those structures. We will do this in the following way:

• All the pointers to the Gnodes in the graph will collected into what is called a bag. You can think of this as just a set of Gnode pointers.
• All the pointers to the Gedges in the graph will be collected into another bag.
• These Pointer Bags will be organized as singly linked lists, but we will not use the full power of a list class; instead we will code the minimal functionality we need right here. We use the following scheme:
  • Each bag is a singly linked list of cells (look back at our previous volumes on abstract data structures) which consist of a pointer to an Gedge or Gnode respectively and a pointer to the next cell. In our implementation here, the cells are the class objects GedgePtrBagLink or GnodePtrBagLink which have the standard cell structure consisting of say

                       Gnode *d_pointer_p;
                       GnodePtrBagLink *d_next_p;
    

    or

                      Gedge *d_pointer_p;
                      GedgePtrBagLink *d_next_p;
    

  • We move around these singly linked lists with iterators: here they are the classes GedgePtrBagIter and GnodePtrBagIter respectively. Now these classes allow us to move around, but not to change the contents of the bags of Gedge and Gnode pointers.
  • We need to alter the pointer bags when we want to delete or add and edge or node. The addition of an edge or node is very easy; we simply add the new edge or node to the appropriate bag. However, deletion is harder. Think about it this way: a given node has its pointer stored somewhere in that singly linked list of pointers. So if we remove that pointer, we are really deleting a cell from a list. This requires a while loop to search through the list to find the element. Let ADDR represent the address of the memory location which stores the address of the head cell of the bag pointer; hence *ADDR is the address of the head cell. If we want to alter the list, we need to pass in ADDR to our remove method: consider such a generic remove:

    void remove(GnodePtrBagLink **ADDR,GnodePtrBagLink *Key)
    {
      GnodePtrBagLink *tmp = Key;   //this is the cell pointer we want to delete
      Key = Key->next();            //reset to the next cell
      
      //reset Bag
      GnodePtrBagLink *Now = *ADDR; //set Now to head cell
      GnodePtrBagLink *Prev;
      
      if(tmp==Now){
        //If the Key is at the head of the list, then
        //by resetting *ADDR to the next cell, we 
        //effectively remove the head cell.
        *ADDR = (*ADDR)->next();
        
        //Once the reset is done, we can delete Now
        delete Now;
        }
      else{
        //In this case, the Key is not at the head, so we
        //have to search through the list to find the cell
        //whose next pointer is the Key.
        Prev = Now;
        Now = Now->next();
        
        //If the Key was the Now from above, the following while
        //loop would be skipped.
        //
        //If the Key was not the Now above, we enter the while
        //loop to find the cell whose next point is the Key.          
        while( !(Now==tmp) ){
          Prev = Now;
          Now = Now->next();    
          } 
         
        //In either case, we arrive here with the cell information 
        //we need.  We reset the Prev cell's next pointer to be 
        //the next pointer for Now (so we jump over the Key cell)
        //and then we can delete Now.  
        Prev->d_next_p = Now->next(); 
        delete Now;      
        }
    }
    

    The classes GedgePtrBagmanip and GnodePtrBagmanip respectively will be implemented to allow us to do such removes. We will use code like the remove() code above in both the classes to implement the GedgePtrBagmanip::remove() and GnodePtrBagmanip::remove() method:
• The Graph class thus works like this: we add Gedge and Gnode objects as we wish. Each time we do so we add to the appropriate bag of pointers object GedgePtrBag or GnodePtrBag. Movement in the Graph object is done with GedgePtrBagIter or GnodePtrBagIter objects. While altering the Graph object is handled by making changes to the pointer bag objects via the manipulator objects GedgePtrBagManip or GnodePtrBagManip.

Let's look at these definition files in a skeleton form:

class Edge:

The Edge class is the part of the Edge objects that has nothing to do with Graph objects. Hence, it is factored out and placed in its own class. The Gedge object will derive from Edge and will include dependencies on Graph objects.

class Edge{
    //overloaded I/O
    friend istream& operator>>(istream& in, Edge& A);
    friend istream& operator>>(istream& in, Edge* A);
    friend ostream& operator<<(ostream& out,const Edge& A);
    friend ostream& operator<<(ostream& out,const Edge* A);
  private:
    double d_weight;
  public:
    Edge();
    Edge(double weight);
    Edge(const Edge&);
    ~Edge();
    Edge& operator=(const Edge&);
    double weight() const;
    istream& grab(istream& in); 
    ostream& print(ostream& out) const;
  };

Note that by using overloaded I/O, we can use code like

cout << Edge;

to print out the contents of an Edge object.

class Node:

In a similar fashion, the portions of the node objects that are not graph object dependent are factored out and put in the Node class. Note both this class and the Edge class can be tested independently of the Graph objects.

class Node{
    // Overloaded I/O
    friend istream& operator>>(istream& in, Node& A);
    friend istream& operator>>(istream& in, Node* A);
    friend ostream& operator<<(ostream& out,const Node& A);
    friend ostream& operator<<(ostream& out,const Node* A);
  private:
    char *d_name_p;
    
  public:
    Node();
    Node(const char *name);
    Node(const Node&);
    ~Node();
    Node& operator=(const Node&);
    const char *name() const;
    istream& grab(istream& in); 
    ostream& print(ostream& out) const;
  };

class Gedge:

Now we add functionality to the basic Edge object using class derivation. This class must be connected to the Graph and Gnode objects. Note that the Gedge class allows the Graph class to be a friend so that the Graph class has access to its private constructors and destructors. Note this implies something important: the only way to construct a Gedge object is either by instantiating a Gedge object directly or by constructing Gedge objects through the Graph object. Note the copy constructor and overloaded equal are not implemented but are listed in the class definition. This will prevent the compiler from generating default versions of these methods.

class Gedge : public Edge{
    friend Graph;
  private:
    Gnode *d_from_p;
    Gnode *d_to_p;
    Gedge(const Gedge&);                  //not implemented
    Gedge& operator=(const Gedge&);       //not implemented
    Gedge(Gnode *from,Gnode *to,double weight);
    ~Gedge();
  public:
    Gnode *from();
    Gnode *to();
  };

class Gnode:

Most of the comments about the Gedge class are relevant here also. Note that there is a new public method called edges() which allows us to access the bag of pointers which stores the edges associated with a given Gnode object.

class Gnode : public Node{
    friend Graph;
  private:
    GedgePtrBag d_edges;
    Gnode(const Gnode&);                   //not implemented
    Gnode& operator=(const Gnode&);        //not implemented
    Gnode(const char *name);
    ~Gnode();
    void add(Gedge *edgeptr);
    void remove(Gedge *edgeptr);
  public:
    const GedgePtrBag& edges() const;
  };

class Graph:

Now we can finally see the full Graph class structure. A graph consists of bags of node and edge pointers and a variety of methods allowing us to use the Graph object.

class Graph{
    //Overloaded I/O
    friend istream& operator>>(istream& in, Graph& A);
    friend istream& operator>>(istream& in, Graph* A);
    friend ostream& operator<<(ostream& out,const Graph& A);
    friend ostream& operator<<(ostream& out,const Graph* A);
  private:
    GnodePtrBag d_nodes;
    GedgePtrBag d_edges;
    Graph(const Graph&);
    Graph& operator=(const Graph&);
  public:
    Graph();
    ~Graph();
    Gnode *addNode(const char *nodeName);
    Gnode *findNode(const char *nodeName);
    void removeNode(Gnode *node);
    Gedge *addEdge(Gnode *from,Gnode *to,double weight);
    Gedge *findEdge(Gnode *from,Gnode *to);
    void removeEdge(Gedge *edge);
    const GnodePtrBag& nodes() const;
    const GedgePtrBag& edges() const;
    istream& grab(istream& in); 
    ostream& print(ostream& out) const;
  };

The Edge or Node Bag Pointer Classes:

Since these classes are so similar, we will restrict our comments to the Edge object versions. There are several classes to talk about here: GedgePtrBagLink (the cells of the singly linked list we use to implement the bag of pointers), GedgePtrBag (the actuall singly linked list structure of bag pointers), GedgePtrBagIter (the usual iterator class) and GedgePtrBagManip (the class allowing us to manipulate the bag of pointers). We begin with the GedgePtrBagLink class:

class GedgePtrBagLink:

Note this class must declare the manipulator and iterator classes as friends to allow them appropriate access. The definitions are of a fairly standard singly linked list cell design.

class GedgePtrBagLink{
    friend GedgePtrBagIter;
    friend GedgePtrBagManip;
  private:
    Gedge *d_pointer_p;
    GedgePtrBagLink *d_next_p;
    GedgePtrBagLink(const GedgePtrBagLink&);
    GedgePtrBagLink& operator=(const GedgePtrBagLink&);
    int operator==(const GedgePtrBagLink&);    
  public:
    GedgePtrBagLink(Gedge *pointer,GedgePtrBagLink *next);
    ~GedgePtrBagLink();
    GedgePtrBagLink *next() const;
    Gedge *pointer() const;
  };

class GedgePtrBag:

This class is essentially a singly linked list of the cells defined above that has very limited functionality compared to a full singly linked list implementation as discussed in previous volumes. The removeAll() method is a little different. The bag of edge pointers may contain a given edge pointer many times as we can add edges as often as we like even if an edge between nodes is already established. So we must move throught the bag of edge pointers and remove a given edge every time we find it. This requires the manipulator class.

class GedgePtrBag{
    friend GedgePtrBagIter;
    friend GedgePtrBagManip;
  private:
    GedgePtrBagLink *d_root_p;
    GedgePtrBag(const GedgePtrBag&);
    GedgePtrBag& operator=(const GedgePtrBag&);
  public:
    GedgePtrBag();
    ~GedgePtrBag();
    void add(Gedge *pointer);
    void removeAll(const Gedge *pointer);
  };

class GedgePtrBagIter:

This class implements a standard singly linked list iterator design.

class GedgePtrBagIter{
    friend GedgePtrBagLink;
  private:
    GedgePtrBagLink *d_link_p;
    GedgePtrBagIter(const GedgePtrBagIter& T);
    GedgePtrBagIter& operator=(const GedgePtrBagIter&);
  public:
    GedgePtrBagIter(const GedgePtrBag& bag) : d_link_p(bag.d_root_p){};
    ~GedgePtrBagIter(){};
    void operator++();
    Gedge *operator()() const;
    operator const void *() const;
  };

class GedgePtrBagmanip:

The last class in this group is for the manipulator class object. We will use **d_addrLink_p to store the address of memory location whose value is the address of the head cell in the edge bag pointer container. Hence, *d_addrLink_p will be the address of the head cell. The variable edgePtrBagLink *L is a local variable which enables us to move through the bag and is needed to do the manipulator implementation correctly. The following code for the advance() method is completely wrong although seemingly plausible because it does not use edgePtrBagLink *L:

void GedgePtrBagManip::advance()
{
  *d_addrLink_p = (*d_addrLink_p)->next();
}

This code fails because *d_addrLink_p starts as the head cell address. Hence, a call to advance() will replace the head cell with the next cell. Also, this creates a possible memory leak as the replaced cell is never correctly deleted. The effect of this code fragment is that as we move through the bag calling the advance method to do so, we lose all the cells in the bag!! The correct way to do this is to use the local variable edgePtrBagLink *L to march through the bag:

void GedgePtrBagManip::advance()
{
  L = L->next();
}

class GedgePtrBagManip{
  private:
    GedgePtrBagLink **d_addrLink_p;
    GedgePtrBagLink *L;
    GedgePtrBagManip(const GedgePtrBagManip&);
    GedgePtrBagManip& operator=(const GedgePtrBagManip&);
  public:
    GedgePtrBagManip(GedgePtrBag* bag);
    ~GedgePtrBagManip();
    void advance();
    void remove();
    Gedge *operator()() const;
    operator const void *() const;
  };