1.1 --- a/src/work/list_graph.h Mon Apr 26 09:21:27 2004 +0000
1.2 +++ b/src/work/list_graph.h Mon Apr 26 09:54:24 2004 +0000
1.3 @@ -369,10 +369,17 @@
1.4 /* stream operations, for testing purpose */
1.5
1.6 friend std::ostream& operator<<(std::ostream& os, const Node& i) {
1.7 - os << i.node->id; return os;
1.8 + if (i.valid())
1.9 + os << i.node->id;
1.10 + else
1.11 + os << "invalid";
1.12 + return os;
1.13 }
1.14 friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
1.15 - os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
1.16 + if (i.valid())
1.17 + os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
1.18 + else
1.19 + os << "invalid";
1.20 return os;
1.21 }
1.22
2.1 --- a/src/work/makefile Mon Apr 26 09:21:27 2004 +0000
2.2 +++ b/src/work/makefile Mon Apr 26 09:54:24 2004 +0000
2.3 @@ -1,12 +1,12 @@
2.4 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
2.5 -CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.6 +CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.7
2.8 BINARIES ?= bin_heap_demo
2.9
2.10 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
2.11 # ismert rendszeren :-) (Misi)
2.12 -#CXX := $(shell type -p g++-3.4 || type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.13 -CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.14 +CXX := $(shell type -p g++-3.4 || type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.15 +#CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.16 CC := $(CXX)
2.17
2.18
3.1 --- a/src/work/marci/bfs_iterator.h Mon Apr 26 09:21:27 2004 +0000
3.2 +++ b/src/work/marci/bfs_iterator.h Mon Apr 26 09:54:24 2004 +0000
3.3 @@ -28,6 +28,9 @@
3.4 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
3.5 own_reached_map(true) { }
3.6 ~BfsIterator() { if (own_reached_map) delete &reached; }
3.7 + //s is marcked reached.
3.8 + //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
3.9 + //is the queue is not empty, then is it pushed.
3.10 void pushAndSetReached(Node s) {
3.11 reached.set(s, true);
3.12 if (bfs_queue.empty()) {
3.13 @@ -80,7 +83,7 @@
3.14 return *this;
3.15 }
3.16 bool finished() const { return bfs_queue.empty(); }
3.17 - operator OutEdgeIt () const { return actual_edge; }
3.18 + operator OutEdgeIt() const { return actual_edge; }
3.19 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.20 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
3.21 Node aNode() const { return bfs_queue.front(); }
3.22 @@ -89,6 +92,51 @@
3.23 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
3.24 };
3.25
3.26 + /// Bfs searches from s for the nodes wich are not marked in
3.27 + /// reachedmap
3.28 + template <typename Graph,
3.29 + typename ReachedMap=typename Graph::template NodeMap<bool>,
3.30 + typename PredMap
3.31 + =typename Graph::template NodeMap<typename Graph::Edge>,
3.32 + typename DistMap=typename Graph::template NodeMap<int> >
3.33 + class Bfs : public BfsIterator<Graph, ReachedMap> {
3.34 + typedef BfsIterator<Graph, ReachedMap> Parent;
3.35 + protected:
3.36 + typedef typename Parent::Node Node;
3.37 + PredMap& pred;
3.38 + DistMap& dist;
3.39 + public:
3.40 + Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
3.41 + //s is marked to be reached and pushed in the bfs queue.
3.42 + //if the queue is empty, then the first out-edge is processed
3.43 + //If s was not marked previously, then
3.44 + //in addition its pred is set to be INVALID, and dist to 0.
3.45 + //if s was marked previuosly, then it is simply pushed.
3.46 + void push(Node s) {
3.47 + if (this->reached[s]) {
3.48 + Parent::pushAndSetReached(s);
3.49 + } else {
3.50 + Parent::pushAndSetReached(s);
3.51 + pred.set(s, INVALID);
3.52 + dist.set(s, 0);
3.53 + }
3.54 + }
3.55 + void run(Node s) {
3.56 + push(s);
3.57 + while (!this->finished()) this->operator++();
3.58 + }
3.59 + Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
3.60 + Parent::operator++();
3.61 + if (this->graph->valid(actual_edge) && this->b_node_newly_reached) {
3.62 + pred.set(s, actual_edge);
3.63 + dist.set(s, dist[this->aNode()]);
3.64 + }
3.65 + return *this;
3.66 + }
3.67 + const PredMap& getPredMap() const { return pred; }
3.68 + const DistMap& getDistMap() const { return dist; }
3.69 + };
3.70 +
3.71 template <typename Graph, /*typename OutEdgeIt,*/
3.72 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.73 class DfsIterator {
3.74 @@ -142,7 +190,7 @@
3.75 return *this;
3.76 }
3.77 bool finished() const { return dfs_stack.empty(); }
3.78 - operator OutEdgeIt () const { return actual_edge; }
3.79 + operator OutEdgeIt() const { return actual_edge; }
3.80 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.81 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
3.82 Node aNode() const { return actual_node; /*FIXME*/}
4.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Mon Apr 26 09:21:27 2004 +0000
4.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Mon Apr 26 09:54:24 2004 +0000
4.3 @@ -24,22 +24,62 @@
4.4 typedef Graph::OutEdgeIt OutEdgeIt;
4.5
4.6 Graph g;
4.7 - //Node s, t;
4.8 - //Graph::EdgeMap<int> cap(g);
4.9 - //readDimacsMaxFlow(std::cin, g, s, t, cap);
4.10 - std::vector<Graph::Node> s_nodes;
4.11 - std::vector<Graph::Node> t_nodes;
4.12 - for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
4.13 - for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
4.14 - g.addEdge(s_nodes[0], t_nodes[2]);
4.15 - g.addEdge(t_nodes[1], s_nodes[2]);
4.16 +// std::vector<Graph::Node> s_nodes;
4.17 +// std::vector<Graph::Node> t_nodes;
4.18 +// for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
4.19 +// for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
4.20 +// g.addEdge(s_nodes[0], t_nodes[2]);
4.21 +// g.addEdge(t_nodes[1], s_nodes[2]);
4.22 +// g.addEdge(s_nodes[0], t_nodes[1]);
4.23 +
4.24 +// Graph::NodeMap<int> ref_map(g, -1);
4.25 +// IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
4.26 +// for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
4.27 +// for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
4.28 +
4.29 + std::vector<Graph::Node> nodes;
4.30 + for (int i=0; i<3; ++i) nodes.push_back(g.addNode());
4.31 + for (int i=3; i<6; ++i) nodes.push_back(g.addNode());
4.32 + g.addEdge(nodes[0], nodes[3+2]);
4.33 + g.addEdge(nodes[3+1], nodes[2]);
4.34 + g.addEdge(nodes[0], nodes[3+1]);
4.35
4.36 Graph::NodeMap<int> ref_map(g, -1);
4.37 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
4.38 - for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
4.39 - for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
4.40 + for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false);
4.41 + for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
4.42 +
4.43 + Graph::Node u;
4.44 + std::cout << "These nodes will be in S:\n";
4.45 + //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
4.46 + //irni 1etlen FOR_EACH-csel.
4.47 + for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
4.48 + std::cout << u << " ";
4.49 + std::cout << "\n";
4.50 + std::cout << "These nodes will be in T:\n";
4.51 + for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
4.52 + std::cout << u << " ";
4.53 + std::cout << "\n";
4.54 +
4.55 typedef BipartiteGraphWrapper<Graph> BGW;
4.56 BGW bgw(g, bipartite_map);
4.57 +
4.58 + std::cout << "Nodes by NodeIt:\n";
4.59 + FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
4.60 + std::cout << n << " ";
4.61 + }
4.62 + std::cout << "\n";
4.63 + std::cout << "Nodes in S by ClassNodeIt:\n";
4.64 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
4.65 + std::cout << n << " ";
4.66 + }
4.67 + std::cout << "\n";
4.68 + std::cout << "Nodes in T by ClassNodeIt:\n";
4.69 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
4.70 + std::cout << n << " ";
4.71 + }
4.72 + std::cout << "\n";
4.73 + std::cout << "Edges of the bipartite graph:\n";
4.74 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
4.75 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
4.76 }
4.77 @@ -58,21 +98,43 @@
4.78 Graph::Node s;
4.79 s=g.first(si);
4.80 bfs.pushAndSetReached(BGW::Node(s));
4.81 - while (!bfs.finished()) ++bfs;
4.82 + while (!bfs.finished()) { ++bfs; }
4.83
4.84 - BGW::EdgeMap<bool> cap(bgw);
4.85 - BGW::EdgeMap<bool> flow1(bgw);
4.86 + FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
4.87 + std::cout << "out-edges of " << n << ":\n";
4.88 + FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
4.89 + std::cout << " " << e << "\n";
4.90 + std::cout << " aNode: " << stgw.aNode(e) << "\n";
4.91 + std::cout << " bNode: " << stgw.bNode(e) << "\n";
4.92 + }
4.93 + std::cout << "in-edges of " << n << ":\n";
4.94 + FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
4.95 + std::cout << " " << e << "\n";
4.96 + std::cout << " aNode: " << stgw.aNode(e) << "\n";
4.97 + std::cout << " bNode: " << stgw.bNode(e) << "\n";
4.98 + }
4.99 + }
4.100 + std::cout << "Edges of the stGraphWrapper:\n";
4.101 + FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
4.102 + std::cout << " " << n << "\n";
4.103 + }
4.104
4.105 - typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> >
4.106 - RBGW;
4.107 - RBGW rbgw(bgw, cap, flow1);
4.108 - RBGW::NodeMap<int> u(rbgw);
4.109 + stGW::NodeMap<bool> b(stgw);
4.110 + FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
4.111 + std::cout << n << ": " << b[n] <<"\n";
4.112 + }
4.113 +
4.114 + std::cout << "Bfs from s: \n";
4.115 + BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
4.116 + bfs_stgw.pushAndSetReached(stgw.S_NODE);
4.117 + while (!bfs_stgw.finished()) {
4.118 + std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
4.119 + ++bfs_stgw;
4.120 + }
4.121
4.122 -
4.123 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
4.124 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
4.125 - max_flow_test.augmentOnShortestPath();
4.126 - max_flow_test.augmentOnShortestPath();
4.127 + while (max_flow_test.augmentOnShortestPath()) { }
4.128
4.129 std::cout << max_flow_test.flowValue() << std::endl;
4.130
5.1 --- a/src/work/marci/edmonds_karp.h Mon Apr 26 09:21:27 2004 +0000
5.2 +++ b/src/work/marci/edmonds_karp.h Mon Apr 26 09:54:24 2004 +0000
5.3 @@ -322,7 +322,9 @@
5.4 typename MapGraphWrapper::template NodeMap<int> dist;
5.5 public:
5.6 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
5.7 - void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
5.8 + void set(const typename MapGraphWrapper::Node& n, int a) {
5.9 + dist.set(n, a);
5.10 + }
5.11 int operator[](const typename MapGraphWrapper::Node& n)
5.12 { return dist[n]; }
5.13 // int get(const typename MapGraphWrapper::Node& n) const {
6.1 --- a/src/work/marci/for_each_macros.h Mon Apr 26 09:21:27 2004 +0000
6.2 +++ b/src/work/marci/for_each_macros.h Mon Apr 26 09:54:24 2004 +0000
6.3 @@ -4,13 +4,13 @@
6.4
6.5 namespace hugo {
6.6
6.7 -#define FOR_EACH(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.8 -#define FOR_EACH_INC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.9 +#define FOR_EACH_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.10 +#define FOR_EACH_INC_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.11
6.12 -#define FOR_EACH_EDGE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.13 -#define FOR_EACH_NODE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.14 -#define FOR_EACH_INEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.15 -#define FOR_EACH_OUTEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.16 +#define FOR_EACH_EDGE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.17 +#define FOR_EACH_NODE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
6.18 +#define FOR_EACH_INEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.19 +#define FOR_EACH_OUTEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
6.20
6.21 // template<typename It, typename Graph>
6.22 // It loopFirst(const Graph& g) const {
7.1 --- a/src/work/marci/graph_wrapper.h Mon Apr 26 09:21:27 2004 +0000
7.2 +++ b/src/work/marci/graph_wrapper.h Mon Apr 26 09:54:24 2004 +0000
7.3 @@ -923,12 +923,17 @@
7.4 SFalseTTrueMap* s_false_t_true_map;
7.5
7.6 public:
7.7 - static const bool S_CLASS=false;
7.8 - static const bool T_CLASS=true;
7.9 + //marci
7.10 + //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
7.11 + //static const bool S_CLASS=false;
7.12 + //static const bool T_CLASS=true;
7.13
7.14 + bool S_CLASS;
7.15 + bool T_CLASS;
7.16 +
7.17 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
7.18 - : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
7.19 - }
7.20 + : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
7.21 + S_CLASS(false), T_CLASS(true) { }
7.22 typedef typename GraphWrapper<Graph>::Node Node;
7.23 //using GraphWrapper<Graph>::NodeIt;
7.24 typedef typename GraphWrapper<Graph>::Edge Edge;
7.25 @@ -1102,7 +1107,7 @@
7.26 //(invalid, 2, vmi)
7.27 //invalid, 3, invalid)
7.28 template <typename T> class NodeMap;
7.29 - template <typename T> class EdgeMap;
7.30 + template <typename T, typename Parent> class EdgeMap;
7.31
7.32 // template <typename T> friend class NodeMap;
7.33 // template <typename T> friend class EdgeMap;
7.34 @@ -1141,9 +1146,11 @@
7.35 return (v.spec!=u.spec ||
7.36 static_cast<typename Graph::Node>(u)!=
7.37 static_cast<typename Graph::Node>(v));
7.38 - }
7.39 + }
7.40 + friend std::ostream& operator<<(std::ostream& os, const Node& i);
7.41 int getSpec() const { return spec; }
7.42 };
7.43 +
7.44 class NodeIt {
7.45 friend class GraphWrapper<Graph>;
7.46 friend class stGraphWrapper<Graph>;
7.47 @@ -1155,14 +1162,15 @@
7.48 n(_n), spec(_spec) { }
7.49 NodeIt(const Invalid& i) : n(i), spec(3) { }
7.50 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
7.51 - if (!_G->valid(n)) spec=1;
7.52 + if (!_G.graph->valid(n)) spec=1;
7.53 }
7.54 operator Node() const { return Node(n, spec); }
7.55 };
7.56 +
7.57 class Edge : public Graph::Edge {
7.58 friend class GraphWrapper<Graph>;
7.59 friend class stGraphWrapper<Graph>;
7.60 - template <typename T> friend class EdgeMap;
7.61 + template <typename T, typename Parent> friend class EdgeMap;
7.62 int spec;
7.63 typename Graph::Node n;
7.64 public:
7.65 @@ -1184,8 +1192,10 @@
7.66 static_cast<typename Graph::Edge>(v) ||
7.67 u.n!=v.n);
7.68 }
7.69 + friend std::ostream& operator<<(std::ostream& os, const Edge& i);
7.70 int getSpec() const { return spec; }
7.71 };
7.72 +
7.73 class OutEdgeIt {
7.74 friend class GraphWrapper<Graph>;
7.75 friend class stGraphWrapper<Graph>;
7.76 @@ -1229,6 +1239,7 @@
7.77 }
7.78 operator Edge() const { return Edge(e, spec, n); }
7.79 };
7.80 +
7.81 class InEdgeIt {
7.82 friend class GraphWrapper<Graph>;
7.83 friend class stGraphWrapper<Graph>;
7.84 @@ -1261,9 +1272,10 @@
7.85 e=INVALID;
7.86 spec=3;
7.87 n=INVALID;
7.88 + break;
7.89 case 2:
7.90 e=INVALID;
7.91 - spec=1;
7.92 + spec=2;
7.93 _G.graph->first(n, T_CLASS); //vmi->t;
7.94 if (!_G.graph->valid(n)) spec=3; //Ha T ures
7.95 break;
7.96 @@ -1271,6 +1283,7 @@
7.97 }
7.98 operator Edge() const { return Edge(e, spec, n); }
7.99 };
7.100 +
7.101 class EdgeIt {
7.102 friend class GraphWrapper<Graph>;
7.103 friend class stGraphWrapper<Graph>;
7.104 @@ -1334,7 +1347,7 @@
7.105 typename Graph::Node v;
7.106 switch (i.spec) {
7.107 case 0: //normal edge
7.108 - this->graph->aNode(i.e);
7.109 + v=this->graph->aNode(i.e);
7.110 this->graph->next(i.e);
7.111 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
7.112 if (this->graph->inSClass(v)) { //S, nincs kiel
7.113 @@ -1447,14 +1460,19 @@
7.114 bool valid(const Node& n) const { return (n.spec<3); }
7.115 bool valid(const Edge& e) const { return (e.spec<3); }
7.116
7.117 -// int nodeNum() const { return this->graph->nodeNum(); }
7.118 -// int edgeNum() const { return this->graph->edgeNum(); }
7.119 + int nodeNum() const { return this->graph->nodeNum()+2; }
7.120 + int edgeNum() const {
7.121 + return this->graph->edgeNum()+this->graph->nodeNum();
7.122 + }
7.123
7.124 Node aNode(const OutEdgeIt& e) const { return tail(e); }
7.125 Node aNode(const InEdgeIt& e) const { return head(e); }
7.126 Node bNode(const OutEdgeIt& e) const { return head(e); }
7.127 Node bNode(const InEdgeIt& e) const { return tail(e); }
7.128 -
7.129 +
7.130 + void addNode() const { }
7.131 + void addEdge() const { }
7.132 +
7.133 // Node addNode() const { return Node(this->graph->addNode()); }
7.134 // Edge addEdge(const Node& tail, const Node& head) const {
7.135 // return Edge(this->graph->addEdge(tail, head)); }
7.136 @@ -1468,7 +1486,9 @@
7.137 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
7.138 T s_value, t_value;
7.139 public:
7.140 - NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G) { }
7.141 + NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
7.142 + s_value(),
7.143 + t_value() { }
7.144 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
7.145 s_value(a),
7.146 t_value(a) { }
7.147 @@ -1502,8 +1522,11 @@
7.148 }
7.149 };
7.150
7.151 - template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
7.152 - typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
7.153 + template<typename T,
7.154 + typename Parent=
7.155 + typename GraphWrapper<Graph>::template EdgeMap<T> >
7.156 + class EdgeMap : public Parent {
7.157 + //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
7.158 typename GraphWrapper<Graph>::template NodeMap<T> node_value;
7.159 public:
7.160 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
7.161 @@ -1527,7 +1550,7 @@
7.162 void set(const Edge& e, T t) {
7.163 switch (e.spec) {
7.164 case 0:
7.165 - GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
7.166 + Parent::set(e, t);
7.167 break;
7.168 case 1:
7.169 node_value.set(e.n, t);
7.170 @@ -1539,6 +1562,55 @@
7.171 }
7.172 }
7.173 };
7.174 +
7.175 +// template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
7.176 +// typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
7.177 +// typename GraphWrapper<Graph>::template NodeMap<T> node_value;
7.178 +// public:
7.179 +// EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
7.180 +// node_value(_G) { }
7.181 +// EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
7.182 +// node_value(_G, a) { }
7.183 +// T operator[](const Edge& e) const {
7.184 +// switch (e.spec) {
7.185 +// case 0:
7.186 +// return Parent::operator[](e);
7.187 +// break;
7.188 +// case 1:
7.189 +// return node_value[e.n];
7.190 +// break;
7.191 +// case 2:
7.192 +// default:
7.193 +// return node_value[e.n];
7.194 +// break;
7.195 +// }
7.196 +// }
7.197 +// void set(const Edge& e, T t) {
7.198 +// switch (e.spec) {
7.199 +// case 0:
7.200 +// GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
7.201 +// break;
7.202 +// case 1:
7.203 +// node_value.set(e.n, t);
7.204 +// break;
7.205 +// case 2:
7.206 +// default:
7.207 +// node_value.set(e.n, t);
7.208 +// break;
7.209 +// }
7.210 +// }
7.211 +// };
7.212 +
7.213 + friend std::ostream& operator<<(std::ostream& os, const Node& i) {
7.214 + os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
7.215 + return os;
7.216 + }
7.217 + friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
7.218 + os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
7.219 + " node: " << i.n << ")";
7.220 + return os;
7.221 + }
7.222 +
7.223 };
7.224
7.225 ///@}
8.1 --- a/src/work/marci/leda_graph_wrapper.h Mon Apr 26 09:21:27 2004 +0000
8.2 +++ b/src/work/marci/leda_graph_wrapper.h Mon Apr 26 09:54:24 2004 +0000
8.3 @@ -22,8 +22,11 @@
8.4 // @defgroup empty_graph The LedaGraphWrapper class
8.5 // @{
8.6
8.7 - /// An empty graph class.
8.8 + /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
8.9
8.10 + /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
8.11 + /// and then the generic algorithms and wrappers of HUGO can be used
8.12 + /// with LEDA graphs.
8.13 /// This class provides all the common features of a grapf structure,
8.14 /// however completely without implementations or real data structures
8.15 /// behind the interface.
8.16 @@ -194,19 +197,19 @@
8.17 return i;
8.18 }
8.19
8.20 - template< typename It >
8.21 - It first() const {
8.22 - It e;
8.23 - first(e);
8.24 - return e;
8.25 - }
8.26 +// template< typename It >
8.27 +// It first() const {
8.28 +// It e;
8.29 +// first(e);
8.30 +// return e;
8.31 +// }
8.32
8.33 - template< typename It >
8.34 - It first(Node v) const {
8.35 - It e;
8.36 - first(e, v);
8.37 - return e;
8.38 - }
8.39 +// template< typename It >
8.40 +// It first(Node v) const {
8.41 +// It e;
8.42 +// first(e, v);
8.43 +// return e;
8.44 +// }
8.45
8.46 ///Gives back the head node of an edge.
8.47 Node head(Edge e) const {
9.1 --- a/src/work/marci/macro_test.cc Mon Apr 26 09:21:27 2004 +0000
9.2 +++ b/src/work/marci/macro_test.cc Mon Apr 26 09:54:24 2004 +0000
9.3 @@ -14,7 +14,7 @@
9.4 Graph::Node n1=g.addNode();
9.5 Graph::Node n2=g.addNode();
9.6 Graph::NodeIt n;
9.7 - FOR_EACH(n, g) {
9.8 + FOR_EACH_GLOB(n, g) {
9.9 std::cout << g.id(n) << " ";
9.10 }
9.11 std::cout << std::endl;
10.1 --- a/src/work/marci/makefile Mon Apr 26 09:21:27 2004 +0000
10.2 +++ b/src/work/marci/makefile Mon Apr 26 09:54:24 2004 +0000
10.3 @@ -9,7 +9,7 @@
10.4 CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
10.5
10.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
10.7 -BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
10.8 +BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
10.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
10.10
10.11 include ../makefile