1.1 --- a/doc/Doxyfile Thu May 27 10:04:55 2004 +0000
1.2 +++ b/doc/Doxyfile Fri May 28 07:48:16 2004 +0000
1.3 @@ -392,6 +392,7 @@
1.4 # with spaces.
1.5
1.6 INPUT = mainpage.dox \
1.7 + graphs.dox \
1.8 maps.dox coding_style.dox \
1.9 groups.dox \
1.10 ../src/hugo \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/doc/graphs.dox Fri May 28 07:48:16 2004 +0000
2.3 @@ -0,0 +1,145 @@
2.4 +/*!
2.5 +
2.6 +\page graphs How to use graphs
2.7 +
2.8 +The following program demonstrates the basic features of HugoLib's graph
2.9 +structures.
2.10 +
2.11 +\code
2.12 +#include <iostream>
2.13 +#include <hugo/list_graph.h>
2.14 +
2.15 +using namespace hugo;
2.16 +
2.17 +int main()
2.18 +{
2.19 + typedef ListGraph Graph;
2.20 +\endcode
2.21 +
2.22 +ListGraph is one of HugoLib's graph classes. It is based on linked lists,
2.23 +therefore iterating throuh its edges and nodes is fast.
2.24 +
2.25 +\code
2.26 + typedef Graph::Edge Edge;
2.27 + typedef Graph::InEdgeIt InEdgeIt;
2.28 + typedef Graph::OutEdgeIt OutEdgeIt;
2.29 + typedef Graph::EdgeIt EdgeIt;
2.30 + typedef Graph::Node Node;
2.31 + typedef Graph::NodeIt NodeIt;
2.32 +
2.33 + Graph g;
2.34 +
2.35 + for (int i = 0; i < 3; i++)
2.36 + g.addNode();
2.37 +
2.38 + for (NodeIt i(g); g.valid(i); g.next(i))
2.39 + for (NodeIt j(g); g.valid(j); g.next(j))
2.40 + if (i != j) g.addEdge(i, j);
2.41 +\endcode
2.42 +
2.43 +After some convenience typedefs we create a graph and add three nodes to it.
2.44 +Then we add edges to it to form a full graph.
2.45 +
2.46 +\code
2.47 + std::cout << "Nodes:";
2.48 + for (NodeIt i(g); g.valid(i); g.next(i))
2.49 + std::cout << " " << g.id(i);
2.50 + std::cout << std::endl;
2.51 +\endcode
2.52 +
2.53 +Here we iterate through all nodes of the graph. We use a constructor of the
2.54 +node iterator to initialize it to the first node. The next member function is
2.55 +used to step to the next node, and valid is used to check if we have passed the
2.56 +last one.
2.57 +
2.58 +\code
2.59 + std::cout << "Nodes:";
2.60 + NodeIt n;
2.61 + for (g.first(n); n != INVALID; g.next(n))
2.62 + std::cout << " " << g.id(n);
2.63 + std::cout << std::endl;
2.64 +\endcode
2.65 +
2.66 +Here you can see an alternative way to iterate through all nodes. Here we use a
2.67 +member function of the graph to initialize the node iterator to the first node
2.68 +of the graph. Using next on the iterator pointing to the last node invalidates
2.69 +the iterator i.e. sets its value to INVALID. Checking for this value is
2.70 +equivalent to using the valid member function.
2.71 +
2.72 +Both of the previous code fragments print out the same:
2.73 +
2.74 +\code
2.75 +Nodes: 2 1 0
2.76 +\endcode
2.77 +
2.78 +\code
2.79 + std::cout << "Edges:";
2.80 + for (EdgeIt i(g); g.valid(i); g.next(i))
2.81 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
2.82 + std::cout << std::endl;
2.83 +\endcode
2.84 +
2.85 +\code
2.86 +Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
2.87 +\endcode
2.88 +
2.89 +We can also iterate through all edges of the graph very similarly. The head and
2.90 +tail member functions can be used to access the endpoints of an edge.
2.91 +
2.92 +\code
2.93 + NodeIt first_node(g);
2.94 +
2.95 + std::cout << "Out-edges of node " << g.id(first_node) << ":";
2.96 + for (OutEdgeIt i(g, first_node); g.valid(i); g.next(i))
2.97 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
2.98 + std::cout << std::endl;
2.99 +
2.100 + std::cout << "In-edges of node " << g.id(first_node) << ":";
2.101 + for (InEdgeIt i(g, first_node); g.valid(i); g.next(i))
2.102 + std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
2.103 + std::cout << std::endl;
2.104 +\endcode
2.105 +
2.106 +\code
2.107 +Out-edges of node 2: (2,0) (2,1)
2.108 +In-edges of node 2: (0,2) (1,2)
2.109 +\endcode
2.110 +
2.111 +We can also iterate through the in and out-edges of a node. In the above
2.112 +example we print out the in and out-edges of the first node of the graph.
2.113 +
2.114 +\code
2.115 + Graph::EdgeMap<int> m(g);
2.116 +
2.117 + for (EdgeIt e(g); g.valid(e); g.next(e))
2.118 + m.set(e, 10 - g.id(e));
2.119 +
2.120 + std::cout << "Id Edge Value" << std::endl;
2.121 + for (EdgeIt e(g); g.valid(e); g.next(e))
2.122 + std::cout << g.id(e) << " (" << g.id(g.tail(e)) << "," << g.id(g.head(e))
2.123 + << ") " << m[e] << std::endl;
2.124 +\endcode
2.125 +
2.126 +\code
2.127 +Id Edge Value
2.128 +4 (0,2) 6
2.129 +2 (1,2) 8
2.130 +5 (0,1) 5
2.131 +0 (2,1) 10
2.132 +3 (1,0) 7
2.133 +1 (2,0) 9
2.134 +\endcode
2.135 +
2.136 +In generic graph optimization programming graphs are not containers rather
2.137 +incidence structures which are iterable in many ways. HugoLib introduces
2.138 +concepts that allow us to attach containers to graphs. These containers are
2.139 +called maps.
2.140 +
2.141 +In the example above we create an EdgeMap which assigns an int value to all
2.142 +edges of the graph. We use the set member function of the map to write values
2.143 +into the map and the operator[] to retrieve them.
2.144 +
2.145 +Here we used the maps provided by the ListGraph class, but you can also write
2.146 +your own maps. You can read more about using maps \ref maps "here".
2.147 +
2.148 +*/
3.1 --- a/doc/mainpage.dox Thu May 27 10:04:55 2004 +0000
3.2 +++ b/doc/mainpage.dox Fri May 28 07:48:16 2004 +0000
3.3 @@ -1,6 +1,23 @@
3.4 /**
3.5 \mainpage
3.6
3.7 -Please make a better mainpage (doc/mainpage.dox).
3.8 +\section intro Introduction
3.9
3.10 -*/
3.11 \ No newline at end of file
3.12 +\subsection whatis What is HugoLib
3.13 +
3.14 +HugoLib stands for Hungarian Graph Optimization Library. It is a C++ template
3.15 +library aimed at combinatorial optimization tasks which often involve working
3.16 +with graphs. As the name also suggests, its development was started by
3.17 +Hungarian people.
3.18 +
3.19 +\subsection howtoread How to read this document
3.20 +
3.21 +If you are new to HugoLib, you probably should start \ref graphs "here".
3.22 +You can also find this page along with other under Related Pages (left-hand
3.23 +side frame).
3.24 +
3.25 +If you are more interested in details about data structures and algorithms then
3.26 +you should browse the reference manual part of the documentation. The Modules
3.27 +section is a good starting point for this.
3.28 +
3.29 +*/