COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graphs.dox @ 2015:5e51c9eb5e83

Last change on this file since 2015:5e51c9eb5e83 was 1638:4e50ed042394, checked in by Akos Ladanyi, 14 years ago

less stupid title

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