1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/graphs.dox Fri May 28 07:48:16 2004 +0000
1.3 @@ -0,0 +1,145 @@
1.4 +/*!
1.5 +
1.6 +\page graphs How to use graphs
1.7 +
1.8 +The following program demonstrates the basic features of HugoLib's graph
1.9 +structures.
1.10 +
1.11 +\code
1.12 +#include <iostream>
1.13 +#include <hugo/list_graph.h>
1.14 +
1.15 +using namespace hugo;
1.16 +
1.17 +int main()
1.18 +{
1.19 + typedef ListGraph Graph;
1.20 +\endcode
1.21 +
1.22 +ListGraph is one of HugoLib's graph classes. It is based on linked lists,
1.23 +therefore iterating throuh its edges and nodes is fast.
1.24 +
1.25 +\code
1.26 + typedef Graph::Edge Edge;
1.27 + typedef Graph::InEdgeIt InEdgeIt;
1.28 + typedef Graph::OutEdgeIt OutEdgeIt;
1.29 + typedef Graph::EdgeIt EdgeIt;
1.30 + typedef Graph::Node Node;
1.31 + typedef Graph::NodeIt NodeIt;
1.32 +
1.33 + Graph g;
1.34 +
1.35 + for (int i = 0; i < 3; i++)
1.36 + g.addNode();
1.37 +
1.38 + for (NodeIt i(g); g.valid(i); g.next(i))
1.39 + for (NodeIt j(g); g.valid(j); g.next(j))
1.40 + if (i != j) g.addEdge(i, j);
1.41 +\endcode
1.42 +
1.43 +After some convenience typedefs we create a graph and add three nodes to it.
1.44 +Then we add edges to it to form a full graph.
1.45 +
1.46 +\code
1.47 + std::cout << "Nodes:";
1.48 + for (NodeIt i(g); g.valid(i); g.next(i))
1.49 + std::cout << " " << g.id(i);
1.50 + std::cout << std::endl;
1.51 +\endcode
1.52 +
1.53 +Here we iterate through all nodes of the graph. We use a constructor of the
1.54 +node iterator to initialize it to the first node. The next member function is
1.55 +used to step to the next node, and valid is used to check if we have passed the
1.56 +last one.
1.57 +
1.58 +\code
1.59 + std::cout << "Nodes:";
1.60 + NodeIt n;
1.61 + for (g.first(n); n != INVALID; g.next(n))
1.62 + std::cout << " " << g.id(n);
1.63 + std::cout << std::endl;
1.64 +\endcode
1.65 +
1.66 +Here you can see an alternative way to iterate through all nodes. Here we use a
1.67 +member function of the graph to initialize the node iterator to the first node
1.68 +of the graph. Using next on the iterator pointing to the last node invalidates
1.69 +the iterator i.e. sets its value to INVALID. Checking for this value is
1.70 +equivalent to using the valid member function.
1.71 +
1.72 +Both of the previous code fragments print out the same:
1.73 +
1.74 +\code
1.75 +Nodes: 2 1 0
1.76 +\endcode
1.77 +
1.78 +\code
1.79 + std::cout << "Edges:";
1.80 + for (EdgeIt i(g); g.valid(i); g.next(i))
1.81 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
1.82 + std::cout << std::endl;
1.83 +\endcode
1.84 +
1.85 +\code
1.86 +Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
1.87 +\endcode
1.88 +
1.89 +We can also iterate through all edges of the graph very similarly. The head and
1.90 +tail member functions can be used to access the endpoints of an edge.
1.91 +
1.92 +\code
1.93 + NodeIt first_node(g);
1.94 +
1.95 + std::cout << "Out-edges of node " << g.id(first_node) << ":";
1.96 + for (OutEdgeIt i(g, first_node); g.valid(i); g.next(i))
1.97 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
1.98 + std::cout << std::endl;
1.99 +
1.100 + std::cout << "In-edges of node " << g.id(first_node) << ":";
1.101 + for (InEdgeIt i(g, first_node); g.valid(i); g.next(i))
1.102 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
1.103 + std::cout << std::endl;
1.104 +\endcode
1.105 +
1.106 +\code
1.107 +Out-edges of node 2: (2,0) (2,1)
1.108 +In-edges of node 2: (0,2) (1,2)
1.109 +\endcode
1.110 +
1.111 +We can also iterate through the in and out-edges of a node. In the above
1.112 +example we print out the in and out-edges of the first node of the graph.
1.113 +
1.114 +\code
1.115 + Graph::EdgeMap<int> m(g);
1.116 +
1.117 + for (EdgeIt e(g); g.valid(e); g.next(e))
1.118 + m.set(e, 10 - g.id(e));
1.119 +
1.120 + std::cout << "Id Edge Value" << std::endl;
1.121 + for (EdgeIt e(g); g.valid(e); g.next(e))
1.122 + std::cout << g.id(e) << " (" << g.id(g.tail(e)) << "," << g.id(g.head(e))
1.123 + << ") " << m[e] << std::endl;
1.124 +\endcode
1.125 +
1.126 +\code
1.127 +Id Edge Value
1.128 +4 (0,2) 6
1.129 +2 (1,2) 8
1.130 +5 (0,1) 5
1.131 +0 (2,1) 10
1.132 +3 (1,0) 7
1.133 +1 (2,0) 9
1.134 +\endcode
1.135 +
1.136 +In generic graph optimization programming graphs are not containers rather
1.137 +incidence structures which are iterable in many ways. HugoLib introduces
1.138 +concepts that allow us to attach containers to graphs. These containers are
1.139 +called maps.
1.140 +
1.141 +In the example above we create an EdgeMap which assigns an int value to all
1.142 +edges of the graph. We use the set member function of the map to write values
1.143 +into the map and the operator[] to retrieve them.
1.144 +
1.145 +Here we used the maps provided by the ListGraph class, but you can also write
1.146 +your own maps. You can read more about using maps \ref maps "here".
1.147 +
1.148 +*/