alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: kpeter@2476: namespace lemon { kpeter@2476: 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: kpeter@2476: Each graph should meet the \ref 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 kpeter@2476: \ref concepts::ErasableGraph "ErasableGraph" 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. kpeter@2476: \li \ref ListGraph is the most versatile graph class. It meets kpeter@2476: the \ref concepts::ErasableGraph "ErasableGraph" concept athos@1168: and it also has some convenient extra features. kpeter@2476: \li \ref SmartGraph is a more memory efficient version of \ref ListGraph. kpeter@2476: The price of this is that it only meets the kpeter@2476: \ref concepts::ExtendableGraph "ExtendableGraph" concept, alpar@756: so you cannot delete individual edges or nodes. kpeter@2476: \li \ref FullGraph "FullGraph" alpar@1200: implements a complete graph. It is a kpeter@2476: \ref 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: kpeter@2476: \li \ref NodeSet "NodeSet" implements a graph with no edges. This class alpar@921: can be used as a base class of \ref lemon::EdgeSet "EdgeSet". kpeter@2476: \li \ref 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 kpeter@2476: is possible to attach several \ref 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 alpar@921: #include 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 kpeter@2476: \ref 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 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: */ kpeter@2476: kpeter@2476: } kpeter@2476: