Changeset 46:58557724a139 in lemontutorial for graphs.dox
 Timestamp:
 02/22/10 00:46:59 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 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.
Note: See TracChangeset
for help on using the changeset viewer.