COIN-OR::LEMON - Graph Library

Changeset 37:c8be1109221b in lemon-tutorial


Ignore:
Timestamp:
02/20/10 21:54:52 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve and extend basics page

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • basics.dox

    r32 r37  
    3232[SEC]sec_digraphs[SEC] Directed Graphs
    3333
     34The core features of LEMON are the data structures, algorithms and auxiliary
     35tools that make it possible to represent graphs and working with them easily
     36and efficiently.
    3437This section tells you how to work with a directed graph (\e digraph,
    3538for short) in LEMON. Here we use \ref ListDigraph, the most versatile
    3639digraph structure. (The library also provides other digraph types,
    3740see \ref sec_graph_structures "later".)
     41
     42For using \ref ListDigraph, you must include the header file
     43\ref list_graph.h like this:
     44
     45\code
     46#include <lemon/list_graph.h>
     47\endcode
     48
     49The default constructor of the class creates an empty digraph.
     50
     51\code
     52  ListDigraph g;
     53\endcode
    3854
    3955The nodes and the arcs of a graph are identified by two data types called
     
    4460
    4561\code
    46   ListDigraph g;
    47   ListDigraph::Node a = g.addNode();
    48   ListDigraph::Node b = g.addNode();
    49   ListDigraph::Node c = g.addNode();
    50   ListDigraph::Node d = g.addNode();
    51 
    52   g.addArc(a,b);
    53   g.addArc(b,c);
    54   g.addArc(c,d);
    55   g.addArc(d,a);
     62  ListDigraph::Node x = g.addNode();
     63  ListDigraph::Node y = g.addNode();
     64  ListDigraph::Node z = g.addNode();
     65
     66  g.addArc(x,y);
     67  g.addArc(y,z);
     68  g.addArc(z,x);
    5669\endcode
    5770
     
    5972
    6073\code
    61   ListDigraph::Arc arc = g.addArc(a,c);
     74  ListDigraph::Arc arc = g.addArc(x,z);
     75\endcode
     76
     77Parallel and loop arcs are also supported.
     78
     79\code
     80  ListDigraph::Arc parallel = g.addArc(x,y);
     81  ListDigraph::Arc loop = g.addArc(x,x);
    6282\endcode
    6383
     
    7292\ref concepts::Digraph::source() "source()"
    7393and \ref concepts::Digraph::target() "target()".
    74 They give back the two end nodes of an arc.
    75 
    76 \code
    77   if (g.source(arc) == g.target(arc))
     94They give back the two end nodes of an arc (as \c Node objects).
     95
     96\code
     97  if (g.source(loop) == g.target(loop))
    7898    std::cout << "This is a loop arc" << std::endl;
    7999\endcode
    80100
    81 Each graph item has a unique integer identifier, which can be obtained using
    82 the \ref concepts::Digraph::id() "id()" function of the graph structure.
     101Each graph item has a non-negative integer identifier, which can be obtained
     102using the \ref concepts::Digraph::id() "id()" function of the graph structure.
     103These identifiers are unique with respect to a certain item type in a graph,
     104but a node and an arc may have the same id.
    83105
    84106\code
     
    94116
    95117Let us assume you want to list the elements of the graph. For this purpose,
    96 the graph structures provide several iterators. For example, the following
     118the graph structures provide several \e iterators. For example, the following
    97119code will count the number of nodes in a graph.
    98120
     
    104126\endcode
    105127
    106 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
    107 is an iterator class that traverses the
    108 nodes. You must give the graph to the constructor and the iterator will be set
     128\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
     129is an iterator class that lists the nodes.
     130The name of an iterator type starts with a name that refers to
     131the iterated objects and ends with 'It'.
     132
     133Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
     134the graph object to the constructor and the iterator will be set
    109135to the first node. The next node is obtained by the prefix ++
    110136operator. If there are no more nodes in the graph, the iterator will
    111 be set to \ref INVALID.
    112 
    113 \note \ref INVALID is a global constant, which converts to
    114 and compares with each and every iterator in LEMON.
    115 
    116 The iterators convert to the corresponding item types. For example,
    117 to following code will add a full graph to the existing nodes.
     137be set to \ref INVALID, which is exploited in the stop condition of
     138the loop.
     139
     140\note \ref INVALID is a constant in the \ref lemon namespace, which converts to
     141and compares with each and every iterator and graph item type.
     142Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
     143
     144The iterators convert to the corresponding item types.
     145For example, the identifiers of the nodes can be printed like this.
     146
     147\code
     148  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
     149    std::cout << g.id(n) << std::endl;
     150\endcode
     151
     152As an other example, the following code adds a full graph to the
     153existing nodes.
    118154
    119155\code
     
    163199\code
    164200  int cnt = 0;
    165   for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
     201  for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
    166202    cnt++;
    167   std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
    168 \endcode
     203  std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
     204\endcode
     205
     206\note LEMON provides functions for counting the nodes and arcs of a digraph:
     207\ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs().
     208Using them is not just simpler than the above loops, but they could be much
     209faster, since several graph types support constant time item counting.
    169210
    170211
     
    184225  initialized. On the removal of an item, the corresponding values in the maps
    185226  are properly destructed.
     227 
     228By principle, the graph classes represent only the pure structure of
     229the graph (i.e. the nodes and arcs and their connections).
     230All data that are assigned to the items of the graph (e.g. node labels,
     231arc costs or capacities) must be stored separately using maps.
    186232
    187233\note These maps must not be confused with \c std::map, since they provide
    188 O(1) time acces to the elements instead of O(log n).
     234O(1) time access to the elements instead of O(log n).
    189235
    190236So, if you want to assign \c int values to each node, you have to allocate a
     
    199245
    200246\code
    201   map[a] = 2;
    202   map[b] = 3;
    203   map[c] = map[a] + map[b];
    204 \endcode
    205 
    206 Any kind of data can be assigned to the graph items.
    207 
    208 \code
    209   ListDigraph::NodeMap<std::string> label(g);
    210   label[a] = "Node A";
    211   label[b] = "Node B";
    212 \endcode
    213 
    214 For a more complex example, let us create a map that assigns a unique
    215 integer number to each node.
    216 
    217 \code
    218   ListDigraph::NodeMap<int> id(g);
    219   int cnt = 0;
     247  map[x] = 2;
     248  map[y] = 3;
     249  map[z] = map[x] + map[y];
     250\endcode
     251
     252Any kind of data can be assigned to the graph items (assuming that the type
     253has a default constructor).
     254
     255\code
     256  ListDigraph::NodeMap<std::string> name(g);
     257  name[x] = "Node A";
     258  name[y] = "Node B";
     259\endcode
     260
     261As a more complex example, let us create a map that assigns \c char labels
     262to the nodes.
     263
     264\code
     265  ListDigraph::NodeMap<char> label(g);
     266  char ch = 'A';
    220267  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    221     id[n] = cnt++;
     268    label[n] = ch++;
    222269\endcode
    223270
     
    228275\code
    229276  ListDigraph::NodeMap<int> out_deg(g, 0);
    230 
    231277  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
    232278    out_deg[g.source(a)]++;
     
    238284type.
    239285
     286
     287[SEC]sec_naming_conv[SEC] Naming Conventions
     288
     289In LEMON, there are some naming conventions you might already notice
     290in the above examples.
     291
     292The name of a source file is written lowercase and the words are separated with
     293underscores (e.g. \ref list_graph.h). All header files are located in the
     294\c %lemon subdirectory, so you can include them like this.
     295
     296\code
     297#include <lemon/header_file.h>
     298\endcode
     299
     300The name of a class or any type looks like the following
     301(e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node",
     302\ref concepts::Digraph::NodeIt "NodeIt" etc.).
     303
     304\code
     305AllWordsCapitalizedWithoutUnderscores
     306\endcode
     307
     308The name of a function looks like the following
     309(e.g. \ref concepts::Digraph::source() "source()",
     310\ref concepts::Digraph::source() "target()",
     311\ref countNodes(), \ref countArcs() etc.).
     312
     313\code
     314firstWordLowerCaseRestCapitalizedWithoutUnderscores
     315\endcode
     316
     317The names of constants and macros look like the following
     318(e.g. \ref INVALID).
     319
     320\code
     321ALL_UPPER_CASE_WITH_UNDERSCORES
     322\endcode
     323
     324For more details, see \ref coding_style.
     325
    240326[TRAILER]
    241327*/
  • toc.txt

    r31 r37  
    77** sec_digraph_it
    88** sec_digraph_maps
     9** sec_naming_conv
    910*_sec_algorithms
    1011**_sec_alg_graph_search
Note: See TracChangeset for help on using the changeset viewer.