Changes between Version 1 and Version 2 of TrianglesAlgorithm


Ignore:
Timestamp:
04/26/10 00:24:44 (9 years ago)
Author:
jberry
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • TrianglesAlgorithm

    v1 v2  
    1 Hi 
     1Algorithms 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. 
     2 
     3We will consider the example of finding triangles. There is MTGL code to do this: [source: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 [source:trunk/tutorial/triangles1.cpp]. 
     4 
     5To compile the latter in the mtgl/tutorial directory: 
     6{{{ 
     7  c++ -I.. -o triangles1 triangles1.cpp 
     8}}}  
     9 
     10To run the program: 
     11{{{ 
     12./triangles1 < graphs/two_triangles.graph 
     13Graph (g): 
     14(0, 1) 
     15(1, 2) 
     16(2, 0) 
     17(2, 3) 
     18(3, 4) 
     19(4, 2) 
     20 
     21Graph (dg): 
     22(0, 1) 
     23(1, 2) 
     24(2, 3) 
     25(2, 0) 
     26(3, 4) 
     27(4, 2) 
     28 
     290 : { {0}(0, 1) } 
     301 : { {1}(1, 2) } 
     312 : { {2}(2, 0) {3}(2, 3) } 
     323 : { {4}(3, 4) } 
     334 : { {5}(4, 2) } 
     34triangle eids: {5,4,3} 
     35triangle eids: {0,1,2} 
     36triangle: {(4,2), (3,4), (2,3)} 
     37triangle: {(0,1), (1,2), (2,0)} 
     38max b: 2 
     39max d: 2 
     40num tri: 2 
     410 : { {0}(0, 1) } 
     421 : { {1}(1, 2) } 
     432 : { {3}(2, 3) {2}(2, 0) } 
     443 : { {4}(3, 4) } 
     454 : { {5}(4, 2) } 
     46triangle eids: {5,4,3} 
     47triangle eids: {0,1,2} 
     48triangle: {(4,2), (3,4), (2,3)} 
     49triangle: {(0,1), (1,2), (2,0)} 
     50max b: 2 
     51max d: 2 
     52num tri: 2 
     53}}} 
     54 
     55= Triangle Visitor = 
     56 
     57Upon finding a triangles, 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.  
     58{{{ 
     59template <class graph> 
     60class triangle_printing_visitor { 
     61public: 
     62  typedef typename graph_traits<graph>::size_type size_type; 
     63  typedef typename graph_traits<graph>::vertex_descriptor vertex_descriptor; 
     64  typedef typename graph_traits<graph>::edge_descriptor edge_descriptor; 
     65  typedef typename graph_traits<graph>::edge_iterator edge_iterator; 
     66 
     67  triangle_printing_visitor(graph& gg) : g(gg), edgs(edges(g)), 
     68                                         vid_map(get(_vertex_id_map, g)) {} 
     69 
     70  void operator()(size_type eid1, size_type eid2, size_type eid3) { 
     71       edge_descriptor e1 = edgs[eid1]; 
     72       edge_descriptor e2 = edgs[eid2]; 
     73       edge_descriptor e3 = edgs[eid3]; 
     74       printf("triangle eids: {%lu,%lu,%lu}\n", eid1, eid2, eid3); 
     75       vertex_descriptor e1src = source(e1, g); 
     76       vertex_descriptor e1trg = target(e1, g); 
     77       vertex_descriptor e2src = source(e2, g); 
     78       vertex_descriptor e2trg = target(e2, g); 
     79       vertex_descriptor e3src = source(e3, g); 
     80       vertex_descriptor e3trg = target(e3, g); 
     81       size_type e1srcid = get(vid_map, e1src); 
     82       size_type e1trgid = get(vid_map, e1trg); 
     83       size_type e2srcid = get(vid_map, e2src); 
     84       size_type e2trgid = get(vid_map, e2trg); 
     85       size_type e3srcid = get(vid_map, e3src); 
     86       size_type e3trgid = get(vid_map, e3trg); 
     87       printf("triangle: {(%lu,%lu), (%lu,%lu), (%lu,%lu)}\n", 
     88          e1srcid, e1trgid, e2srcid, e2trgid, e3srcid, e3trgid); 
     89  } 
     90private: 
     91  graph& g; 
     92  edge_iterator edgs; 
     93  vertex_id_map<graph> vid_map; 
     94}; 
     95}}}