COIN-OR::LEMON - Graph Library

Changeset 27:b453a59230c8 in lemon-tutorial


Ignore:
Timestamp:
02/14/10 22:19:50 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rework and extend the section of basic concepts

File:
1 edited

Legend:

Unmodified
Added
Removed
  • basics.dox

    r26 r27  
    2121[PAGE]sec_basics[PAGE] Basic Concepts
    2222
    23 Throughout the document we are working with the \ref lemon namespace.
    24 To save a lot of typing we assume that a
     23Throughout the tutorial we are working with the \ref lemon namespace.
     24To save a lot of typing, we assume that a
    2525
    2626\code
     
    3232[SEC]sec_digraphs[SEC] Directed Graphs
    3333
    34 This section tells you how to work with a directed graph. We use ListDigraph,
    35 the most versatile graph structure.
    36 
    37 The nodes and the arcs of a graph are identified by two datatypes called
    38 ListDigraph::Node and ListDigraph::Arc. You can add new components the graph
    39 by the \ref ListDigraph::addNode() "addNode()" and the
    40 \ref ListDigraph::addArc() "addArc()" member functions, like this:
     34This section tells you how to work with a directed graph (\e digraph,
     35for short) in LEMON.
     36The library provides various digraph structures for both general and special
     37purposes. Here we use \c ListDigraph, the most versatile digraph type.
     38
     39The nodes and the arcs of a graph are identified by two data types called
     40\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
     41"ListDigraph::Arc". You can add new items to the graph using the member
     42functions \ref ListDigraph::addNode() "addNode()" and
     43\ref ListDigraph::addArc() "addArc()", like this:
    4144
    4245\code
     
    5659
    5760\code
    58   ListDigraph::Arc diag = g.addArc(a,c);
    59 \endcode
    60 
    61 \note You can also remove nodes or arcs with the
    62 \ref ListDigraph::erase() "erase()", but this operation may not be available
    63 with all graph structures.
    64 
    65 Two other important member functions are
     61  ListDigraph::Arc arc = g.addArc(a,c);
     62\endcode
     63
     64\note Using ListDigraph, you can also remove nodes or arcs with the
     65\ref ListDigraph::erase() "erase()" function.
     66However, not all graph structures support the addition and deletion
     67of graph items.
     68
     69Two important member functions of the directed graphs are
    6670\ref concepts::Digraph::source() "source()"
    6771and \ref concepts::Digraph::target() "target()".
    68 They gives back the to end nodes of and arc.
    69 
    70 \code
    71   if(g.source(e)==g.target(e))
     72They give back the two end nodes of an arc.
     73
     74\code
     75  if (g.source(arc) == g.target(arc))
    7276    std::cout << "This is a loop arc" << std::endl;
    7377\endcode
    7478
     79Each graph item has a unique integer identifier, which can be obtained using
     80the \ref concepts::Digraph::id() "id()" function of the graph structure.
     81
     82\code
     83  std::cout << "Arc " << g.id(arc) << " goes from node "
     84    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
     85\endcode
     86
     87\note In fact, the \c Node and \c Arc types are typically simple wrapper
     88classes for a single \c int value, which is the identifier of the item.
     89
    7590
    7691[SEC]sec_digraph_it[SEC] Iterators
    7792
    78 Now assume you want to list the elements of the graph. For this purpose the
    79 the graphs provides several iterators. For example for following code will
    80 cound the number of nodes in a graph.
    81 
    82 \code
    83   int cnt = 0;
    84   for(ListDigraph::NodeIt n(g); n!=INVALID; ++n)
     93Let us assume you want to list the elements of the graph. For this purpose,
     94the graph structures provide several iterators. For example, the following
     95code will count the number of nodes in a graph.
     96
     97\code
     98  int cnt = 0;
     99  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    85100    cnt++;
    86101  std::cout << "Number of nodes: " << cnt << std::endl;
     
    88103
    89104Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
    90 is an iterator class that lists the
    91 nodes. You must give the graph to the constructor and it will be set
     105is an iterator class that traverses the
     106nodes. You must give the graph to the constructor and the iterator will be set
    92107to the first node. The next node is obtained by the prefix ++
    93 operator.  If there is no more nodes in the graph, the iterator will
     108operator. If there are no more nodes in the graph, the iterator will
    94109be set to \ref INVALID.
    95110
    96 \note \ref INVALID is a global constant in lemon and it converts to
    97 and compares with each and every iterators in LEMON.
    98 
    99 The iterators converts to the corresponding descriptor types. For example
     111\note \ref INVALID is a global constant, which converts to
     112and compares with each and every iterator in LEMON.
     113
     114The iterators convert to the corresponding item types. For example,
    100115to following code will add a full graph to the existing nodes.
    101116
    102117\code
    103   for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
    104     for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
    105       if(u!=v) g.addArc(u,v);
    106 \endcode
    107 
    108 The items are also ordered by the 'less than' operator. For example this
    109 code will add only one of the opposite arcs.
    110 
    111 \code
    112   for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
    113     for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
    114       if(u<v) g.addArc(u,v);
    115 \endcode
    116 
    117 \warning There order in which the iterator visits the items is
     118  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
     119    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
     120      if (u != v) g.addArc(u, v);
     121\endcode
     122
     123\note Contrary to the iterators in the C++ Standard Template Library (STL),
     124LEMON iterators are convertible to the corresponding
     125item types without having to use \c %operator*(). This is not confusing, since the
     126program context always indicates whether we refer to the iterator or to the graph
     127item (they do not have conflicting functionalities).
     128
     129The graph items are also ordered by the 'less than' operator (with respect to
     130their integer identifiers). For example, this code will add only one of the
     131opposite arcs.
     132
     133\code
     134  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
     135    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
     136      if (u < v) g.addArc(u, v);
     137\endcode
     138
     139\warning The order in which the iterators visit the items is
    118140undefined. The only thing you may assume that they will list the items
    119141in the same order until the graph is not changed.
     
    125147\code
    126148  int cnt = 0;
    127   for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
     149  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
    128150    cnt++;
    129151  std::cout << "Number of arcs: " << cnt << std::endl;
     
    135157and
    136158\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
    137 Their usage are the same, but you must also give the node to the constructor.
    138 
    139 \code
    140   int cnt = 0;
    141   for(ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)
     159Their usage is the same, but you must also give the node to the constructor.
     160
     161\code
     162  int cnt = 0;
     163  for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
    142164    cnt++;
    143165  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
     
    147169[SEC]sec_digraph_maps[SEC] Maps
    148170
    149 The concept of "Maps" is another fundamental part of LEMON. They allow assigning
    150 values of any type to the nodes or arcs of a graph. The default maps
     171The concept of "maps" is another fundamental part of LEMON. They allow assigning
     172values of any type to the nodes or arcs of a graph. The standard maps
    151173provided by the graph structures have a couple of nice properties.
    152174
    153 - \e Fast. Accessing (reading/writing) the values are as fast as a
    154   simple vector reading/writing
     175- \e Fast. Accessing (reading/writing) the values is as fast as a
     176  simple vector reading/writing.
    155177- \e Dynamic. Whenever you need, you
    156178  can allocate new maps in your code, just as a local variable. So when you
     
    161183  are properly destructed.
    162184
     185\note These maps must not be confused with \c std::map, since they provide
     186O(1) time acces to the elements instead of O(log n).
     187
    163188So, if you want to assign \c int values to each node, you have to allocate a
    164 \ref concepts::Digraph::Node Map "NodeMap<int>".
     189\ref concepts::Digraph::NodeMap "NodeMap<int>".
    165190
    166191\code
     
    172197
    173198\code
    174   map[a]=2;
    175   map[b]=3;
    176   map[c]=map[a]+map[b];
    177 \endcode
    178 
    179 As a more complex example, let's create a map that assigns a unique
     199  map[a] = 2;
     200  map[b] = 3;
     201  map[c] = map[a] + map[b];
     202\endcode
     203
     204Any kind of data can be assigned to the graph items.
     205
     206\code
     207  ListDigraph::NodeMap<std::string> label(g);
     208  label[a] = "Node A";
     209  label[b] = "Node B";
     210\endcode
     211
     212For a more complex example, let us create a map that assigns a unique
    180213integer number to each node.
    181214
    182215\code
    183216  ListDigraph::NodeMap<int> id(g);
    184   int cnt=0;
    185   for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)
    186     id[n]=cnt;
    187 \endcode
    188 
    189 You can also give an initial value of the elements as a second parameter.
    190 
    191 For example the following code puts the number of outgoing edges in a map.
    192 
    193 \code
    194   ListDigraph::NodeMap<int> out_deg(g,0);
    195 
    196   for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
     217  int cnt = 0;
     218  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
     219    id[n] = cnt++;
     220\endcode
     221
     222When you create a map, you can also give an initial value of the elements
     223as a second parameter. For example, the following code puts the number
     224of outgoing arcs for each node in a map.
     225
     226\code
     227  ListDigraph::NodeMap<int> out_deg(g, 0);
     228
     229  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
    197230    out_deg[g.source(a)]++;
    198231\endcode
    199232
    200 \warning The initial value will apply to the existing items only. If
     233\warning The initial value will apply to the currently existing items only. If
    201234you add new nodes/arcs to the graph, then the corresponding values in the
    202235map will be initialized with the default constructor of the
Note: See TracChangeset for help on using the changeset viewer.