doc/graphs.dox
changeset 666 410a1419e86b
child 756 c54cf1e83039
equal deleted inserted replaced
-1:000000000000 0:1344de31ab0b
       
     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 */