COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graphs.dox @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2476:059dcdda37c5, checked in by Peter Kovacs, 12 years ago

Bug fixes in the documentation (mainly bad references).

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