# source:lemon-0.x/doc/graphs.dox@2196:09af6d2b683b

Last change on this file since 2196:09af6d2b683b was 2116:b6a68c15a6a3, checked in by Balazs Dezso, 14 years ago

Revert splitted files

File size: 5.9 KB
Line
1/*!
2
3\page graphs Graphs
4
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
9The primary data structures of LEMON are the graph classes. They all
10provide a node list - edge list interface, i.e. they have
11functionalities to list the nodes and the edges of the graph as well
12as  incoming and outgoing edges of a given node.
13
14Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
15This concept does not make it possible to change the graph (i.e. it is
16not possible to add or delete edges or nodes). Most of the graph
17algorithms will run on these graphs.
18
19
20In case of graphs meeting the full feature
21\ref lemon::concept::ErasableGraph "ErasableGraph"
22concept
23you can also erase individual edges and nodes in arbitrary order.
24
25The implemented graph structures are the following.
26\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
27the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
28and it also has some convenient extra features.
29\li \ref lemon::SmartGraph "SmartGraph" is a more memory
30efficient version of \ref lemon::ListGraph "ListGraph". The
31price of this is that it only meets the
32\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept,
33so you cannot delete individual edges or nodes.
34\li \ref lemon::FullGraph "FullGraph"
35implements a complete graph. It is a
36\ref lemon::concept::Graph "Graph", so you cannot
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
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.
41
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
45the node set of another graph. The base graph can be an arbitrary graph and it
46is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
47
48\todo Don't we need SmartNodeSet and SmartEdgeSet?
49\todo Some cross-refs are wrong.
50
51The graph structures themselves can not store data attached
52to the edges and nodes. However they all provide
53\ref maps-page "map classes"
54to dynamically attach data the to graph components.
55
56The following program demonstrates the basic features of LEMON's graph
57structures.
58
59\code
60#include <iostream>
61#include <lemon/list_graph.h>
62
63using namespace lemon;
64
65int main()
66{
67  typedef ListGraph Graph;
68\endcode
69
70ListGraph is one of LEMON's graph classes. It is based on linked lists,
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++)
85
86  for (NodeIt i(g); i!=INVALID; ++i)
87    for (NodeIt j(g); j!=INVALID; ++j)
88      if (i != j) g.addEdge(i, j);
89\endcode
90
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.
93
94\code
95  std::cout << "Nodes:";
96  for (NodeIt i(g); i!=INVALID; ++i)
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
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
105\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
106
107The previous code fragment prints out the following:
108
109\code
110Nodes: 2 1 0
111\endcode
112
113\code
114  std::cout << "Edges:";
115  for (EdgeIt i(g); i!=INVALID; ++i)
116    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
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
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.
127
128\code
129  NodeIt first_node(g);
130
131  std::cout << "Out-edges of node " << g.id(first_node) << ":";
132  for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
133    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
134  std::cout << std::endl;
135
136  std::cout << "In-edges of node " << g.id(first_node) << ":";
137  for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
138    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
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
153  for (EdgeIt e(g); e!=INVALID; ++e)
154    m.set(e, 10 - g.id(e));
155
156  std::cout << "Id Edge  Value" << std::endl;
157  for (EdgeIt e(g); e!=INVALID; ++e)
158    std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(e))
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
172As we mentioned above, graphs are not containers rather
173incidence structures which are iterable in many ways. LEMON introduces
174concepts that allow us to attach containers to graphs. These containers are
175called maps.
176
177In the example above we create an EdgeMap which assigns an integer value to all
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