COIN-OR::LEMON - Graph Library

Changeset 46:58557724a139 in lemon-tutorial


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

Add new sekeleton pages and complete the TOC

Files:
5 added
3 edited

Legend:

Unmodified
Added
Removed
  • graphs.dox

    r38 r46  
    2424efficient graph structures. Diverse applications require the
    2525usage of different physical graph storages.
    26 In \ref sec_basics, we have introduced a general digraph structure,
    27 \ref ListDigraph. Apart from this class, LEMON provides several
     26Until now, we used two general graph structures, \ref ListDigraph
     27and \ref ListGraph. Apart from these types, LEMON also provides several
    2828other classes for handling directed and undirected graphs to meet the
    2929diverging requirements of the possible users. In order to save on running
     
    6262
    6363
    64 [SEC]sec_digraph_types[SEC] Digraph Structures
     64[SEC]sec_digraph_types[SEC] Directed Graph Structures
    6565
    6666The already used \ref ListDigraph class is the most versatile directed
     
    9191
    9292
    93 [SEC]sec_undir_graphs[SEC] Undirected Graphs
     93[SEC]sec_graph_types[SEC] Undirected Graph Structures
    9494
    95 LEMON also provides undirected graph structures. For example,
    96 \ref ListGraph and \ref SmartGraph are the undirected versions of
    97 \ref ListDigraph and \ref SmartDigraph, respectively.
    98 They provide similar features to the digraph structures.
     95The general undirected graph classes, \ref ListGraph and \ref SmartGraph
     96have similar implementations as their directed variants.
     97Therefore, \ref SmartDigraph is more efficient, but \ref ListGraph provides
     98more functionality.
    9999
    100 The \ref concepts::Graph "undirected graphs" also fulfill the concept of
    101 \ref concepts::Digraph "directed graphs", in such a way that each
    102 undirected \e edge of a graph can also be regarded as two oppositely
    103 directed \e arcs. As a result, all directed graph algorithms automatically
    104 run on undirected graphs, as well.
    105 
    106 Undirected graphs provide an \c Edge type for the \e undirected \e edges
    107 and an \c Arc type for the \e directed \e arcs. The \c Arc type is
    108 convertible to \c Edge (or inherited from it), thus the corresponding
    109 edge can always be obtained from an arc.
    110 
    111 Only nodes and edges can be added to or removed from an undirected
    112 graph and the corresponding arcs are added or removed automatically
    113 (there are twice as many arcs as edges)
    114 
    115 For example,
    116 \code
    117   ListGraph g;
    118 
    119   ListGraph::Node a = g.addNode();
    120   ListGraph::Node b = g.addNode();
    121   ListGraph::Node c = g.addNode();
    122 
    123   ListGraph::Edge e = g.addEdge(a,b);
    124   g.addEdge(b,c);
    125   g.addEdge(c,a);
    126 \endcode
    127 
    128 Each edge has an inherent orientation, thus it can be defined whether an
    129 arc is forward or backward oriented in an undirected graph with respect
    130 to this default oriantation of the represented edge.
    131 The direction of an arc can be obtained and set using the functions
    132 \ref concepts::Graph::direction() "direction()" and
    133 \ref concepts::Graph::direct() "direct()", respectively.
    134 
    135 For example,
    136 \code
    137   ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
    138   ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
    139 
    140   if (a2 == g.oppositeArc(a1))
    141     std::cout << "a2 is the opposite of a1" << std::endl;
    142 \endcode
    143 
    144 The end nodes of an edge can be obtained using the functions
    145 \ref concepts::Graph::source() "u()" and
    146 \ref concepts::Graph::target() "v()", while the
    147 \ref concepts::Graph::source() "source()" and
    148 \ref concepts::Graph::target() "target()" can be used for arcs.
    149 
    150 \code
    151   std::cout << "Edge " << g.id(e) << " connects node "
    152     << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
    153 
    154   std::cout << "Arc " << g.id(a2) << " goes from node "
    155     << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
    156 \endcode
    157 
    158 
    159 Similarly to the digraphs, the undirected graphs also provide iterators
    160 \ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
    161 \ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
    162 "InArcIt", which can be used the same way.
    163 However, they also have iterator classes for edges.
    164 \ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
    165 \ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
    166 certain node.
    167 
    168 For example, the degree of each node can be computed and stored in a node map
    169 like this:
    170 
    171 \code
    172   ListGraph::NodeMap<int> deg(g, 0);
    173   for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
    174     for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
    175       deg[n]++;
    176     }
    177   }
    178 \endcode
    179 
    180 In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
    181 and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
    182 but with opposite direction. They are convertible to both \c Arc and
    183 \c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
    184 on these edges, but it is not convertible to \c Arc, only to \c Edge.
    185 
    186 Apart from the node and arc maps, an undirected graph also defines
    187 a template member class for constructing edge maps. These maps can be
    188 used in conjunction with both edges and arcs.
    189 
    190 For example,
    191 \code
    192   ListGraph::EdgeMap cost(g);
    193   cost[e] = 10;
    194   std::cout << cost[e] << std::endl;
    195   std::cout << cost[a1] << ", " << cost[a2] << std::endl;
    196 
    197   ListGraph::ArcMap arc_cost(g);
    198   arc_cost[a1] = cost[a1];
    199   arc_cost[a2] = 2 * cost[a2];
    200   // std::cout << arc_cost[e] << std::endl;   // this is not valid
    201   std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
    202 \endcode
    203 
    204 [SEC]sec_special_graphs[SEC] Special Graph Structures
    205 
    206 In addition to the general undirected classes \ref ListGraph and
    207 \ref SmartGraph, LEMON also provides special purpose graph types for
    208 handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
    209 \ref HypercubeGraph "hypercube graphs".
     100In addition to these general structures, LEMON also provides special purpose
     101undirected graph types for handling \ref FullGraph "full graphs",
     102\ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".
    210103They all static structures, i.e. they do not allow distinct item additions
    211104or deletions, the graph has to be built at once.
  • toc.txt

    r39 r46  
    88** sec_digraph_maps
    99** sec_naming_conv
    10 *_sec_algorithms
    11 **_sec_alg_graph_search
    12 **_sec_alg_shortest_paths
    13 **_sec_alg_spanning_tree
    14 **_sec_alg_max_flow
     10* sec_algorithms
     11** sec_graph_search
     12** sec_shortest_paths
     13** sec_max_flow
     14* sec_undir_graphs
     15** sec_undir_graph_use
     16** sec_undir_graph_algs
     17* sec_graph_utilities
     18** sec_util_item_count
     19** sec_util_graph_copy
     20** sec_util_typedefs
     21** sec_util_graph_maps
     22* sec_maps
     23** sec_map_concepts
     24** sec_own_maps
     25** sec_map_adaptors
     26** sec_algs_with_maps
    1527* sec_graph_structures
    1628** sec_graph_concepts
    1729** sec_digraph_types
    18 ** sec_undir_graphs
    19 ** sec_special_graphs
    20 *_sec_maps
    21 **_sec_map_concepts
    22 **_own_maps
    23 **_algs_with_maps
     30** sec_graph_types
    2431* sec_graph_adaptors
    2532** sec_reverse_digraph
     
    3037* sec_tools
    3138** sec_aux_structures
    32 **_sec_time_count
    33 **_sec_random
    3439** sec_graph_to_eps
    35 **_sec_glemon
     40** sec_time_count
     41** sec_random
     42** sec_arg_parser
     43* sec_glemon
    3644* sec_license
  • tools.dox

    r45 r46  
    6868\image html graph_to_eps.png
    6969
     70
     71[SEC]sec_time_count[SEC] Time Measuring and Counting
     72
     73See \ref timecount.
     74
     75
     76[SEC]sec_random[SEC] Random Number Generation
     77
     78See \ref Random.
     79
     80
     81[SEC]sec_arg_parser[SEC] Argument Parser
     82
     83See \ref ArgParser.
     84
    7085[TRAILER]
    7186*/
Note: See TracChangeset for help on using the changeset viewer.