wiki:TrianglesAlgorithm

Algorithms in the MTGL typically accept a callback function or "visitor" from the user. This visitor will be called upon the occurrence of certain events, and the user will have an opportunity to react. It is common practice to include auxiliary data in the visitor object and update those data when events occur.

We will consider the example of finding triangles. There is MTGL code to do this: trunk/mtgl/triangles.hpp. This file contains the functor (algorithm object) "find_triangles" (along with some deprecated versions of triangles finding algorithms). Our example usage of find_triangles is found in the file trunk/tutorial/triangles1.cpp.

To compile the latter in the mtgl/tutorial directory:

  c++ -I.. -o triangles1 triangles1.cpp

To run the program:

./triangles1 < graphs/two_triangles.graph
Graph (g):
(0, 1)
(1, 2)
(2, 0)
(2, 3)
(3, 4)
(4, 2)

Graph (dg):
(0, 1)
(1, 2)
(2, 3)
(2, 0)
(3, 4)
(4, 2)

0 : { {0}(0, 1) }
1 : { {1}(1, 2) }
2 : { {2}(2, 0) {3}(2, 3) }
3 : { {4}(3, 4) }
4 : { {5}(4, 2) }
triangle eids: {5,4,3}
triangle eids: {0,1,2}
triangle: {(4,2), (3,4), (2,3)}
triangle: {(0,1), (1,2), (2,0)}
max b: 2
max d: 2
num tri: 2
0 : { {0}(0, 1) }
1 : { {1}(1, 2) }
2 : { {3}(2, 3) {2}(2, 0) }
3 : { {4}(3, 4) }
4 : { {5}(4, 2) }
triangle eids: {5,4,3}
triangle eids: {0,1,2}
triangle: {(4,2), (3,4), (2,3)}
triangle: {(0,1), (1,2), (2,0)}
max b: 2
max d: 2
num tri: 2

Triangle Visitor

Upon finding a triangle, the algorithm will extract the three edge id's for the edges in the triangle and pass them to a user-defined function. That function is the operator() method in a visitor object such as the one defined below. It is up to the user to determine what data (if any) to store in this object. The only requirement of the triangle algorithm API is that the operator() must take three edge id's as arguments. The example below simply extracts the id's of the endpoints of the triangle edges and prints them.

template <class graph>
class triangle_printing_visitor {
public:
  typedef typename graph_traits<graph>::size_type size_type;
  typedef typename graph_traits<graph>::vertex_descriptor vertex_descriptor;
  typedef typename graph_traits<graph>::edge_descriptor edge_descriptor;
  typedef typename graph_traits<graph>::edge_iterator edge_iterator;

  triangle_printing_visitor(graph& gg) : g(gg), edgs(edges(g)),
                                         vid_map(get(_vertex_id_map, g)) {}

  void operator()(size_type eid1, size_type eid2, size_type eid3) {
       edge_descriptor e1 = edgs[eid1];
       edge_descriptor e2 = edgs[eid2];
       edge_descriptor e3 = edgs[eid3];
       printf("triangle eids: {%lu,%lu,%lu}\n", eid1, eid2, eid3);
       vertex_descriptor e1src = source(e1, g);
       vertex_descriptor e1trg = target(e1, g);
       vertex_descriptor e2src = source(e2, g);
       vertex_descriptor e2trg = target(e2, g);
       vertex_descriptor e3src = source(e3, g);
       vertex_descriptor e3trg = target(e3, g);
       size_type e1srcid = get(vid_map, e1src);
       size_type e1trgid = get(vid_map, e1trg);
       size_type e2srcid = get(vid_map, e2src);
       size_type e2trgid = get(vid_map, e2trg);
       size_type e3srcid = get(vid_map, e3src);
       size_type e3trgid = get(vid_map, e3trg);
       printf("triangle: {(%lu,%lu), (%lu,%lu), (%lu,%lu)}\n",
          e1srcid, e1trgid, e2srcid, e2trgid, e3srcid, e3trgid);
  }
private:
  graph& g;
  edge_iterator edgs;
  vertex_id_map<graph> vid_map;
};

Once this visitor has been written, the triangle algorithm object can be instantiated and run as follows:

  triangle_printing_visitor<Graph> tpv(g);
  find_triangles<Graph, triangle_printing_visitor<Graph> > ft(g,tpv);
  ft.run();

Many of the MTGL algorithms work in this way, but we don't go into further detail since the algorithm API's are not yet settled.