Using AGD

In the following, we present a complete example of extending the library by a new layout algorithm. Moreover, the main() routine is an easy example of an application. The algorithm added to the library simply assigns random coordinates to the vertices for brevity.

#include<AGD/LayoutModuleImpl.h>
#include<AGD/ConstLedaGraphConcept.h>
#include<AGD/GraphWinInterface.h>

class RandomLayout : public LayoutModuleImpl<ConstLedaGraphConcept>  
{
  public:
    RandomLayout();
    string name() const { return string("Random"); }
    string long_name() const { return string("Random Layout"); }
    string author() const { return string("NA"); }
    string impl_author() const { return string("David Alberts"); }
    string impl_date() const { return string("May 1997"); }
    AGDModule *clone() const { return new RandomLayout; }
  protected:
    void do_call(ConstLedaGraphConcept& C);
  private:
    random_source rs;
};

RandomLayout::RandomLayout()
{ add_post_rule (key::straight_line); }

void RandomLayout::do_call(ConstLedaGraphConcept &C)
{
  const graph &G = C.get_graph();
  LayoutInterface &A = C.get_layout();

  a.make_straight_line();  // remove all bend points

  node v;
  forall_nodes(v,G)
  {
    double x,y;
    rs >> x >> y;   // assigns pseudo-random numbers in the range [0..1]
    x *= 500.0;     // scale to [0..500]
    y *= 500.0;
    A.set_position(v,DPoint(x,y));
  }
}

int main()
{
  GraphWin GW;               // create a GraphWin                           (1)
  GW.open();                 // open it, and let user edit a graph          (2)
  graph& G = GW.get_graph(); // get the graph                               (3)
  GraphWinInterface GWI(GW); // create an interface to GW for AGD alg's     (4)
  RandomLayout RL;           // create an instance RL of RandomLayout       (5)
  RL.call(G,GWI);            // apply RL to G displaying it in GW           (6)
  GW.edit();                 // let the user edit the result                (7)
}

A new class RandomLayout is created representing the new algorithm. It is derived from the base class LayoutModuleImpl<ConstLedaGraphConcept>. The template argument ConstLedaGraphConcept defines the implementation concept used by RandomLayout. In this case, the algorithm works on a const LEDA graph, i.e., the implementation method do_call() does not alter its input graph. There are also implementation concepts which allow to manipulate the input graph by creating temporarily a copy (see Chapter Chapter Implementation of Layout Algorithms). Apart from the constructor, all methods in the class RandomLayout are refinements of virtual methods provided by its base class.

The constructor declares the precondition (none in this case) and postcondition (all edges are straight lines) of the algorithm. The refined public methods provide information about the particular algorithm and implementation. The protected method do_call() implements the drawing procedure. It is called by the inherited public method call() (see main()).

We describe the main() function in more detail: In line (1) we create an instance GW of class GraphWin as visualization component. Line (2) displays GW on the screen and lets the user edit a graph. In line (3) we get a reference to the graph which has been created. We create a layout interface to GW in line (4). We create an instance of the RandomLayout algorithm in line (5) and use it on G displaying the result again in GW in line (6). Finally, we let the user edit the resulting graph in line (7). The graph together with the computed coordinates can be saved to disk, for example.

Before calling an algorithm it is possible to check whether a certain input graph satisfies the precondition of the algorithm that should be applied using the check() method. In our example this is not necessary, since there are no restrictions on the input.