COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graphs.dox @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 6.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19/*!
20
21\page graphs Graphs
22
23\todo Write a new Graphs page. I think it should be contain the Graph,
24UGraph and BpUGraph concept. It should be describe the iterators and
25the basic functions and the differences of the implementations.
26
27The primary data structures of LEMON are the graph classes. They all
28provide a node list - edge list interface, i.e. they have
29functionalities to list the nodes and the edges of the graph as well
30as  incoming and outgoing edges of a given node.
31
32Each graph should meet the \ref lemon::concepts::Graph "Graph" concept.
33This concept does not make it possible to change the graph (i.e. it is
34not possible to add or delete edges or nodes). Most of the graph
35algorithms will run on these graphs.
36
37
38In case of graphs meeting the full feature
39\ref lemon::concepts::ErasableGraph "ErasableGraph"
40concept
41you can also erase individual edges and nodes in arbitrary order.
42
43The implemented graph structures are the following.
44\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
45the \ref lemon::concepts::ErasableGraph "ErasableGraph" concept
46and it also has some convenient extra features.
47\li \ref lemon::SmartGraph "SmartGraph" is a more memory
48efficient version of \ref lemon::ListGraph "ListGraph". The
49price of this is that it only meets the
50\ref lemon::concepts::ExtendableGraph "ExtendableGraph" concept,
51so you cannot delete individual edges or nodes.
52\li \ref lemon::FullGraph "FullGraph"
53implements a complete graph. It is a
54\ref lemon::concepts::Graph "Graph", so you cannot
55change the number of nodes once it is constructed. It is extremely memory
56efficient: it uses constant amount of memory independently from the number of
57the 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.
59
60\li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
61can 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
63the node set of another graph. The base graph can be an arbitrary graph and it
64is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
65
66\todo Don't we need SmartNodeSet and SmartEdgeSet?
67\todo Some cross-refs are wrong.
68
69The graph structures themselves can not store data attached
70to the edges and nodes. However they all provide
71\ref maps-page "map classes"
72to dynamically attach data the to graph components.
73
74The following program demonstrates the basic features of LEMON's graph
75structures.
76
77\code
78#include <iostream>
79#include <lemon/list_graph.h>
80
81using namespace lemon;
82
83int main()
84{
85  typedef ListGraph Graph;
86\endcode
87
88ListGraph is one of LEMON's graph classes. It is based on linked lists,
89therefore iterating throuh its edges and nodes is fast.
90
91\code
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;
98
99  Graph g;
100 
101  for (int i = 0; i < 3; i++)
102    g.addNode();
103 
104  for (NodeIt i(g); i!=INVALID; ++i)
105    for (NodeIt j(g); j!=INVALID; ++j)
106      if (i != j) g.addEdge(i, j);
107\endcode
108
109After some convenient typedefs we create a graph and add three nodes to it.
110Then we add edges to it to form a complete graph.
111
112\code
113  std::cout << "Nodes:";
114  for (NodeIt i(g); i!=INVALID; ++i)
115    std::cout << " " << g.id(i);
116  std::cout << std::endl;
117\endcode
118
119Here we iterate through all nodes of the graph. We use a constructor of the
120node iterator to initialize it to the first node. The operator++ is used to
121step to the next node. Using operator++ on the iterator pointing to the last
122node invalidates the iterator i.e. sets its value to
123\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
124
125The previous code fragment prints out the following:
126
127\code
128Nodes: 2 1 0
129\endcode
130
131\code
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;
136\endcode
137
138\code
139Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
140\endcode
141
142We can also iterate through all edges of the graph very similarly. The
143\c target and
144\c source member functions can be used to access the endpoints of an edge.
145
146\code
147  NodeIt first_node(g);
148
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;
153
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;
158\endcode
159
160\code
161Out-edges of node 2: (2,0) (2,1)
162In-edges of node 2: (0,2) (1,2)
163\endcode
164
165We can also iterate through the in and out-edges of a node. In the above
166example we print out the in and out-edges of the first node of the graph.
167
168\code
169  Graph::EdgeMap<int> m(g);
170
171  for (EdgeIt e(g); e!=INVALID; ++e)
172    m.set(e, 10 - g.id(e));
173 
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;
178\endcode
179
180\code
181Id Edge  Value
1824  (0,2) 6
1832  (1,2) 8
1845  (0,1) 5
1850  (2,1) 10
1863  (1,0) 7
1871  (2,0) 9
188\endcode
189
190As we mentioned above, graphs are not containers rather
191incidence structures which are iterable in many ways. LEMON introduces
192concepts that allow us to attach containers to graphs. These containers are
193called maps.
194
195In the example above we create an EdgeMap which assigns an integer value to all
196edges of the graph. We use the set member function of the map to write values
197into the map and the operator[] to retrieve them.
198
199Here we used the maps provided by the ListGraph class, but you can also write
200your own maps. You can read more about using maps \ref maps-page "here".
201
202*/
Note: See TracBrowser for help on using the repository browser.