COIN-OR::LEMON - Graph Library

Changeset 37:c8be1109221b in lemon-tutorial


Ignore:
Timestamp:
02/20/10 21:54:52 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
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.