ladanyi@666: /*!
ladanyi@666: 
ladanyi@666: \page graphs How to use graphs
ladanyi@666: 
ladanyi@666: The following program demonstrates the basic features of HugoLib's graph
ladanyi@666: structures.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: #include <iostream>
ladanyi@666: #include <hugo/list_graph.h>
ladanyi@666: 
ladanyi@666: using namespace hugo;
ladanyi@666: 
ladanyi@666: int main()
ladanyi@666: {
ladanyi@666:   typedef ListGraph Graph;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: ListGraph is one of HugoLib's graph classes. It is based on linked lists,
ladanyi@666: therefore iterating throuh its edges and nodes is fast.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   typedef Graph::Edge Edge;
ladanyi@666:   typedef Graph::InEdgeIt InEdgeIt;
ladanyi@666:   typedef Graph::OutEdgeIt OutEdgeIt;
ladanyi@666:   typedef Graph::EdgeIt EdgeIt;
ladanyi@666:   typedef Graph::Node Node;
ladanyi@666:   typedef Graph::NodeIt NodeIt;
ladanyi@666: 
ladanyi@666:   Graph g;
ladanyi@666:   
ladanyi@666:   for (int i = 0; i < 3; i++)
ladanyi@666:     g.addNode();
ladanyi@666:   
ladanyi@666:   for (NodeIt i(g); g.valid(i); g.next(i))
ladanyi@666:     for (NodeIt j(g); g.valid(j); g.next(j))
ladanyi@666:       if (i != j) g.addEdge(i, j);
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: After some convenience typedefs we create a graph and add three nodes to it.
ladanyi@666: Then we add edges to it to form a full graph.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   std::cout << "Nodes:";
ladanyi@666:   for (NodeIt i(g); g.valid(i); g.next(i))
ladanyi@666:     std::cout << " " << g.id(i);
ladanyi@666:   std::cout << std::endl;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: Here we iterate through all nodes of the graph. We use a constructor of the
ladanyi@666: node iterator to initialize it to the first node. The next member function is
ladanyi@666: used to step to the next node, and valid is used to check if we have passed the
ladanyi@666: last one.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   std::cout << "Nodes:";
ladanyi@666:   NodeIt n;
ladanyi@666:   for (g.first(n); n != INVALID; g.next(n))
ladanyi@666:     std::cout << " " << g.id(n);
ladanyi@666:   std::cout << std::endl;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: Here you can see an alternative way to iterate through all nodes. Here we use a
ladanyi@666: member function of the graph to initialize the node iterator to the first node
ladanyi@666: of the graph. Using next on the iterator pointing to the last node invalidates
ladanyi@666: the iterator i.e. sets its value to INVALID. Checking for this value is
ladanyi@666: equivalent to using the valid member function.
ladanyi@666: 
ladanyi@666: Both of the previous code fragments print out the same:
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: Nodes: 2 1 0
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   std::cout << "Edges:";
ladanyi@666:   for (EdgeIt i(g); g.valid(i); g.next(i))
ladanyi@666:     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
ladanyi@666:   std::cout << std::endl;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: We can also iterate through all edges of the graph very similarly. The head and
ladanyi@666: tail member functions can be used to access the endpoints of an edge.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   NodeIt first_node(g);
ladanyi@666: 
ladanyi@666:   std::cout << "Out-edges of node " << g.id(first_node) << ":";
ladanyi@666:   for (OutEdgeIt i(g, first_node); g.valid(i); g.next(i))
ladanyi@666:     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; 
ladanyi@666:   std::cout << std::endl;
ladanyi@666: 
ladanyi@666:   std::cout << "In-edges of node " << g.id(first_node) << ":";
ladanyi@666:   for (InEdgeIt i(g, first_node); g.valid(i); g.next(i))
ladanyi@666:     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; 
ladanyi@666:   std::cout << std::endl;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: Out-edges of node 2: (2,0) (2,1)
ladanyi@666: In-edges of node 2: (0,2) (1,2)
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: We can also iterate through the in and out-edges of a node. In the above
ladanyi@666: example we print out the in and out-edges of the first node of the graph.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   Graph::EdgeMap<int> m(g);
ladanyi@666: 
ladanyi@666:   for (EdgeIt e(g); g.valid(e); g.next(e))
ladanyi@666:     m.set(e, 10 - g.id(e));
ladanyi@666:   
ladanyi@666:   std::cout << "Id Edge  Value" << std::endl;
ladanyi@666:   for (EdgeIt e(g); g.valid(e); g.next(e))
ladanyi@666:     std::cout << g.id(e) << "  (" << g.id(g.tail(e)) << "," << g.id(g.head(e))
ladanyi@666:       << ") " << m[e] << std::endl;
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: Id Edge  Value
ladanyi@666: 4  (0,2) 6
ladanyi@666: 2  (1,2) 8
ladanyi@666: 5  (0,1) 5
ladanyi@666: 0  (2,1) 10
ladanyi@666: 3  (1,0) 7
ladanyi@666: 1  (2,0) 9
ladanyi@666: \endcode
ladanyi@666: 
ladanyi@666: In generic graph optimization programming graphs are not containers rather
ladanyi@666: incidence structures which are iterable in many ways. HugoLib introduces
ladanyi@666: concepts that allow us to attach containers to graphs. These containers are
ladanyi@666: called maps.
ladanyi@666: 
ladanyi@666: In the example above we create an EdgeMap which assigns an int value to all
ladanyi@666: edges of the graph. We use the set member function of the map to write values
ladanyi@666: into the map and the operator[] to retrieve them.
ladanyi@666: 
ladanyi@666: Here we used the maps provided by the ListGraph class, but you can also write
ladanyi@666: your own maps. You can read more about using maps \ref maps "here".
ladanyi@666: 
ladanyi@666: */