ladanyi@666: /*!
ladanyi@666: 
ladanyi@1638: \page graphs Graphs
ladanyi@666: 
deba@2111: \todo Write a new Graphs page. I think it should be contain the Graph,
deba@2111: UGraph and BpUGraph concept. It should be describe the iterators and
deba@2111: the basic functions and the differences of the implementations.
deba@2111: 
alpar@921: The primary data structures of LEMON are the graph classes. They all
alpar@756: provide a node list - edge list interface, i.e. they have
alpar@756: functionalities to list the nodes and the edges of the graph as well
deba@2116: as  incoming and outgoing edges of a given node. 
alpar@756: 
alpar@2260: Each graph should meet the \ref lemon::concepts::Graph "Graph" concept.
deba@2116: This concept does not make it possible to change the graph (i.e. it is
deba@2116: not possible to add or delete edges or nodes). Most of the graph
deba@2116: algorithms will run on these graphs.
alpar@756: 
alpar@756: 
deba@2116: In case of graphs meeting the full feature
alpar@2260: \ref lemon::concepts::ErasableGraph "ErasableGraph"
deba@2116: concept
deba@2116: you can also erase individual edges and nodes in arbitrary order.
deba@2116: 
deba@2116: The implemented graph structures are the following.
alpar@921: \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
alpar@2260: the \ref lemon::concepts::ErasableGraph "ErasableGraph" concept
athos@1168: and it also has some convenient extra features.
alpar@921: \li \ref lemon::SmartGraph "SmartGraph" is a more memory
alpar@921: efficient version of \ref lemon::ListGraph "ListGraph". The
athos@1168: price of this is that it only meets the
alpar@2260: \ref lemon::concepts::ExtendableGraph "ExtendableGraph" concept,
alpar@756: so you cannot delete individual edges or nodes.
alpar@921: \li \ref lemon::FullGraph "FullGraph"
alpar@1200: implements a complete graph. It is a
alpar@2260: \ref lemon::concepts::Graph "Graph", so you cannot
alpar@756: change the number of nodes once it is constructed. It is extremely memory
alpar@756: efficient: it uses constant amount of memory independently from the number of
alpar@1043: the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and
alpar@1043: \ref maps-page "EdgeMap"'s will depend on the number of nodes.
alpar@756: 
alpar@921: \li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
alpar@921: can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
alpar@921: \li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
alpar@873: the node set of another graph. The base graph can be an arbitrary graph and it
alpar@921: is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
alpar@756: 
alpar@756: \todo Don't we need SmartNodeSet and SmartEdgeSet?
alpar@756: \todo Some cross-refs are wrong.
alpar@756: 
athos@1168: The graph structures themselves can not store data attached
alpar@756: to the edges and nodes. However they all provide
alpar@1043: \ref maps-page "map classes"
alpar@756: to dynamically attach data the to graph components.
alpar@756: 
alpar@921: The following program demonstrates the basic features of LEMON's graph
ladanyi@666: structures.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666: #include <iostream>
alpar@921: #include <lemon/list_graph.h>
ladanyi@666: 
alpar@921: using namespace lemon;
ladanyi@666: 
ladanyi@666: int main()
ladanyi@666: {
ladanyi@666:   typedef ListGraph Graph;
ladanyi@666: \endcode
ladanyi@666: 
alpar@921: ListGraph is one of LEMON'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@875:   for (NodeIt i(g); i!=INVALID; ++i)
ladanyi@875:     for (NodeIt j(g); j!=INVALID; ++j)
ladanyi@666:       if (i != j) g.addEdge(i, j);
ladanyi@666: \endcode
ladanyi@666: 
athos@1168: After some convenient typedefs we create a graph and add three nodes to it.
athos@1168: Then we add edges to it to form a complete graph.
ladanyi@666: 
ladanyi@666: \code
ladanyi@666:   std::cout << "Nodes:";
ladanyi@875:   for (NodeIt i(g); i!=INVALID; ++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@875: node iterator to initialize it to the first node. The operator++ is used to
ladanyi@875: step to the next node. Using operator++ on the iterator pointing to the last
ladanyi@875: node invalidates the iterator i.e. sets its value to
alpar@921: \ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
ladanyi@666: 
ladanyi@875: The previous code fragment prints out the following:
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@875:   for (EdgeIt i(g); i!=INVALID; ++i)
alpar@986:     std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(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: 
athos@1168: We can also iterate through all edges of the graph very similarly. The 
athos@1168: \c target and
athos@1168: \c source 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@875:   for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986:     std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 
ladanyi@666:   std::cout << std::endl;
ladanyi@666: 
ladanyi@666:   std::cout << "In-edges of node " << g.id(first_node) << ":";
ladanyi@875:   for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986:     std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(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@875:   for (EdgeIt e(g); e!=INVALID; ++e)
ladanyi@666:     m.set(e, 10 - g.id(e));
ladanyi@666:   
ladanyi@666:   std::cout << "Id Edge  Value" << std::endl;
ladanyi@875:   for (EdgeIt e(g); e!=INVALID; ++e)
alpar@986:     std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(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: 
alpar@873: As we mentioned above, graphs are not containers rather
alpar@921: incidence structures which are iterable in many ways. LEMON introduces
ladanyi@666: concepts that allow us to attach containers to graphs. These containers are
ladanyi@666: called maps.
ladanyi@666: 
athos@1168: In the example above we create an EdgeMap which assigns an integer 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
alpar@1043: your own maps. You can read more about using maps \ref maps-page "here".
ladanyi@666: 
ladanyi@666: */