COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graphs.dox @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 18 years ago

Splitted graph files

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