The C++ Graph Classes: A Tutorial - Graph(C++) and Graph_alg(C++)

Using the Graph Classes to Create Objects

To start, we'll need in our example to create objects from the Graph classes that will model the widget, the widget modules, and module relations. From the definitions in the last section, we see that a Graph will model the widget, Vertices will model the widget modules, and Edges will model module relations. For each (source, destination) module pair, the Edge will contain the time necessary for the destination module to receive the previously-manufactured source module.

The Graph classes define a generic version of each class; if no user data is needed then the classes can be used as provided. Figure 2 shows a generic representation of the Vertices and Edges from Figure 1.

A Generic Version of Figure 1

For instance, if the widget module needed no additional data, then we could use the Vertex class to directly create widget modules:

       Vertex w0; //a widget module w0

A limitation to this approach that may be immediately obvious is that we have no way (other than the Vertex and Edge addresses) to identify any part of the Graph. If we were to iterate over the Vertices, we could only use the Vertex address to know where we were at any given point.

For most applications, therefore, it will be desirable to attach user data to any or all of the Graph class objects. However, an all-or-none decision must be made when user data is required for any of the Graph classes. User versions of each of the Graph classes must be created, even if user data is not required for the remaining classes. This implementation decision allows the Graph package to be much less complex than it otherwise would be. Thus, if the modules in Figure 1 are to include an identifier such as ``A'', ``B'', etc., which is quite useful if iteration over the modules ever takes place, this forces the use of not only a user-derived class from Vertex, but user-derived classes from Graph and Edge as well.

Here's how we would create the widget module necessary for Figure 1. We'll use the name Product for the user-derived Graph type representing the widget, Module for the user-derived Vertex type representing the widget module, and Transport_Time for the user-derived Edge type that represents the widget ``directed'' relation.

Note that Module is derived from the Graph class Vertex:

   class Module: public Vertex {
       String id;
       Module(const String& s) : Vertex(), id(s) {}
       /* macro invocation */

We use an id of type String and have created a constructor for our Module that initializes it. (If we had no need to initialize data, we would not have needed to create a Module constructor: see the section, ``Vertex Constructors and Destructors''.) We also invoke a derivedVertex macro that takes three arguments: the user versions of the Graph classes in the order user Graph, user Vertex, and user Edge. This macro creates the necessary declarations to support the user types within the package. As with all macro invocations, care must be taken not to insert spaces in the macro calls.

Creating the user Graph and Edge types, Product and Transport_Time, work much the same way. Note that in the case of the Graph derived type, we do not have user data that needs to be included. To create a Product, we need to define a constructor (see the section ``Graph Constructors and Destructors''): in this case, a parameterless one will do. The derived Edge class, Transport_Time, must define a constructor that includes the two Modules that are being related through the Transport_Time. (See the section, ``Edge Constructors and Destructors''.) Note that it initializes a data member through the constructor as did the constructor for Module. ttime will represent the transport time needed between Modules:

   class Product: public Graph {
       Product() : Graph() {}
   class Transport_Time: public Edge {
       int ttime;
       Transport_Time(Module* m1, Module* m2, int time):
           Edge(m1,m2), ttime(time) {}

(It's useful to note that since Transport_Time is representing a directed Edge, the order of m1 and m2 is significant in the Transport_Time constructor. If Transport_Time would represent an Edge in an undirected Graph, then, for the same m1 and m2, the constructor

   Transport_Time(Module* m2, Module* m1, int time):
       Edge(m2,m1), ttime(time) {}

would have precisely the same meaning.)

We use macros to simulate parameterized types. The Graphdeclare1 and Graphdeclare2 macros are needed to generate the appropriate declarations for our Graph:

       #include <Graph.h>
       class Product {...};
       class Module {...};
       class Transport_Time {...};

which completes the declare process necessary for the package. We would then typically place the above declaration bundle in a ``h'' file.

Next topic: Creating, Inserting, Removing, and Destroying the User Graph Types
Previous topic: Example: Manufacturing Process of a Widget

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005