1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda_bfs_dfs.cc Fri Mar 12 20:11:31 2004 +0000
1.3 @@ -0,0 +1,329 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <vector>
1.7 +#include <string>
1.8 +
1.9 +#include <LEDA/graph.h>
1.10 +
1.11 +#include <list_graph.h>
1.12 +#include <smart_graph.h>
1.13 +#include <bfs_iterator.h>
1.14 +#include <graph_wrapper.h>
1.15 +#include <leda_graph.h>
1.16 +
1.17 +using namespace hugo;
1.18 +using std::cout;
1.19 +using std::endl;
1.20 +using std::string;
1.21 +
1.22 +template <typename Graph, typename NodeNameMap>
1.23 +class EdgeNameMap {
1.24 + Graph& graph;
1.25 + NodeNameMap& node_name_map;
1.26 +public:
1.27 + EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
1.28 + graph(_graph), node_name_map(_node_name_map) { }
1.29 + string get(typename Graph::Edge e) const {
1.30 + return
1.31 + (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
1.32 + }
1.33 +};
1.34 +
1.35 +int main (int, char*[])
1.36 +{
1.37 +
1.38 +
1.39 + //typedef SmartGraph Graph;
1.40 + //typedef ListGraph Graph;
1.41 + typedef LedaGraph<leda::graph> Graph;
1.42 +
1.43 + typedef Graph::Node Node;
1.44 + typedef Graph::NodeIt NodeIt;
1.45 + typedef Graph::Edge Edge;
1.46 + typedef Graph::EdgeIt EdgeIt;
1.47 + typedef Graph::OutEdgeIt OutEdgeIt;
1.48 + typedef Graph::InEdgeIt InEdgeIt;
1.49 +
1.50 +
1.51 + leda::graph g;
1.52 + Graph G(g);
1.53 +
1.54 + Node s=G.addNode();
1.55 + Node v1=G.addNode();
1.56 + Node v2=G.addNode();
1.57 + Node v3=G.addNode();
1.58 + Node v4=G.addNode();
1.59 + Node t=G.addNode();
1.60 +
1.61 + Graph::NodeMap<string> node_name(G);
1.62 + node_name.set(s, "s");
1.63 + node_name.set(v1, "v1");
1.64 + node_name.set(v2, "v2");
1.65 + node_name.set(v3, "v3");
1.66 + node_name.set(v4, "v4");
1.67 + node_name.set(t, "t");
1.68 +
1.69 + G.addEdge(s, v1);
1.70 + G.addEdge(s, v2);
1.71 + G.addEdge(v1, v2);
1.72 + G.addEdge(v2, v1);
1.73 + G.addEdge(v1, v3);
1.74 + G.addEdge(v3, v2);
1.75 + G.addEdge(v2, v4);
1.76 + G.addEdge(v4, v3);
1.77 + G.addEdge(v3, t);
1.78 + G.addEdge(v4, t);
1.79 +
1.80 + cout << " /--> -------------> "<< endl;
1.81 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.82 + cout << " / | | / /-> \\ "<< endl;
1.83 + cout << " / | | / | ^ \\ "<< endl;
1.84 + cout << "s | | / | | \\-> t "<< endl;
1.85 + cout << " \\ | | / | | /-> "<< endl;
1.86 + cout << " \\ | --/ / | | / "<< endl;
1.87 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.88 + cout << " \\--> -------------> "<< endl;
1.89 +
1.90 +// typedef TrivGraphWrapper<const Graph> CGW;
1.91 +// CGW wG(G);
1.92 +
1.93 +// cout << "bfs and dfs demo on the directed graph" << endl;
1.94 +// for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {
1.95 +// cout << n << ": ";
1.96 +// cout << "out edges: ";
1.97 +// for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
1.98 +// cout << e << " ";
1.99 +// cout << "in edges: ";
1.100 +// for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)
1.101 +// cout << e << " ";
1.102 +// cout << endl;
1.103 +// }
1.104 +
1.105 + {
1.106 + typedef TrivGraphWrapper<const Graph> GW;
1.107 + GW wG(G);
1.108 +
1.109 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
1.110 +
1.111 + cout << "bfs and dfs iterator demo on the directed graph" << endl;
1.112 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
1.113 + cout << node_name.get(n) << ": ";
1.114 + cout << "out edges: ";
1.115 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
1.116 + cout << edge_name.get(e) << " ";
1.117 + cout << "in edges: ";
1.118 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
1.119 + cout << edge_name.get(e) << " ";
1.120 + cout << endl;
1.121 + }
1.122 +
1.123 + cout << "bfs from s ..." << endl;
1.124 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
1.125 + bfs.pushAndSetReached(s);
1.126 + while (!bfs.finished()) {
1.127 + //cout << "edge: ";
1.128 + if (wG.valid(bfs)) {
1.129 + cout << edge_name.get(bfs) << /*endl*/", " <<
1.130 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
1.131 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.132 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
1.133 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.134 + ": is not newly reached.");
1.135 + } else {
1.136 + cout << "invalid" << /*endl*/", " <<
1.137 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
1.138 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.139 + /*" bNode: " <<*/
1.140 + "invalid.";
1.141 + }
1.142 + cout << endl;
1.143 + ++bfs;
1.144 + }
1.145 +
1.146 + cout << " /--> -------------> "<< endl;
1.147 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.148 + cout << " / | | / /-> \\ "<< endl;
1.149 + cout << " / | | / | ^ \\ "<< endl;
1.150 + cout << "s | | / | | \\-> t "<< endl;
1.151 + cout << " \\ | | / | | /-> "<< endl;
1.152 + cout << " \\ | --/ / | | / "<< endl;
1.153 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.154 + cout << " \\--> -------------> "<< endl;
1.155 +
1.156 + cout << "dfs from s ..." << endl;
1.157 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
1.158 + dfs.pushAndSetReached(s);
1.159 + while (!dfs.finished()) {
1.160 + ++dfs;
1.161 + //cout << "edge: ";
1.162 + if (wG.valid(dfs)) {
1.163 + cout << edge_name.get(dfs) << /*endl*/", " <<
1.164 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
1.165 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.166 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
1.167 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.168 + ": is not newly reached.");
1.169 + } else {
1.170 + cout << "invalid" << /*endl*/", " <<
1.171 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
1.172 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.173 + /*" bNode: " <<*/
1.174 + "invalid.";
1.175 + }
1.176 + cout << endl;
1.177 + }
1.178 + }
1.179 +
1.180 +
1.181 + {
1.182 + typedef RevGraphWrapper<const Graph> GW;
1.183 + GW wG(G);
1.184 +
1.185 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
1.186 +
1.187 + cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
1.188 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
1.189 + cout << node_name.get(n) << ": ";
1.190 + cout << "out edges: ";
1.191 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
1.192 + cout << edge_name.get(e) << " ";
1.193 + cout << "in edges: ";
1.194 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
1.195 + cout << edge_name.get(e) << " ";
1.196 + cout << endl;
1.197 + }
1.198 +
1.199 + cout << "bfs from t ..." << endl;
1.200 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
1.201 + bfs.pushAndSetReached(t);
1.202 + while (!bfs.finished()) {
1.203 + //cout << "edge: ";
1.204 + if (wG.valid(bfs)) {
1.205 + cout << edge_name.get(bfs) << /*endl*/", " <<
1.206 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
1.207 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.208 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
1.209 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.210 + ": is not newly reached.");
1.211 + } else {
1.212 + cout << "invalid" << /*endl*/", " <<
1.213 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
1.214 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.215 + /*" bNode: " <<*/
1.216 + "invalid.";
1.217 + }
1.218 + cout << endl;
1.219 + ++bfs;
1.220 + }
1.221 +
1.222 + cout << " /--> -------------> "<< endl;
1.223 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.224 + cout << " / | | / /-> \\ "<< endl;
1.225 + cout << " / | | / | ^ \\ "<< endl;
1.226 + cout << "s | | / | | \\-> t "<< endl;
1.227 + cout << " \\ | | / | | /-> "<< endl;
1.228 + cout << " \\ | --/ / | | / "<< endl;
1.229 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.230 + cout << " \\--> -------------> "<< endl;
1.231 +
1.232 + cout << "dfs from t ..." << endl;
1.233 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
1.234 + dfs.pushAndSetReached(t);
1.235 + while (!dfs.finished()) {
1.236 + ++dfs;
1.237 + //cout << "edge: ";
1.238 + if (wG.valid(dfs)) {
1.239 + cout << edge_name.get(dfs) << /*endl*/", " <<
1.240 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
1.241 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.242 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
1.243 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.244 + ": is not newly reached.");
1.245 + } else {
1.246 + cout << "invalid" << /*endl*/", " <<
1.247 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
1.248 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.249 + /*" bNode: " <<*/
1.250 + "invalid.";
1.251 + }
1.252 + cout << endl;
1.253 + }
1.254 + }
1.255 +
1.256 + {
1.257 + typedef UndirGraphWrapper<const Graph> GW;
1.258 + GW wG(G);
1.259 +
1.260 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
1.261 +
1.262 + cout << "bfs and dfs iterator demo on the undirected graph" << endl;
1.263 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
1.264 + cout << node_name.get(n) << ": ";
1.265 + cout << "out edges: ";
1.266 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
1.267 + cout << edge_name.get(e) << " ";
1.268 + cout << "in edges: ";
1.269 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
1.270 + cout << edge_name.get(e) << " ";
1.271 + cout << endl;
1.272 + }
1.273 +
1.274 + cout << "bfs from t ..." << endl;
1.275 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
1.276 + bfs.pushAndSetReached(t);
1.277 + while (!bfs.finished()) {
1.278 + //cout << "edge: ";
1.279 + if (wG.valid(GW::OutEdgeIt(bfs))) {
1.280 + cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
1.281 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
1.282 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.283 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
1.284 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.285 + ": is not newly reached.");
1.286 + } else {
1.287 + cout << "invalid" << /*endl*/", " <<
1.288 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
1.289 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.290 + /*" bNode: " <<*/
1.291 + "invalid.";
1.292 + }
1.293 + cout << endl;
1.294 + ++bfs;
1.295 + }
1.296 +
1.297 + cout << " /--> -------------> "<< endl;
1.298 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.299 + cout << " / | | / /-> \\ "<< endl;
1.300 + cout << " / | | / | ^ \\ "<< endl;
1.301 + cout << "s | | / | | \\-> t "<< endl;
1.302 + cout << " \\ | | / | | /-> "<< endl;
1.303 + cout << " \\ | --/ / | | / "<< endl;
1.304 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.305 + cout << " \\--> -------------> "<< endl;
1.306 +
1.307 + cout << "dfs from t ..." << endl;
1.308 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
1.309 + dfs.pushAndSetReached(t);
1.310 + while (!dfs.finished()) {
1.311 + ++dfs;
1.312 + //cout << "edge: ";
1.313 + if (wG.valid(GW::OutEdgeIt(dfs))) {
1.314 + cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
1.315 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
1.316 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.317 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
1.318 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.319 + ": is not newly reached.");
1.320 + } else {
1.321 + cout << "invalid" << /*endl*/", " <<
1.322 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
1.323 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.324 + /*" bNode: " <<*/
1.325 + "invalid.";
1.326 + }
1.327 + cout << endl;
1.328 + }
1.329 + }
1.330 +
1.331 + return 0;
1.332 +}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/leda_graph.h Fri Mar 12 20:11:31 2004 +0000
2.3 @@ -0,0 +1,314 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_LEDA_GRAPH_H
2.6 +#define HUGO_LEDA_GRAPH_H
2.7 +
2.8 +#include <LEDA/graph.h>
2.9 +#include <LEDA/node_array.h>
2.10 +#include <LEDA/edge_array.h>
2.11 +//#include <LEDA/graph_alg.h>
2.12 +//#include <LEDA/dimacs.h>
2.13 +
2.14 +//#if defined(LEDA_NAMESPACE)
2.15 +//using namespace leda;
2.16 +//#endif
2.17 +
2.18 +#include <invalid.h>
2.19 +
2.20 +/// The namespace of HugoLib
2.21 +namespace hugo {
2.22 +
2.23 + // @defgroup empty_graph The LedaGraph class
2.24 + // @{
2.25 +
2.26 + /// An empty graph class.
2.27 +
2.28 + /// This class provides all the common features of a grapf structure,
2.29 + /// however completely without implementations or real data structures
2.30 + /// behind the interface.
2.31 + /// All graph algorithms should compile with this class, but it will not
2.32 + /// run properly, of course.
2.33 + ///
2.34 + /// It can be used for checking the interface compatibility,
2.35 + /// or it can serve as a skeleton of a new graph structure.
2.36 + ///
2.37 + /// Also, you will find here the full documentation of a certain graph
2.38 + /// feature, the documentation of a real graph imlementation
2.39 + /// like @ref ListGraph or
2.40 + /// @ref SmartGraph will just refer to this structure.
2.41 + template<typename Graph>
2.42 + class LedaGraph
2.43 + {
2.44 + Graph* _graph;
2.45 + public:
2.46 +
2.47 + //LedaGraph() { }
2.48 + LedaGraph(Graph& __graph) : _graph(&__graph) { }
2.49 + LedaGraph(const LedaGraph &G) : _graph(G._graph) { }
2.50 +
2.51 + template <typename T> class NodeMap;
2.52 + template <typename T> class EdgeMap;
2.53 +
2.54 + /// The base type of the node iterators.
2.55 + class Node {
2.56 + friend class LedaGraph;
2.57 + //friend class Edge;
2.58 + friend class EdgeIt;
2.59 + friend class InEdgeIt;
2.60 + friend class OutEdgeIt;
2.61 + protected:
2.62 + template <typename T> friend class NodeMap;
2.63 + leda_node _n;
2.64 + Node(leda_node __n) : _n(__n) { }
2.65 + public:
2.66 + /// @warning The default constructor sets the iterator
2.67 + /// to an undefined value.
2.68 + Node() {} //FIXME
2.69 + /// Initialize the iterator to be invalid
2.70 + Node(Invalid) : _n(0) { }
2.71 + //Node(const Node &) {}
2.72 + bool operator==(Node n) const { return _n==n._n; } //FIXME
2.73 + bool operator!=(Node n) const { return _n!=n._n; } //FIXME
2.74 + };
2.75 +
2.76 + /// This iterator goes through each node.
2.77 + class NodeIt : public Node {
2.78 + public:
2.79 + /// @warning The default constructor sets the iterator
2.80 + /// to an undefined value.
2.81 + NodeIt() {} //FIXME
2.82 + /// Initialize the iterator to be invalid
2.83 + NodeIt(Invalid i) : Node(i) {}
2.84 + /// Sets the iterator to the first node of \c G.
2.85 + NodeIt(const LedaGraph &G) : Node(G._graph->first_node()) { }
2.86 + //NodeIt(const NodeIt &) {} //FIXME
2.87 + };
2.88 +
2.89 + /// The base type of the edge iterators.
2.90 + class Edge {
2.91 + friend class LedaGraph;
2.92 + protected:
2.93 + template <typename T> friend class EdgeMap;
2.94 + leda_edge _e;
2.95 + Edge(leda_edge __e) : _e(__e) { }
2.96 + public:
2.97 + /// @warning The default constructor sets the iterator
2.98 + /// to an undefined value.
2.99 + Edge() {} //FIXME
2.100 + /// Initialize the iterator to be invalid
2.101 + Edge(Invalid) : _e(0) {}
2.102 + //Edge(const Edge &) {}
2.103 + bool operator==(Edge e) const { return _e==e._e; } //FIXME
2.104 + bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
2.105 + };
2.106 +
2.107 + /// This iterator goes trought the outgoing edges of a certain graph.
2.108 +
2.109 + class OutEdgeIt : public Edge {
2.110 + public:
2.111 + /// @warning The default constructor sets the iterator
2.112 + /// to an undefined value.
2.113 + OutEdgeIt() {}
2.114 + /// Initialize the iterator to be invalid
2.115 + OutEdgeIt(Invalid i) : Edge(i) {}
2.116 + /// This constructor sets the iterator to first outgoing edge.
2.117 +
2.118 + /// This constructor set the iterator to the first outgoing edge of
2.119 + /// node
2.120 + ///@param n the node
2.121 + ///@param G the graph
2.122 + OutEdgeIt(const LedaGraph & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
2.123 + };
2.124 +
2.125 + class InEdgeIt : public Edge {
2.126 + public:
2.127 + /// @warning The default constructor sets the iterator
2.128 + /// to an undefined value.
2.129 + InEdgeIt() {}
2.130 + /// Initialize the iterator to be invalid
2.131 + InEdgeIt(Invalid i) : Edge(i) {}
2.132 + InEdgeIt(const LedaGraph & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
2.133 + };
2.134 +
2.135 + // class SymEdgeIt : public Edge {};
2.136 + class EdgeIt : public Edge {
2.137 + public:
2.138 + /// @warning The default constructor sets the iterator
2.139 + /// to an undefined value.
2.140 + EdgeIt() {}
2.141 + /// Initialize the iterator to be invalid
2.142 + EdgeIt(Invalid i) : Edge(i) {}
2.143 + EdgeIt(const LedaGraph & G) : Edge(G._graph->first_edge()) { }
2.144 + };
2.145 +
2.146 + /// First node of the graph.
2.147 +
2.148 + /// \post \c i and the return value will be the first node.
2.149 + ///
2.150 + NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
2.151 +
2.152 + /// The first outgoing edge.
2.153 + InEdgeIt &first(InEdgeIt &i, Node n) const {
2.154 + i=InEdgeIt(*this, n);
2.155 + return i;
2.156 + }
2.157 + /// The first incoming edge.
2.158 + OutEdgeIt &first(OutEdgeIt &i, Node n) const {
2.159 + i=OutEdgeIt(*this, n);
2.160 + return i;
2.161 + }
2.162 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
2.163 + /// The first edge of the Graph.
2.164 + EdgeIt &first(EdgeIt &i) const {
2.165 + i=EdgeIt(*this);
2.166 + return i; }
2.167 +
2.168 +// Node getNext(Node) const {}
2.169 +// InEdgeIt getNext(InEdgeIt) const {}
2.170 +// OutEdgeIt getNext(OutEdgeIt) const {}
2.171 +// //SymEdgeIt getNext(SymEdgeIt) const {}
2.172 +// EdgeIt getNext(EdgeIt) const {}
2.173 +
2.174 + /// Go to the next node.
2.175 + NodeIt &next(NodeIt &i) const {
2.176 + i._n=_graph->succ_node(i._n);
2.177 + return i;
2.178 + }
2.179 + /// Go to the next incoming edge.
2.180 + InEdgeIt &next(InEdgeIt &i) const {
2.181 + i._e=_graph->in_succ(i._e);
2.182 + return i;
2.183 + }
2.184 + /// Go to the next outgoing edge.
2.185 + OutEdgeIt &next(OutEdgeIt &i) const {
2.186 + i._e=_graph->adj_succ(i._e);
2.187 + return i;
2.188 + }
2.189 + //SymEdgeIt &next(SymEdgeIt &) const {}
2.190 + /// Go to the next edge.
2.191 + EdgeIt &next(EdgeIt &i) const {
2.192 + i._e=_graph->succ_edge(i._e);
2.193 + return i;
2.194 + }
2.195 +
2.196 + template< typename It >
2.197 + It first() const {
2.198 + It e;
2.199 + first(e);
2.200 + return e;
2.201 + }
2.202 +
2.203 + template< typename It >
2.204 + It first(Node v) const {
2.205 + It e;
2.206 + first(e, v);
2.207 + return e;
2.208 + }
2.209 +
2.210 + ///Gives back the head node of an edge.
2.211 + Node head(Edge e) const {
2.212 + return Node(_graph->target(e._e));
2.213 + }
2.214 + ///Gives back the tail node of an edge.
2.215 + Node tail(Edge e) const {
2.216 + return Node(_graph->source(e._e));
2.217 + }
2.218 +
2.219 + Node aNode(InEdgeIt e) const { return head(e); }
2.220 + Node aNode(OutEdgeIt e) const { return tail(e); }
2.221 + // Node aNode(SymEdgeIt) const {}
2.222 +
2.223 + Node bNode(InEdgeIt e) const { return tail(e); }
2.224 + Node bNode(OutEdgeIt e) const { return head(e); }
2.225 + // Node bNode(SymEdgeIt) const {}
2.226 +
2.227 + /// Checks if a node iterator is valid
2.228 + bool valid(Node n) const { return n._n; }
2.229 + /// Checks if an edge iterator is valid
2.230 + bool valid(Edge e) const { return e._e; }
2.231 +
2.232 + ///Gives back the \e id of a node.
2.233 + int id(Node n) const { return n._n->id(); }
2.234 + ///Gives back the \e id of an edge.
2.235 + int id(Edge e) const { return e._e->id(); }
2.236 +
2.237 + //void setInvalid(Node &) const {};
2.238 + //void setInvalid(Edge &) const {};
2.239 +
2.240 + Node addNode() const { return Node(_graph->new_node()); }
2.241 + Edge addEdge(Node tail, Node head) const {
2.242 + return Edge(_graph->new_edge(tail._n, head._n));
2.243 + }
2.244 +
2.245 + void erase(Node n) const { _graph->del_node(n._n); }
2.246 + void erase(Edge e) const { _graph->del_edge(e._e); }
2.247 +
2.248 + void clear() const { _graph->clear(); }
2.249 +
2.250 + int nodeNum() const { return _graph->number_of_nodes(); }
2.251 + int edgeNum() const { return _graph->number_of_edges(); }
2.252 +
2.253 + ///Read/write map from the nodes to type \c T.
2.254 + template<typename T> class NodeMap
2.255 + {
2.256 + leda_node_map<T> leda_stuff;
2.257 + public:
2.258 + typedef T ValueType;
2.259 + typedef Node KeyType;
2.260 +
2.261 + NodeMap(const LedaGraph &G) : leda_stuff(*(G._graph)) {}
2.262 + NodeMap(const LedaGraph &G, T t) : leda_stuff(*(G._graph), t) {}
2.263 +
2.264 + void set(Node i, T t) { leda_stuff[i._n]=t; }
2.265 + T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
2.266 + T &operator[](Node i) { return leda_stuff[i._n]; }
2.267 + const T &operator[](Node i) const { return leda_stuff[i._n]; }
2.268 +
2.269 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
2.270 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
2.271 + };
2.272 +
2.273 + ///Read/write map from the edges to type \c T.
2.274 + template<typename T> class EdgeMap
2.275 + {
2.276 + leda_edge_map<T> leda_stuff;
2.277 + public:
2.278 + typedef T ValueType;
2.279 + typedef Edge KeyType;
2.280 +
2.281 + EdgeMap(const LedaGraph &G) : leda_stuff(*(G._graph)) {}
2.282 + EdgeMap(const LedaGraph &G, T t) : leda_stuff(*(G._graph), t) {}
2.283 +
2.284 + void set(Edge i, T t) { leda_stuff[i._e]=t; }
2.285 + T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
2.286 + T &operator[](Edge i) { return leda_stuff[i._e]; }
2.287 + const T &operator[](Edge i) const { return leda_stuff[i._e]; }
2.288 +
2.289 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
2.290 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
2.291 + };
2.292 +
2.293 + };
2.294 +
2.295 + // @}
2.296 +
2.297 +} //namespace hugo
2.298 +
2.299 +
2.300 +
2.301 +// class EmptyBipGraph : public EmptyGraph
2.302 +// {
2.303 +// class ANode {};
2.304 +// class BNode {};
2.305 +
2.306 +// ANode &next(ANode &) {}
2.307 +// BNode &next(BNode &) {}
2.308 +
2.309 +// ANode &getFirst(ANode &) const {}
2.310 +// BNode &getFirst(BNode &) const {}
2.311 +
2.312 +// enum NodeClass { A = 0, B = 1 };
2.313 +// NodeClass getClass(Node n) {}
2.314 +
2.315 +// }
2.316 +
2.317 +#endif // HUGO_LEDA_GRAPH_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/leda_graph_demo.cc Fri Mar 12 20:11:31 2004 +0000
3.3 @@ -0,0 +1,85 @@
3.4 +// -*- c++ -*-
3.5 +#include <iostream>
3.6 +#include <fstream>
3.7 +
3.8 +#include <LEDA/graph.h>
3.9 +#include <leda_graph.h>
3.10 +#include <dimacs.h>
3.11 +#include <time_measure.h>
3.12 +#include <edmonds_karp.h>
3.13 +
3.14 +using namespace hugo;
3.15 +
3.16 +using std::cout;
3.17 +using std::endl;
3.18 +
3.19 +int main() {
3.20 + leda::graph g;
3.21 + typedef LedaGraph<leda::graph> Graph;
3.22 + Graph G(g);
3.23 +// G.addNode();
3.24 +// G.addNode();
3.25 +// std::cout << G.nodeNum() << std::endl;
3.26 +
3.27 + typedef Graph::Node Node;
3.28 + typedef Graph::NodeIt NodeIt;
3.29 + typedef Graph::Edge Edge;
3.30 + typedef Graph::EdgeIt EdgeIt;
3.31 + typedef Graph::OutEdgeIt OutEdgeIt;
3.32 + typedef Graph::InEdgeIt InEdgeIt;
3.33 +
3.34 + Node s, t;
3.35 + Graph::EdgeMap<int> cap(G);
3.36 + readDimacsMaxFlow(std::cin, G, s, t, cap);
3.37 +
3.38 +
3.39 +// cout << "bfs and dfs iterator demo on the directed graph" << endl;
3.40 +// for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
3.41 +// cout << G.id(n) << ": ";
3.42 +// cout << "out edges: ";
3.43 +// for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
3.44 +// cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";
3.45 +// cout << "in edges: ";
3.46 +// for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
3.47 +// cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";
3.48 +// cout << endl;
3.49 +// }
3.50 +
3.51 +// int i=0;
3.52 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cap.set(e, i); i+=3; }
3.53 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cout << cap.get(e) << " "; }
3.54 +// cout << endl;
3.55 +
3.56 + {
3.57 + //std::cout << "SmartGraph..." << std::endl;
3.58 + std::cout << "on-the-fly edmonds karp demo on wrapped leda graph..." << std::endl;
3.59 + Graph::EdgeMap<int> flow(G); //0 flow
3.60 +
3.61 +
3.62 + Timer ts;
3.63 + ts.reset();
3.64 +
3.65 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.66 + //max_flow_test.augmentWithBlockingFlow<Graph>();
3.67 + int i=0;
3.68 + while (max_flow_test.augmentOnShortestPath()) {
3.69 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.70 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.71 +// }
3.72 +// std::cout<<std::endl;
3.73 + ++i;
3.74 + }
3.75 +
3.76 +// std::cout << "maximum flow: "<< std::endl;
3.77 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
3.78 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.79 +// }
3.80 +// std::cout<<std::endl;
3.81 + std::cout << "elapsed time: " << ts << std::endl;
3.82 + std::cout << "number of augmentation phases: " << i << std::endl;
3.83 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.84 + }
3.85 +
3.86 +
3.87 + return 0;
3.88 +}