1.1 --- a/src/work/marci/leda_bfs_dfs.cc Tue Mar 16 13:06:06 2004 +0000
1.2 +++ b/src/work/marci/leda_bfs_dfs.cc Tue Mar 16 15:27:20 2004 +0000
1.3 @@ -9,7 +9,7 @@
1.4 #include <smart_graph.h>
1.5 #include <bfs_iterator.h>
1.6 #include <graph_wrapper.h>
1.7 -#include <leda_graph.h>
1.8 +#include <leda_graph_wrapper.h>
1.9
1.10 using namespace hugo;
1.11 using std::cout;
1.12 @@ -35,7 +35,7 @@
1.13
1.14 //typedef SmartGraph Graph;
1.15 //typedef ListGraph Graph;
1.16 - typedef LedaGraph<leda::graph> Graph;
1.17 + typedef LedaGraphWrapper<leda::graph> Graph;
1.18
1.19 typedef Graph::Node Node;
1.20 typedef Graph::NodeIt NodeIt;
2.1 --- a/src/work/marci/leda_graph_demo.cc Tue Mar 16 13:06:06 2004 +0000
2.2 +++ b/src/work/marci/leda_graph_demo.cc Tue Mar 16 15:27:20 2004 +0000
2.3 @@ -3,7 +3,7 @@
2.4 #include <fstream>
2.5
2.6 #include <LEDA/graph.h>
2.7 -#include <leda_graph.h>
2.8 +#include <leda_graph_wrapper.h>
2.9 #include <dimacs.h>
2.10 #include <time_measure.h>
2.11 #include <edmonds_karp.h>
2.12 @@ -15,7 +15,7 @@
2.13
2.14 int main() {
2.15 leda::graph g;
2.16 - typedef LedaGraph<leda::graph> Graph;
2.17 + typedef LedaGraphWrapper<leda::graph> Graph;
2.18 Graph G(g);
2.19 // G.addNode();
2.20 // G.addNode();
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/leda_graph_wrapper.h Tue Mar 16 15:27:20 2004 +0000
3.3 @@ -0,0 +1,316 @@
3.4 +// -*- c++ -*-
3.5 +#ifndef HUGO_LEDA_GRAPH_WRAPPER_H
3.6 +#define HUGO_LEDA_GRAPH_WRAPPER_H
3.7 +
3.8 +#include <LEDA/graph.h>
3.9 +#include <LEDA/node_array.h>
3.10 +#include <LEDA/edge_array.h>
3.11 +#include <LEDA/node_map.h>
3.12 +#include <LEDA/edge_map.h>
3.13 +//#include <LEDA/graph_alg.h>
3.14 +//#include <LEDA/dimacs.h>
3.15 +
3.16 +//#if defined(LEDA_NAMESPACE)
3.17 +//using namespace leda;
3.18 +//#endif
3.19 +
3.20 +#include <invalid.h>
3.21 +
3.22 +/// The namespace of HugoLib
3.23 +namespace hugo {
3.24 +
3.25 + // @defgroup empty_graph The LedaGraphWrapper class
3.26 + // @{
3.27 +
3.28 + /// An empty graph class.
3.29 +
3.30 + /// This class provides all the common features of a grapf structure,
3.31 + /// however completely without implementations or real data structures
3.32 + /// behind the interface.
3.33 + /// All graph algorithms should compile with this class, but it will not
3.34 + /// run properly, of course.
3.35 + ///
3.36 + /// It can be used for checking the interface compatibility,
3.37 + /// or it can serve as a skeleton of a new graph structure.
3.38 + ///
3.39 + /// Also, you will find here the full documentation of a certain graph
3.40 + /// feature, the documentation of a real graph imlementation
3.41 + /// like @ref ListGraph or
3.42 + /// @ref SmartGraph will just refer to this structure.
3.43 + template<typename Graph>
3.44 + class LedaGraphWrapper
3.45 + {
3.46 + Graph* _graph;
3.47 + public:
3.48 +
3.49 + //LedaGraphWrapper() { }
3.50 + LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
3.51 + LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
3.52 +
3.53 + template <typename T> class NodeMap;
3.54 + template <typename T> class EdgeMap;
3.55 +
3.56 + /// The base type of the node iterators.
3.57 + class Node {
3.58 + friend class LedaGraphWrapper;
3.59 + //friend class Edge;
3.60 + friend class EdgeIt;
3.61 + friend class InEdgeIt;
3.62 + friend class OutEdgeIt;
3.63 + protected:
3.64 + template <typename T> friend class NodeMap;
3.65 + leda_node _n;
3.66 + Node(leda_node __n) : _n(__n) { }
3.67 + public:
3.68 + /// @warning The default constructor sets the iterator
3.69 + /// to an undefined value.
3.70 + Node() {} //FIXME
3.71 + /// Initialize the iterator to be invalid
3.72 + Node(Invalid) : _n(0) { }
3.73 + //Node(const Node &) {}
3.74 + bool operator==(Node n) const { return _n==n._n; } //FIXME
3.75 + bool operator!=(Node n) const { return _n!=n._n; } //FIXME
3.76 + };
3.77 +
3.78 + /// This iterator goes through each node.
3.79 + class NodeIt : public Node {
3.80 + public:
3.81 + /// @warning The default constructor sets the iterator
3.82 + /// to an undefined value.
3.83 + NodeIt() {} //FIXME
3.84 + /// Initialize the iterator to be invalid
3.85 + NodeIt(Invalid i) : Node(i) {}
3.86 + /// Sets the iterator to the first node of \c G.
3.87 + NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
3.88 + //NodeIt(const NodeIt &) {} //FIXME
3.89 + };
3.90 +
3.91 + /// The base type of the edge iterators.
3.92 + class Edge {
3.93 + friend class LedaGraphWrapper;
3.94 + protected:
3.95 + template <typename T> friend class EdgeMap;
3.96 + leda_edge _e;
3.97 + Edge(leda_edge __e) : _e(__e) { }
3.98 + public:
3.99 + /// @warning The default constructor sets the iterator
3.100 + /// to an undefined value.
3.101 + Edge() {} //FIXME
3.102 + /// Initialize the iterator to be invalid
3.103 + Edge(Invalid) : _e(0) {}
3.104 + //Edge(const Edge &) {}
3.105 + bool operator==(Edge e) const { return _e==e._e; } //FIXME
3.106 + bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
3.107 + };
3.108 +
3.109 + /// This iterator goes trought the outgoing edges of a certain graph.
3.110 +
3.111 + class OutEdgeIt : public Edge {
3.112 + public:
3.113 + /// @warning The default constructor sets the iterator
3.114 + /// to an undefined value.
3.115 + OutEdgeIt() {}
3.116 + /// Initialize the iterator to be invalid
3.117 + OutEdgeIt(Invalid i) : Edge(i) {}
3.118 + /// This constructor sets the iterator to first outgoing edge.
3.119 +
3.120 + /// This constructor set the iterator to the first outgoing edge of
3.121 + /// node
3.122 + ///@param n the node
3.123 + ///@param G the graph
3.124 + OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
3.125 + };
3.126 +
3.127 + class InEdgeIt : public Edge {
3.128 + public:
3.129 + /// @warning The default constructor sets the iterator
3.130 + /// to an undefined value.
3.131 + InEdgeIt() {}
3.132 + /// Initialize the iterator to be invalid
3.133 + InEdgeIt(Invalid i) : Edge(i) {}
3.134 + InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
3.135 + };
3.136 +
3.137 + // class SymEdgeIt : public Edge {};
3.138 + class EdgeIt : public Edge {
3.139 + public:
3.140 + /// @warning The default constructor sets the iterator
3.141 + /// to an undefined value.
3.142 + EdgeIt() {}
3.143 + /// Initialize the iterator to be invalid
3.144 + EdgeIt(Invalid i) : Edge(i) {}
3.145 + EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
3.146 + };
3.147 +
3.148 + /// First node of the graph.
3.149 +
3.150 + /// \post \c i and the return value will be the first node.
3.151 + ///
3.152 + NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
3.153 +
3.154 + /// The first outgoing edge.
3.155 + InEdgeIt &first(InEdgeIt &i, Node n) const {
3.156 + i=InEdgeIt(*this, n);
3.157 + return i;
3.158 + }
3.159 + /// The first incoming edge.
3.160 + OutEdgeIt &first(OutEdgeIt &i, Node n) const {
3.161 + i=OutEdgeIt(*this, n);
3.162 + return i;
3.163 + }
3.164 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
3.165 + /// The first edge of the Graph.
3.166 + EdgeIt &first(EdgeIt &i) const {
3.167 + i=EdgeIt(*this);
3.168 + return i; }
3.169 +
3.170 +// Node getNext(Node) const {}
3.171 +// InEdgeIt getNext(InEdgeIt) const {}
3.172 +// OutEdgeIt getNext(OutEdgeIt) const {}
3.173 +// //SymEdgeIt getNext(SymEdgeIt) const {}
3.174 +// EdgeIt getNext(EdgeIt) const {}
3.175 +
3.176 + /// Go to the next node.
3.177 + NodeIt &next(NodeIt &i) const {
3.178 + i._n=_graph->succ_node(i._n);
3.179 + return i;
3.180 + }
3.181 + /// Go to the next incoming edge.
3.182 + InEdgeIt &next(InEdgeIt &i) const {
3.183 + i._e=_graph->in_succ(i._e);
3.184 + return i;
3.185 + }
3.186 + /// Go to the next outgoing edge.
3.187 + OutEdgeIt &next(OutEdgeIt &i) const {
3.188 + i._e=_graph->adj_succ(i._e);
3.189 + return i;
3.190 + }
3.191 + //SymEdgeIt &next(SymEdgeIt &) const {}
3.192 + /// Go to the next edge.
3.193 + EdgeIt &next(EdgeIt &i) const {
3.194 + i._e=_graph->succ_edge(i._e);
3.195 + return i;
3.196 + }
3.197 +
3.198 + template< typename It >
3.199 + It first() const {
3.200 + It e;
3.201 + first(e);
3.202 + return e;
3.203 + }
3.204 +
3.205 + template< typename It >
3.206 + It first(Node v) const {
3.207 + It e;
3.208 + first(e, v);
3.209 + return e;
3.210 + }
3.211 +
3.212 + ///Gives back the head node of an edge.
3.213 + Node head(Edge e) const {
3.214 + return Node(_graph->target(e._e));
3.215 + }
3.216 + ///Gives back the tail node of an edge.
3.217 + Node tail(Edge e) const {
3.218 + return Node(_graph->source(e._e));
3.219 + }
3.220 +
3.221 + Node aNode(InEdgeIt e) const { return head(e); }
3.222 + Node aNode(OutEdgeIt e) const { return tail(e); }
3.223 + // Node aNode(SymEdgeIt) const {}
3.224 +
3.225 + Node bNode(InEdgeIt e) const { return tail(e); }
3.226 + Node bNode(OutEdgeIt e) const { return head(e); }
3.227 + // Node bNode(SymEdgeIt) const {}
3.228 +
3.229 + /// Checks if a node iterator is valid
3.230 + bool valid(Node n) const { return n._n; }
3.231 + /// Checks if an edge iterator is valid
3.232 + bool valid(Edge e) const { return e._e; }
3.233 +
3.234 + ///Gives back the \e id of a node.
3.235 + int id(Node n) const { return n._n->id(); }
3.236 + ///Gives back the \e id of an edge.
3.237 + int id(Edge e) const { return e._e->id(); }
3.238 +
3.239 + //void setInvalid(Node &) const {};
3.240 + //void setInvalid(Edge &) const {};
3.241 +
3.242 + Node addNode() const { return Node(_graph->new_node()); }
3.243 + Edge addEdge(Node tail, Node head) const {
3.244 + return Edge(_graph->new_edge(tail._n, head._n));
3.245 + }
3.246 +
3.247 + void erase(Node n) const { _graph->del_node(n._n); }
3.248 + void erase(Edge e) const { _graph->del_edge(e._e); }
3.249 +
3.250 + void clear() const { _graph->clear(); }
3.251 +
3.252 + int nodeNum() const { return _graph->number_of_nodes(); }
3.253 + int edgeNum() const { return _graph->number_of_edges(); }
3.254 +
3.255 + ///Read/write map from the nodes to type \c T.
3.256 + template<typename T> class NodeMap
3.257 + {
3.258 + leda_node_map<T> leda_stuff;
3.259 + public:
3.260 + typedef T ValueType;
3.261 + typedef Node KeyType;
3.262 +
3.263 + NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
3.264 + NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
3.265 +
3.266 + void set(Node i, T t) { leda_stuff[i._n]=t; }
3.267 + T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
3.268 + T &operator[](Node i) { return leda_stuff[i._n]; }
3.269 + const T &operator[](Node i) const { return leda_stuff[i._n]; }
3.270 +
3.271 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
3.272 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
3.273 + };
3.274 +
3.275 + ///Read/write map from the edges to type \c T.
3.276 + template<typename T> class EdgeMap
3.277 + {
3.278 + leda_edge_map<T> leda_stuff;
3.279 + public:
3.280 + typedef T ValueType;
3.281 + typedef Edge KeyType;
3.282 +
3.283 + EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
3.284 + EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
3.285 +
3.286 + void set(Edge i, T t) { leda_stuff[i._e]=t; }
3.287 + T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
3.288 + T &operator[](Edge i) { return leda_stuff[i._e]; }
3.289 + const T &operator[](Edge i) const { return leda_stuff[i._e]; }
3.290 +
3.291 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
3.292 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
3.293 + };
3.294 +
3.295 + };
3.296 +
3.297 + // @}
3.298 +
3.299 +} //namespace hugo
3.300 +
3.301 +
3.302 +
3.303 +// class EmptyBipGraph : public EmptyGraph
3.304 +// {
3.305 +// class ANode {};
3.306 +// class BNode {};
3.307 +
3.308 +// ANode &next(ANode &) {}
3.309 +// BNode &next(BNode &) {}
3.310 +
3.311 +// ANode &getFirst(ANode &) const {}
3.312 +// BNode &getFirst(BNode &) const {}
3.313 +
3.314 +// enum NodeClass { A = 0, B = 1 };
3.315 +// NodeClass getClass(Node n) {}
3.316 +
3.317 +// }
3.318 +
3.319 +#endif // HUGO_LEDA_GRAPH_WRAPPER_H
4.1 --- a/src/work/marci/makefile Tue Mar 16 13:06:06 2004 +0000
4.2 +++ b/src/work/marci/makefile Tue Mar 16 15:27:20 2004 +0000
4.3 @@ -9,7 +9,7 @@
4.4 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
4.5
4.6
4.7 -BINARIES = edmonds_karp_demo preflow_demo_leda lg_vs_sg leda_graph_demo
4.8 +BINARIES = edmonds_karp_demo preflow_demo_leda lg_vs_sg leda_graph_demo leda_bfs_dfs
4.9 #preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar
4.10
4.11 all: $(BINARIES)
4.12 @@ -28,6 +28,12 @@
4.13 leda_graph_demo: leda_graph_demo.o
4.14 $(CXX3) -Wall -O -L$(LEDAROOT) -o leda_graph_demo leda_graph_demo.o -lG -lL -lm
4.15
4.16 +leda_bfs_dfs.o:
4.17 + $(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c leda_bfs_dfs.cc
4.18 +
4.19 +leda_bfs_dfs: leda_bfs_dfs.o
4.20 + $(CXX3) -Wall -O -L$(LEDAROOT) -o leda_bfs_dfs leda_bfs_dfs.o -lG -lL -lm
4.21 +
4.22 edmonds_karp_demo:
4.23 $(CXX3) $(CXXFLAGS) -g -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
4.24 $(CXX3) $(CXXFLAGS) -g -pg -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc