doc/graphs.dox
author alpar
Tue, 20 Jul 2004 09:52:03 +0000
changeset 712 6f1abe741fb6
child 756 c54cf1e83039
permissions -rw-r--r--
src/becnhmark gets in the distro.
I hope it works well.
     1 /*!
     2 
     3 \page graphs How to use graphs
     4 
     5 The following program demonstrates the basic features of HugoLib's graph
     6 structures.
     7 
     8 \code
     9 #include <iostream>
    10 #include <hugo/list_graph.h>
    11 
    12 using namespace hugo;
    13 
    14 int main()
    15 {
    16   typedef ListGraph Graph;
    17 \endcode
    18 
    19 ListGraph is one of HugoLib's graph classes. It is based on linked lists,
    20 therefore iterating throuh its edges and nodes is fast.
    21 
    22 \code
    23   typedef Graph::Edge Edge;
    24   typedef Graph::InEdgeIt InEdgeIt;
    25   typedef Graph::OutEdgeIt OutEdgeIt;
    26   typedef Graph::EdgeIt EdgeIt;
    27   typedef Graph::Node Node;
    28   typedef Graph::NodeIt NodeIt;
    29 
    30   Graph g;
    31   
    32   for (int i = 0; i < 3; i++)
    33     g.addNode();
    34   
    35   for (NodeIt i(g); g.valid(i); g.next(i))
    36     for (NodeIt j(g); g.valid(j); g.next(j))
    37       if (i != j) g.addEdge(i, j);
    38 \endcode
    39 
    40 After some convenience typedefs we create a graph and add three nodes to it.
    41 Then we add edges to it to form a full graph.
    42 
    43 \code
    44   std::cout << "Nodes:";
    45   for (NodeIt i(g); g.valid(i); g.next(i))
    46     std::cout << " " << g.id(i);
    47   std::cout << std::endl;
    48 \endcode
    49 
    50 Here we iterate through all nodes of the graph. We use a constructor of the
    51 node iterator to initialize it to the first node. The next member function is
    52 used to step to the next node, and valid is used to check if we have passed the
    53 last one.
    54 
    55 \code
    56   std::cout << "Nodes:";
    57   NodeIt n;
    58   for (g.first(n); n != INVALID; g.next(n))
    59     std::cout << " " << g.id(n);
    60   std::cout << std::endl;
    61 \endcode
    62 
    63 Here you can see an alternative way to iterate through all nodes. Here we use a
    64 member function of the graph to initialize the node iterator to the first node
    65 of the graph. Using next on the iterator pointing to the last node invalidates
    66 the iterator i.e. sets its value to INVALID. Checking for this value is
    67 equivalent to using the valid member function.
    68 
    69 Both of the previous code fragments print out the same:
    70 
    71 \code
    72 Nodes: 2 1 0
    73 \endcode
    74 
    75 \code
    76   std::cout << "Edges:";
    77   for (EdgeIt i(g); g.valid(i); g.next(i))
    78     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
    79   std::cout << std::endl;
    80 \endcode
    81 
    82 \code
    83 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
    84 \endcode
    85 
    86 We can also iterate through all edges of the graph very similarly. The head and
    87 tail member functions can be used to access the endpoints of an edge.
    88 
    89 \code
    90   NodeIt first_node(g);
    91 
    92   std::cout << "Out-edges of node " << g.id(first_node) << ":";
    93   for (OutEdgeIt i(g, first_node); g.valid(i); g.next(i))
    94     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; 
    95   std::cout << std::endl;
    96 
    97   std::cout << "In-edges of node " << g.id(first_node) << ":";
    98   for (InEdgeIt i(g, first_node); g.valid(i); g.next(i))
    99     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; 
   100   std::cout << std::endl;
   101 \endcode
   102 
   103 \code
   104 Out-edges of node 2: (2,0) (2,1)
   105 In-edges of node 2: (0,2) (1,2)
   106 \endcode
   107 
   108 We can also iterate through the in and out-edges of a node. In the above
   109 example we print out the in and out-edges of the first node of the graph.
   110 
   111 \code
   112   Graph::EdgeMap<int> m(g);
   113 
   114   for (EdgeIt e(g); g.valid(e); g.next(e))
   115     m.set(e, 10 - g.id(e));
   116   
   117   std::cout << "Id Edge  Value" << std::endl;
   118   for (EdgeIt e(g); g.valid(e); g.next(e))
   119     std::cout << g.id(e) << "  (" << g.id(g.tail(e)) << "," << g.id(g.head(e))
   120       << ") " << m[e] << std::endl;
   121 \endcode
   122 
   123 \code
   124 Id Edge  Value
   125 4  (0,2) 6
   126 2  (1,2) 8
   127 5  (0,1) 5
   128 0  (2,1) 10
   129 3  (1,0) 7
   130 1  (2,0) 9
   131 \endcode
   132 
   133 In generic graph optimization programming graphs are not containers rather
   134 incidence structures which are iterable in many ways. HugoLib introduces
   135 concepts that allow us to attach containers to graphs. These containers are
   136 called maps.
   137 
   138 In the example above we create an EdgeMap which assigns an int value to all
   139 edges of the graph. We use the set member function of the map to write values
   140 into the map and the operator[] to retrieve them.
   141 
   142 Here we used the maps provided by the ListGraph class, but you can also write
   143 your own maps. You can read more about using maps \ref maps "here".
   144 
   145 */