Changeset 46:58557724a139 in lemon-tutorial
- Timestamp:
- 02/22/10 00:46:59 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 5 added
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
graphs.dox
r38 r46 24 24 efficient graph structures. Diverse applications require the 25 25 usage of different physical graph storages. 26 In \ref sec_basics, we have introduced a general digraph structure, 27 \ref ListDigraph. Apart from this class, LEMONprovides several26 Until now, we used two general graph structures, \ref ListDigraph 27 and \ref ListGraph. Apart from these types, LEMON also provides several 28 28 other classes for handling directed and undirected graphs to meet the 29 29 diverging requirements of the possible users. In order to save on running … … 62 62 63 63 64 [SEC]sec_digraph_types[SEC] Di graph Structures64 [SEC]sec_digraph_types[SEC] Directed Graph Structures 65 65 66 66 The already used \ref ListDigraph class is the most versatile directed … … 91 91 92 92 93 [SEC]sec_ undir_graphs[SEC] Undirected Graphs93 [SEC]sec_graph_types[SEC] Undirected Graph Structures 94 94 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.95 The general undirected graph classes, \ref ListGraph and \ref SmartGraph 96 have similar implementations as their directed variants. 97 Therefore, \ref SmartDigraph is more efficient, but \ref ListGraph provides 98 more functionality. 99 99 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". 100 In addition to these general structures, LEMON also provides special purpose 101 undirected graph types for handling \ref FullGraph "full graphs", 102 \ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs". 210 103 They all static structures, i.e. they do not allow distinct item additions 211 104 or deletions, the graph has to be built at once. -
toc.txt
r39 r46 8 8 ** sec_digraph_maps 9 9 ** 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 15 27 * sec_graph_structures 16 28 ** sec_graph_concepts 17 29 ** 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 24 31 * sec_graph_adaptors 25 32 ** sec_reverse_digraph … … 30 37 * sec_tools 31 38 ** sec_aux_structures 32 **_sec_time_count33 **_sec_random34 39 ** sec_graph_to_eps 35 **_sec_glemon 40 ** sec_time_count 41 ** sec_random 42 ** sec_arg_parser 43 * sec_glemon 36 44 * sec_license -
tools.dox
r45 r46 68 68 \image html graph_to_eps.png 69 69 70 71 [SEC]sec_time_count[SEC] Time Measuring and Counting 72 73 See \ref timecount. 74 75 76 [SEC]sec_random[SEC] Random Number Generation 77 78 See \ref Random. 79 80 81 [SEC]sec_arg_parser[SEC] Argument Parser 82 83 See \ref ArgParser. 84 70 85 [TRAILER] 71 86 */
Note: See TracChangeset
for help on using the changeset viewer.