Implementing Graph Algorithms

• Implementing Graph Algorithms
  • Overview
  • The class GT_Algorithm
    • Methods which must be provided by the derived class
    • Optional methods which may be overridden by the derived class
  • Utilities provided by the class GT_Algorithm
  • A complete Example
    • Header
    • Constructor and Destructor
    • Reset
    • Check
    • Run

Overview

The class GT_Algorithm provides a base class and a standard interface for the implementation of graph algorithms. The key idea here is that each algorithm is a class, and is invoked with the run method. Noth parameters and results are stored as class member variables, instead of parameters and/or function results as usual.

The major advantage of this approach is that all of Graphlet's interfaces provide special support for algorithms which are implemented with this class. Especially, the Tcl interface for algorithms is designed to take an algorithm that has been implemented with GT_Algorithm, and then construct a Tcl interface for it. Since algorithms already have a standardized interface, all the programmer has to supply is code for parsing parameters and error handling.

Another advantage of our approach is that algorithms may be parts of data structures. That is, a class may contain one or more algorithms, for example to customize the building of the data structure. As another example, test suites may use lists of arrays of algorithms.

The class GT_Algorithm

All algorithms in Graphlet are derived from the class GT_Algorithm. The following example shows a minimal algorithm class implemented with GT_Algorithm:

class Sample : public GT_Algorithm {
    public:
    Sample (const string& name);
    virtual ~Sample ();
    virtual int run (GT_Graph& g);
    virtual int check (GT_Graph& g, string& message);
}

Methods which must be provided by the derived class

Sample (const string& name)

This is the constructor of the class Sample. name is usually the name of the Tcl command that is associated with the algorithm. GT_Algorithm's constructor should be defined as follows:

Sample::Sample(const string& name) : GT_Algorithm (name) {
    // Initialize the algorithm's parameters here
}
    

virtual ~ Sample()

The class Sample must contain a virtual destructor since GT_Algorithm already has virtual functions.

virtual int run (GT_Graph& g)

The method run executes the algorithm. Its parameter is the input graph. This procedure must return GT_OK if the command could be completed successfully, and GT_ERROR otherwise. If GT_ERROR is returned, then the Tcl interface raises an exception.
Warning: It is a common mistake to implement run without returning a value. This will result in unpredictable Tcl runtime errors.

virtual int check(GT_Graph& g, string& message)

The method check should be called before run to make sure that the current graph g is valid input for the algorithm. This method should return GT_OK if the graph is valid, and GT_ERROR otherwise. The parameter message should contain a detailed error message if the check fails. Additional error information may be returned in member variables.
Warning: GT_Algorithm does not automatically call check before run. In contrast to that, the Tcl interface for GT_Algorithm enforces this.

Optional methods which may be overridden by the derived class

virtual void reset ()

The method reset reinitializes the member variables of the algorithm. Typically, reset puts the member variables back to the same state as after the constructor.
Warning: Like check, reset is never called automatically. However, the Tcl interface has a configurable option to to do this each time the command is executed.

reset is neccessary because of the following:

GT_Sample_Algorithm a;

// a has three parameters:
// parameter1, default value false 
// parameter2, default value 0
// parameter3, default value ""

// First run: parameter1, parameter2 changed, parameter3 default.
a.parameter1 (true);
a.parameter2 (42);
a.run ();

// Second run: parameter2, parameter1 changed,
// but parameter1 does not have the default value.

a.parameter2 (21);
a.parameter3 ("xyz");
a.run ();

reset is primarily utilized by the Tcl interface. The idea is that there is one Tcl command for each algorithm, with a single C++ object of the corresponding class behind it. If the algorithm is executed several times with varying parameter sets, then it is neccessary to reset the parameters inbetween these executions.

Utilities provided by the class GT_Algorithm

static edge find_self_loop (GT_Graph& g)

find_self_loop searches for a self look in g. It returns 0 if no self loop is found.

static bool remove_all_bends (GT_Graph& g)

remove_all_bends removes all bends in the edges of g. It returns true if bends are found, and false otherwise.
Warning: A user interface should not use this method directly, but should ask the user first.

void adjust_coordinates (GT_Graph& g, double min_x = 0, double min_y = 0)

adjust_coordinates moves the graph so that the minimum coordinates are at (min_x,min_y).

A complete Example

Header

The following C++ header header shows how to implement an algorithm that constructs a matching:

class GT_Matching_Algorithm : public GT_Algorithm {

    typedef GT_Algorithm baseclass;

    // Input: edge weights
    edge_map<double>* the_edge_weights;

    // The result is stored in this variable.
    list<edge> the_matching;

    // Information on errors.
    int the_error_code;
    list<edge> the_self_loops;
    list<edge> the_multiple_edges;
    list<list<node> > the_components;

public:

    // Constructor and Destructor
    GT_Matching_Algorithm (const string& name);
    virtual ~GT_Matching_Algorithm ();

    // Standard methods
    virtual void reset ();
    virtual int run (GT_Graph&amp; g);
    virtual int check (GT_Graph&amp; g, string& message);

    // Accessors
    void edge_weights(const edge_map<double>&) const;
    inline const edge_map<double>& edge_weights() const;

    inlint int error_code() const;
    inline const list<edge>& matching() const;
    inline const list<edge>& self_loops() const;
    inline const list<edge>& multiple_edges() const;
    inline const list<list<node> >& components() const;

    enum {
        no_error,
        error_self_loops,
        error_multiple_edges,
        error_not_connected;
    };
};

The following conventions are used in the above interface:

• Options, for example edge weights, are implemented as member variables.
• The result of the algorithm is stored in a variable the_matching.
• If an error is detected in check (in this case, self loops, multiple edges, or the graph is not connected), then the offending object is stored in the_self_loops, the_multiple_edges and/or the_components.

Constructor and Destructor

The following code implements the constructor for the matching algorithm. There are no edge weights yet; this variable can only be initialized when a graph is kown (e.g. in run, or by explicitely setting this variable from edge_weights).

GT_Matching_Algorithm::GT_Matching_Algorithm (
    const string& name) :
        GT_Algorithm (name)
{
    the_edge_weights = 0;
    the_error_code = no_error; // (yet)

    // All other member variables have default constructors 
}

The desructor is usually quite simple; since most of the clean-up is accomplished in the destructors of the individual members, we only need to free data that has been dynamically allocated.

GT_Matching_Algorithm::~GT_Matching_Algorithm ()
{
    if (the_edge_weights != 0) {
        delete the_edge_weights;
    }
}

If the algorithm had added user defined attributes to the graph, then reset might also need to remove some of these.

Reset

The method reset is optional and resets all options and member variables. Note that since the_edge_weights os a pointer, we must deallocate it.

void GT_Matching_Algorithm::reset ()
{
    if (the_edge_weights != 0) {
        delete the_edge_weights;
    }
    the_edge_weights = 0;

    the_error_code = no_error;

    the_self_loops.clear();
    the_multiple_edges.clear();
    the_components.clear();
}

Check

The method check tests wether the graph is connected, searches for self loops and multiple edges, and also checks wether the edge weights are used consistently, e.g. there are no edge weights, or edge weights for all edges. If it finds an error, it deposits it in the appropriate member variable, sets message to a description of the error and returns GT_ERROR.

int GT_Matching_Algorithm::check (GT_Graph& g, string& message)
{
    if (find_multiple_edges (g, the_self_loops)) {
        message = "The graph contains self a loop";
        the_error_code = error_self_loops;
        return GT_ERROR;
    }

    if (find_multiple_edges (g, the_multiple_edges)) {
        message = "The graph contains multiple edges";
        the_error_code = error_multiple_edges;
        return GT_ERROR;
    }

    if (components (g, the_components) > 1) {
        message = "The graph is not connected";
        the_error_code = error_not_connected;
        return GT_ERROR;
    }

    message = "";
    the_error_code = no_error;
    return GT_OK;
}

Run

The method run is implemented in a straightforward way. Depending on the option the_edge_weights, we either call a matching option with or without edge weights (the latter being easier). The method always returns GT_OK, since there will always be a matching.

int GT_Matching_Algorithm::run (GT_Graph& g)
{
    const graph& gtl = g.gtl();

    the_matching.clear(); // Make sure to remove last time's edges
    if (the_edge_weights != 0) {
        weightless_matching (g, the_matching);
    } else {
        weighted_matching (g, the_edge_weight, the_matching);
    }

    return GT_OK;
}

<- Attributes | Up | Tcl Interface ->