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, 13 years ago

Happy New Year to all source files!

File size: 6.5 KB
RevLine 
[2391]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
[666]19/*!
20
[1638]21\page graphs Graphs
[666]22
[2111]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
[921]27The primary data structures of LEMON are the graph classes. They all
[756]28provide a node list - edge list interface, i.e. they have
29functionalities to list the nodes and the edges of the graph as well
[2116]30as  incoming and outgoing edges of a given node.
[756]31
[2260]32Each graph should meet the \ref lemon::concepts::Graph "Graph" concept.
[2116]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.
[756]36
37
[2116]38In case of graphs meeting the full feature
[2260]39\ref lemon::concepts::ErasableGraph "ErasableGraph"
[2116]40concept
41you can also erase individual edges and nodes in arbitrary order.
42
43The implemented graph structures are the following.
[921]44\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
[2260]45the \ref lemon::concepts::ErasableGraph "ErasableGraph" concept
[1168]46and it also has some convenient extra features.
[921]47\li \ref lemon::SmartGraph "SmartGraph" is a more memory
48efficient version of \ref lemon::ListGraph "ListGraph". The
[1168]49price of this is that it only meets the
[2260]50\ref lemon::concepts::ExtendableGraph "ExtendableGraph" concept,
[756]51so you cannot delete individual edges or nodes.
[921]52\li \ref lemon::FullGraph "FullGraph"
[1200]53implements a complete graph. It is a
[2260]54\ref lemon::concepts::Graph "Graph", so you cannot
[756]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
[1043]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.
[756]59
[921]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
[873]63the node set of another graph. The base graph can be an arbitrary graph and it
[921]64is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
[756]65
66\todo Don't we need SmartNodeSet and SmartEdgeSet?
67\todo Some cross-refs are wrong.
68
[1168]69The graph structures themselves can not store data attached
[756]70to the edges and nodes. However they all provide
[1043]71\ref maps-page "map classes"
[756]72to dynamically attach data the to graph components.
73
[921]74The following program demonstrates the basic features of LEMON's graph
[666]75structures.
76
77\code
78#include <iostream>
[921]79#include <lemon/list_graph.h>
[666]80
[921]81using namespace lemon;
[666]82
83int main()
84{
85  typedef ListGraph Graph;
86\endcode
87
[921]88ListGraph is one of LEMON's graph classes. It is based on linked lists,
[666]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 
[875]104  for (NodeIt i(g); i!=INVALID; ++i)
105    for (NodeIt j(g); j!=INVALID; ++j)
[666]106      if (i != j) g.addEdge(i, j);
107\endcode
108
[1168]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.
[666]111
112\code
113  std::cout << "Nodes:";
[875]114  for (NodeIt i(g); i!=INVALID; ++i)
[666]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
[875]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
[921]123\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
[666]124
[875]125The previous code fragment prints out the following:
[666]126
127\code
128Nodes: 2 1 0
129\endcode
130
131\code
132  std::cout << "Edges:";
[875]133  for (EdgeIt i(g); i!=INVALID; ++i)
[986]134    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
[666]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
[1168]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.
[666]145
146\code
147  NodeIt first_node(g);
148
149  std::cout << "Out-edges of node " << g.id(first_node) << ":";
[875]150  for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
[986]151    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
[666]152  std::cout << std::endl;
153
154  std::cout << "In-edges of node " << g.id(first_node) << ":";
[875]155  for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
[986]156    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
[666]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
[875]171  for (EdgeIt e(g); e!=INVALID; ++e)
[666]172    m.set(e, 10 - g.id(e));
173 
174  std::cout << "Id Edge  Value" << std::endl;
[875]175  for (EdgeIt e(g); e!=INVALID; ++e)
[986]176    std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(e))
[666]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
[873]190As we mentioned above, graphs are not containers rather
[921]191incidence structures which are iterable in many ways. LEMON introduces
[666]192concepts that allow us to attach containers to graphs. These containers are
193called maps.
194
[1168]195In the example above we create an EdgeMap which assigns an integer value to all
[666]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
[1043]200your own maps. You can read more about using maps \ref maps-page "here".
[666]201
202*/
Note: See TracBrowser for help on using the repository browser.