3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 \todo Write a new Graphs page. I think it should be contain the Graph,
24 UGraph and BpUGraph concept. It should be describe the iterators and
25 the basic functions and the differences of the implementations.
27 The primary data structures of LEMON are the graph classes. They all
28 provide a node list - edge list interface, i.e. they have
29 functionalities to list the nodes and the edges of the graph as well
30 as incoming and outgoing edges of a given node.
32 Each graph should meet the \ref lemon::concepts::Graph "Graph" concept.
33 This concept does not make it possible to change the graph (i.e. it is
34 not possible to add or delete edges or nodes). Most of the graph
35 algorithms will run on these graphs.
38 In case of graphs meeting the full feature
39 \ref lemon::concepts::ErasableGraph "ErasableGraph"
41 you can also erase individual edges and nodes in arbitrary order.
43 The implemented graph structures are the following.
44 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
45 the \ref lemon::concepts::ErasableGraph "ErasableGraph" concept
46 and it also has some convenient extra features.
47 \li \ref lemon::SmartGraph "SmartGraph" is a more memory
48 efficient version of \ref lemon::ListGraph "ListGraph". The
49 price of this is that it only meets the
50 \ref lemon::concepts::ExtendableGraph "ExtendableGraph" concept,
51 so you cannot delete individual edges or nodes.
52 \li \ref lemon::FullGraph "FullGraph"
53 implements a complete graph. It is a
54 \ref lemon::concepts::Graph "Graph", so you cannot
55 change the number of nodes once it is constructed. It is extremely memory
56 efficient: it uses constant amount of memory independently from the number of
57 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and
58 \ref maps-page "EdgeMap"'s will depend on the number of nodes.
60 \li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
61 can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
62 \li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
63 the node set of another graph. The base graph can be an arbitrary graph and it
64 is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
66 \todo Don't we need SmartNodeSet and SmartEdgeSet?
67 \todo Some cross-refs are wrong.
69 The graph structures themselves can not store data attached
70 to the edges and nodes. However they all provide
71 \ref maps-page "map classes"
72 to dynamically attach data the to graph components.
74 The following program demonstrates the basic features of LEMON's graph
79 #include <lemon/list_graph.h>
81 using namespace lemon;
85 typedef ListGraph Graph;
88 ListGraph is one of LEMON's graph classes. It is based on linked lists,
89 therefore iterating throuh its edges and nodes is fast.
92 typedef Graph::Edge Edge;
93 typedef Graph::InEdgeIt InEdgeIt;
94 typedef Graph::OutEdgeIt OutEdgeIt;
95 typedef Graph::EdgeIt EdgeIt;
96 typedef Graph::Node Node;
97 typedef Graph::NodeIt NodeIt;
101 for (int i = 0; i < 3; i++)
104 for (NodeIt i(g); i!=INVALID; ++i)
105 for (NodeIt j(g); j!=INVALID; ++j)
106 if (i != j) g.addEdge(i, j);
109 After some convenient typedefs we create a graph and add three nodes to it.
110 Then we add edges to it to form a complete graph.
113 std::cout << "Nodes:";
114 for (NodeIt i(g); i!=INVALID; ++i)
115 std::cout << " " << g.id(i);
116 std::cout << std::endl;
119 Here we iterate through all nodes of the graph. We use a constructor of the
120 node iterator to initialize it to the first node. The operator++ is used to
121 step to the next node. Using operator++ on the iterator pointing to the last
122 node invalidates the iterator i.e. sets its value to
123 \ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
125 The previous code fragment prints out the following:
132 std::cout << "Edges:";
133 for (EdgeIt i(g); i!=INVALID; ++i)
134 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
135 std::cout << std::endl;
139 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
142 We can also iterate through all edges of the graph very similarly. The
144 \c source member functions can be used to access the endpoints of an edge.
147 NodeIt first_node(g);
149 std::cout << "Out-edges of node " << g.id(first_node) << ":";
150 for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
151 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
152 std::cout << std::endl;
154 std::cout << "In-edges of node " << g.id(first_node) << ":";
155 for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
156 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
157 std::cout << std::endl;
161 Out-edges of node 2: (2,0) (2,1)
162 In-edges of node 2: (0,2) (1,2)
165 We can also iterate through the in and out-edges of a node. In the above
166 example we print out the in and out-edges of the first node of the graph.
169 Graph::EdgeMap<int> m(g);
171 for (EdgeIt e(g); e!=INVALID; ++e)
172 m.set(e, 10 - g.id(e));
174 std::cout << "Id Edge Value" << std::endl;
175 for (EdgeIt e(g); e!=INVALID; ++e)
176 std::cout << g.id(e) << " (" << g.id(g.source(e)) << "," << g.id(g.target(e))
177 << ") " << m[e] << std::endl;
190 As we mentioned above, graphs are not containers rather
191 incidence structures which are iterable in many ways. LEMON introduces
192 concepts that allow us to attach containers to graphs. These containers are
195 In the example above we create an EdgeMap which assigns an integer value to all
196 edges of the graph. We use the set member function of the map to write values
197 into the map and the operator[] to retrieve them.
199 Here we used the maps provided by the ListGraph class, but you can also write
200 your own maps. You can read more about using maps \ref maps-page "here".