equal
deleted
inserted
replaced
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
36 |
36 |
37 [SEC]sec_graph_concepts[SEC] Graph Concepts |
37 [SEC]sec_graph_concepts[SEC] Graph Concepts |
38 |
38 |
39 In LEMON, there are various graph types, which are rather different, but |
39 In LEMON, there are various graph types, which are rather different, but |
40 they all conform to the corresponding \ref graph_concepts "graph concept", |
40 they all conform to the corresponding \ref graph_concepts "graph concept", |
41 which defines the common part of the graph interfaces. |
41 which defines the common part of the graph interfaces. |
42 The \ref concepts::Digraph "Digraph concept" describes the common interface |
42 The \ref concepts::Digraph "Digraph concept" describes the common interface |
43 of directed graphs (without any sensible implementation), while |
43 of directed graphs (without any sensible implementation), while |
44 the \ref concepts::Graph "Graph concept" describes the undirected graphs. |
44 the \ref concepts::Graph "Graph concept" describes the undirected graphs. |
45 Any generic graph algorithm should only exploit the features of the |
45 Any generic graph algorithm should only exploit the features of the |
46 corresponding graph concept. (It should compile with the |
46 corresponding graph concept. (It should compile with the |
48 but it will not run properly, of course.) |
48 but it will not run properly, of course.) |
49 |
49 |
50 The graph %concepts define the member classes for the iterators and maps |
50 The graph %concepts define the member classes for the iterators and maps |
51 along with some useful basic functions for obtaining the identifiers of |
51 along with some useful basic functions for obtaining the identifiers of |
52 the items, the end nodes of the arcs (or edges) and their iterators, |
52 the items, the end nodes of the arcs (or edges) and their iterators, |
53 etc. |
53 etc. |
54 An actual graph implementation may have various additional functionalities |
54 An actual graph implementation may have various additional functionalities |
55 according to its purpose. |
55 according to its purpose. |
56 |
56 |
57 |
57 |
58 [SEC]sec_digraph_types[SEC] Digraph Structures |
58 [SEC]sec_digraph_types[SEC] Digraph Structures |
64 or arcs. |
64 or arcs. |
65 |
65 |
66 \ref SmartDigraph is another general digraph implementation, which is |
66 \ref SmartDigraph is another general digraph implementation, which is |
67 significantly more efficient (both in terms of space and time), but it |
67 significantly more efficient (both in terms of space and time), but it |
68 provides less functionality. For example, nodes and arcs cannot be |
68 provides less functionality. For example, nodes and arcs cannot be |
69 removed from it. |
69 removed from it. |
70 |
70 |
71 \ref FullDigraph is an efficient implementation of a directed full graph. |
71 \ref FullDigraph is an efficient implementation of a directed full graph. |
72 This structure is completely static, so you can neither add nor delete |
72 This structure is completely static, so you can neither add nor delete |
73 arcs or nodes, and the class needs constant space in memory. |
73 arcs or nodes, and the class needs constant space in memory. |
74 |
74 |
79 \ref ListGraph and \ref SmartGraph are the undirected versions of |
79 \ref ListGraph and \ref SmartGraph are the undirected versions of |
80 \ref ListDigraph and \ref SmartDigraph, respectively. |
80 \ref ListDigraph and \ref SmartDigraph, respectively. |
81 They provide similar features to the digraph structures. |
81 They provide similar features to the digraph structures. |
82 |
82 |
83 The \ref concepts::Graph "undirected graphs" also fulfill the concept of |
83 The \ref concepts::Graph "undirected graphs" also fulfill the concept of |
84 \ref concepts::Digraph "directed graphs", in such a way that each |
84 \ref concepts::Digraph "directed graphs", in such a way that each |
85 undirected \e edge of a graph can also be regarded as two oppositely |
85 undirected \e edge of a graph can also be regarded as two oppositely |
86 directed \e arcs. As a result, all directed graph algorithms automatically |
86 directed \e arcs. As a result, all directed graph algorithms automatically |
87 run on undirected graphs, as well. |
87 run on undirected graphs, as well. |
88 |
88 |
89 Undirected graphs provide an \c Edge type for the \e undirected \e edges |
89 Undirected graphs provide an \c Edge type for the \e undirected \e edges |
96 (there are twice as many arcs as edges) |
96 (there are twice as many arcs as edges) |
97 |
97 |
98 For example, |
98 For example, |
99 \code |
99 \code |
100 ListGraph g; |
100 ListGraph g; |
101 |
101 |
102 ListGraph::Node a = g.addNode(); |
102 ListGraph::Node a = g.addNode(); |
103 ListGraph::Node b = g.addNode(); |
103 ListGraph::Node b = g.addNode(); |
104 ListGraph::Node c = g.addNode(); |
104 ListGraph::Node c = g.addNode(); |
105 |
105 |
106 ListGraph::Edge e = g.addEdge(a,b); |
106 ListGraph::Edge e = g.addEdge(a,b); |
131 \ref concepts::Graph::target() "target()" can be used for arcs. |
131 \ref concepts::Graph::target() "target()" can be used for arcs. |
132 |
132 |
133 \code |
133 \code |
134 std::cout << "Edge " << g.id(e) << " connects node " |
134 std::cout << "Edge " << g.id(e) << " connects node " |
135 << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl; |
135 << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl; |
136 |
136 |
137 std::cout << "Arc " << g.id(a2) << " goes from node " |
137 std::cout << "Arc " << g.id(a2) << " goes from node " |
138 << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl; |
138 << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl; |
139 \endcode |
139 \endcode |
140 |
140 |
141 |
141 |
181 arc_cost[a1] = cost[a1]; |
181 arc_cost[a1] = cost[a1]; |
182 arc_cost[a2] = 2 * cost[a2]; |
182 arc_cost[a2] = 2 * cost[a2]; |
183 // std::cout << arc_cost[e] << std::endl; // this is not valid |
183 // std::cout << arc_cost[e] << std::endl; // this is not valid |
184 std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl; |
184 std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl; |
185 \endcode |
185 \endcode |
186 |
186 |
187 [SEC]sec_special_graphs[SEC] Special Graph Structures |
187 [SEC]sec_special_graphs[SEC] Special Graph Structures |
188 |
188 |
189 In addition to the general undirected classes \ref ListGraph and |
189 In addition to the general undirected classes \ref ListGraph and |
190 \ref SmartGraph, LEMON also provides special purpose graph types for |
190 \ref SmartGraph, LEMON also provides special purpose graph types for |
191 handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and |
191 handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and |