COIN-OR::LEMON - Graph Library

source: lemon-tutorial/graphs.dox @ 31:02083323ff2c

Last change on this file since 31:02083323ff2c was 28:42b0128ae0a7, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Add a page about undirected graphs and special graph types

File size: 7.6 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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
19namespace lemon {
20/**
21[PAGE]sec_graph_structures[PAGE] Graph Structures
22
23The implementation of combinatorial algorithms heavily relies on
24efficient graph structures. Diverse applications require the
25usage of different physical graph storages.
26In \ref sec_basics, we have introduced a general digraph structure,
27\ref ListDigraph. Apart from this class, LEMON provides several
28other classes for handling directed and undirected graphs to meet the
29diverging requirements of the possible users. In order to save on running
30time or on memory usage, some structures may fail to support some graph
31features like node or arc/edge deletion.
32You are free to use the graph structure that fit your requirements the best,
33since most graph algorithms and auxiliary data structures can be used
34with any of them.
35
36
37[SEC]sec_graph_concepts[SEC] Graph Concepts
38
39In LEMON, there are various graph types, which are rather different, but
40they all conform to the corresponding \ref graph_concepts "graph concept",
41which defines the common part of the graph interfaces.
42The \ref concepts::Digraph "Digraph concept" describes the common interface
43of directed graphs (without any sensible implementation), while
44the \ref concepts::Graph "Graph concept" describes the undirected graphs.
45Any generic graph algorithm should only exploit the features of the
46corresponding graph concept. (It should compile with the
47\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
48but it will not run properly, of course.)
49
50The graph %concepts define the member classes for the iterators and maps
51along with some useful basic functions for obtaining the identifiers of
52the items, the end nodes of the arcs (or edges) and their iterators,
53etc.
54An actual graph implementation may have various additional functionalities
55according to its purpose.
56
57
58[SEC]sec_digraph_types[SEC] Digraph Structures
59
60The already used \ref ListDigraph class is the most versatile directed
61graph structure. Apart from the general digraph functionalities, it
62provides operations for adding and removing nodes and arcs, changing
63the source or target node of an arc, and contracting and splitting nodes
64or arcs.
65
66\ref SmartDigraph is another general digraph implementation, which is
67significantly more efficient (both in terms of space and time), but it
68provides less functionality. For example, nodes and arcs cannot be
69removed from it.
70
71\ref FullDigraph is an efficient implementation of a directed full graph.
72This structure is completely static, so you can neither add nor delete
73arcs or nodes, and the class needs constant space in memory.
74
75
76[SEC]sec_undir_graphs[SEC] Undirected Graphs
77
78LEMON also provides undirected graph structures. For example,
79\ref ListGraph and \ref SmartGraph are the undirected versions of
80\ref ListDigraph and \ref SmartDigraph, respectively.
81They provide similar features to the digraph structures.
82
83The \ref concepts::Graph "undirected graphs" also fulfill the concept of
84\ref concepts::Digraph "directed graphs", in such a way that each
85undirected \e edge of a graph can also be regarded as two oppositely
86directed \e arcs. As a result, all directed graph algorithms automatically
87run on undirected graphs, as well.
88
89Undirected graphs provide an \c Edge type for the \e undirected \e edges
90and an \c Arc type for the \e directed \e arcs. The \c Arc type is
91convertible to \c Edge (or inherited from it), thus the corresponding
92edge can always be obtained from an arc.
93
94Only nodes and edges can be added to or removed from an undirected
95graph and the corresponding arcs are added or removed automatically
96(there are twice as many arcs as edges)
97
98For example,
99\code
100  ListGraph g;
101 
102  ListGraph::Node a = g.addNode();
103  ListGraph::Node b = g.addNode();
104  ListGraph::Node c = g.addNode();
105
106  ListGraph::Edge e = g.addEdge(a,b);
107  g.addEdge(b,c);
108  g.addEdge(c,a);
109\endcode
110
111Each edge has an inherent orientation, thus it can be defined whether an
112arc is forward or backward oriented in an undirected graph with respect
113to this default oriantation of the represented edge.
114The direction of an arc can be obtained and set using the functions
115\ref concepts::Graph::direction() "direction()" and
116\ref concepts::Graph::direct() "direct()", respectively.
117
118For example,
119\code
120  ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
121  ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
122
123  if (a2 == g.oppositeArc(a1))
124    std::cout << "a2 is the opposite of a1" << std::endl;
125\endcode
126
127The end nodes of an edge can be obtained using the functions
128\ref concepts::Graph::source() "u()" and
129\ref concepts::Graph::target() "v()", while the
130\ref concepts::Graph::source() "source()" and
131\ref concepts::Graph::target() "target()" can be used for arcs.
132
133\code
134  std::cout << "Edge " << g.id(e) << " connects node "
135    << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
136 
137  std::cout << "Arc " << g.id(a2) << " goes from node "
138    << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
139\endcode
140
141
142Similarly to the digraphs, the undirected graphs also provide iterators
143\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
144\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
145"InArcIt", which can be used the same way.
146However, they also have iterator classes for edges.
147\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
148\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
149certain node.
150
151For example, the degree of each node can be computed and stored in a node map
152like this:
153
154\code
155  ListGraph::NodeMap<int> deg(g, 0);
156  for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
157    for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
158      deg[n]++;
159    }
160  }
161\endcode
162
163In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
164and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
165but with opposite direction. They are convertible to both \c Arc and
166\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
167on these edges, but it is not convertible to \c Arc, only to \c Edge.
168
169Apart from the node and arc maps, an undirected graph also defines
170a template member class for constructing edge maps. These maps can be
171used in conjunction with both edges and arcs.
172
173For example,
174\code
175  ListGraph::EdgeMap cost(g);
176  cost[e] = 10;
177  std::cout << cost[e] << std::endl;
178  std::cout << cost[a1] << ", " << cost[a2] << std::endl;
179
180  ListGraph::ArcMap arc_cost(g);
181  arc_cost[a1] = cost[a1];
182  arc_cost[a2] = 2 * cost[a2];
183  // std::cout << arc_cost[e] << std::endl;   // this is not valid
184  std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
185\endcode
186 
187[SEC]sec_special_graphs[SEC] Special Graph Structures
188
189In addition to the general undirected classes \ref ListGraph and
190\ref SmartGraph, LEMON also provides special purpose graph types for
191handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
192\ref HypercubeGraph "hypercube graphs".
193They all static structures, i.e. they do not allow distinct item additions
194or deletions, the graph has to be built at once.
195
196[TRAILER]
197*/
198}
Note: See TracBrowser for help on using the repository browser.