1.1 --- a/src/work/marci/merge_node_graph_wrapper.h Thu Nov 18 22:31:21 2004 +0000
1.2 +++ b/src/work/marci/merge_node_graph_wrapper.h Fri Nov 19 17:22:29 2004 +0000
1.3 @@ -38,11 +38,14 @@
1.4 class P2 : public GraphWrapperBase<_Graph2> {
1.5 };
1.6
1.7 + /*! A base class for merging the node-set of two node-disjoint graphs
1.8 + into the node-set of one graph.
1.9 + */
1.10 template <typename _Graph1, typename _Graph2, typename Enable=void>
1.11 class MergeNodeGraphWrapperBase :
1.12 public P1<_Graph1>, public P2<_Graph2> {
1.13 public:
1.14 - void print() const { std::cout << "generic" << std::endl; }
1.15 + void printNode() const { std::cout << "generic" << std::endl; }
1.16 typedef _Graph1 Graph1;
1.17 typedef _Graph2 Graph2;
1.18 typedef P1<_Graph1> Parent1;
1.19 @@ -139,8 +142,8 @@
1.20 else
1.21 ParentMap2::set(n, value);
1.22 }
1.23 - using ParentMap1::operator[];
1.24 - using ParentMap2::operator[];
1.25 +// using ParentMap1::operator[];
1.26 +// using ParentMap2::operator[];
1.27 };
1.28
1.29 };
1.30 @@ -152,7 +155,7 @@
1.31 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
1.32 public P1<_Graph1>, public P2<_Graph2> {
1.33 public :
1.34 - void print() const { std::cout << "same" << std::endl; }
1.35 + void printNode() const { std::cout << "same" << std::endl; }
1.36 typedef _Graph1 Graph1;
1.37 typedef _Graph2 Graph2;
1.38 typedef P1<_Graph1> Parent1;
1.39 @@ -175,7 +178,7 @@
1.40 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
1.41 public P1<_Graph1>, public P2<_Graph2> {
1.42 public :
1.43 - void print() const { std::cout << "2. nagyobb" << std::endl; }
1.44 + void printNode() const { std::cout << "2. nagyobb" << std::endl; }
1.45 typedef _Graph1 Graph1;
1.46 typedef _Graph2 Graph2;
1.47 typedef P1<_Graph1> Parent1;
1.48 @@ -198,7 +201,7 @@
1.49 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
1.50 public P1<_Graph1>, public P2<_Graph2> {
1.51 public :
1.52 - void print() const { std::cout << "1. nagyobb" << std::endl; }
1.53 + void printNode() const { std::cout << "1. nagyobb" << std::endl; }
1.54 typedef _Graph1 Graph1;
1.55 typedef _Graph2 Graph2;
1.56 typedef P1<_Graph1> Parent1;
1.57 @@ -215,14 +218,14 @@
1.58 };
1.59
1.60
1.61 - template <typename _Graph1, typename _Graph2, typename Enable=void>
1.62 + template <typename _Graph1, typename _Graph2>
1.63 class MergeNodeGraphWrapper : public
1.64 - IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > {
1.65 + IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
1.66 public:
1.67 typedef _Graph1 Graph1;
1.68 typedef _Graph2 Graph2;
1.69 typedef IterableGraphExtender<
1.70 - MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > Parent;
1.71 + MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
1.72 protected:
1.73 MergeNodeGraphWrapper() { }
1.74 public:
1.75 @@ -232,6 +235,200 @@
1.76 }
1.77 };
1.78
1.79 +
1.80 + /*! A base class for merging the node-sets and edge-sets of
1.81 + two node-disjoint graphs
1.82 + into one graph.
1.83 + */
1.84 + template <typename _Graph1, typename _Graph2, typename Enable=void>
1.85 + class MergeEdgeGraphWrapperBase :
1.86 + public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
1.87 + public:
1.88 + void printEdge() const { std::cout << "generic" << std::endl; }
1.89 + typedef _Graph1 Graph1;
1.90 + typedef _Graph2 Graph2;
1.91 + typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
1.92 + typedef typename Parent::Parent1 Parent1;
1.93 + typedef typename Parent::Parent2 Parent2;
1.94 +// typedef P1<_Graph1> Parent1;
1.95 +// typedef P2<_Graph2> Parent2;
1.96 + typedef typename Parent1::Edge Graph1Edge;
1.97 + typedef typename Parent2::Edge Graph2Edge;
1.98 + protected:
1.99 + MergeEdgeGraphWrapperBase() { }
1.100 + public:
1.101 + template <typename _Value> class EdgeMap;
1.102 +
1.103 + typedef typename Parent::Node Node;
1.104 +
1.105 + class Edge : public Graph1Edge, public Graph2Edge {
1.106 + friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
1.107 + template <typename Value> friend class EdgeMap;
1.108 + protected:
1.109 + bool backward; //true, iff backward
1.110 + public:
1.111 + Edge() { }
1.112 + /// \todo =false is needed, or causes problems?
1.113 + /// If \c _backward is false, then we get an edge corresponding to the
1.114 + /// original one, otherwise its oppositely directed pair is obtained.
1.115 + Edge(const Graph1Edge& n1,
1.116 + const Graph2Edge& n2, bool _backward) :
1.117 + Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1.118 + Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1.119 + bool operator==(const Edge& v) const {
1.120 + return (this->backward==v.backward &&
1.121 + static_cast<Graph1Edge>(*this)==
1.122 + static_cast<Graph1Edge>(v) &&
1.123 + static_cast<Graph2Edge>(*this)==
1.124 + static_cast<Graph2Edge>(v));
1.125 + }
1.126 + bool operator!=(const Edge& v) const {
1.127 + return (this->backward!=v.backward ||
1.128 + static_cast<Graph1Edge>(*this)!=
1.129 + static_cast<Graph1Edge>(v) ||
1.130 + static_cast<Graph2Edge>(*this)!=
1.131 + static_cast<Graph2Edge>(v));
1.132 + }
1.133 + };
1.134 +
1.135 + using Parent::first;
1.136 + void first(Edge& i) const {
1.137 + Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1.138 + i.backward=false;
1.139 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.140 + Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.141 + i.backward=true;
1.142 + }
1.143 + }
1.144 + void firstIn(Edge& i, const Node& n) const {
1.145 + Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1.146 + i.backward=false;
1.147 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.148 + Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
1.149 + i.backward=true;
1.150 + }
1.151 + }
1.152 + void firstOut(Edge& i, const Node& n) const {
1.153 + Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1.154 + i.backward=false;
1.155 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.156 + Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
1.157 + i.backward=true;
1.158 + }
1.159 + }
1.160 +
1.161 + using Parent::next;
1.162 + void next(Edge& i) const {
1.163 + if (!(i.backward)) {
1.164 + Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1.165 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.166 + Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.167 + i.backward=true;
1.168 + }
1.169 + } else {
1.170 + Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
1.171 + }
1.172 + }
1.173 + void nextIn(Edge& i) const {
1.174 + if (!(i.backward)) {
1.175 + Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1.176 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.177 + Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.178 + i.backward=true;
1.179 + }
1.180 + } else {
1.181 + Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
1.182 + }
1.183 + }
1.184 + void nextOut(Edge& i) const {
1.185 + if (!(i.backward)) {
1.186 + Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1.187 + if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.188 + Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.189 + i.backward=true;
1.190 + }
1.191 + } else {
1.192 + Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
1.193 + }
1.194 + }
1.195 +
1.196 + Node source(const Edge& i) const {
1.197 + if (!(i.backward)) {
1.198 + return
1.199 + Node(Parent1::graph->source(i), INVALID, false);
1.200 + } else {
1.201 + return
1.202 + Node(INVALID, Parent2::graph->source(i), true);
1.203 + }
1.204 + }
1.205 +
1.206 + Node target(const Edge& i) const {
1.207 + if (!(i.backward)) {
1.208 + return
1.209 + Node(Parent1::graph->target(i), INVALID, false);
1.210 + } else {
1.211 + return
1.212 + Node(INVALID, Parent2::graph->target(i), true);
1.213 + }
1.214 + }
1.215 +
1.216 + using Parent::id;
1.217 + int id(const Edge& n) const {
1.218 + if (!n.backward)
1.219 + return this->Parent1::graph->id(n);
1.220 + else
1.221 + return this->Parent2::graph->id(n);
1.222 + }
1.223 +
1.224 + template <typename _Value>
1.225 + class EdgeMap : public Parent1::template EdgeMap<_Value>,
1.226 + public Parent2::template EdgeMap<_Value> {
1.227 + typedef typename Parent1::template EdgeMap<_Value> ParentMap1;
1.228 + typedef typename Parent2::template EdgeMap<_Value> ParentMap2;
1.229 + public:
1.230 + typedef _Value Value;
1.231 + typedef Edge Key;
1.232 + EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
1.233 + ParentMap1(gw), ParentMap2(gw) { }
1.234 + EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
1.235 + const _Value& value) :
1.236 + ParentMap1(gw, value), ParentMap2(gw, value) { }
1.237 + _Value operator[](const Edge& n) const {
1.238 + if (!n.backward)
1.239 + return ParentMap1::operator[](n);
1.240 + else
1.241 + return ParentMap2::operator[](n);
1.242 + }
1.243 + void set(const Edge& n, const _Value& value) {
1.244 + if (!n.backward)
1.245 + ParentMap1::set(n, value);
1.246 + else
1.247 + ParentMap2::set(n, value);
1.248 + }
1.249 +// using ParentMap1::operator[];
1.250 +// using ParentMap2::operator[];
1.251 + };
1.252 +
1.253 + };
1.254 +
1.255 +
1.256 + template <typename _Graph1, typename _Graph2>
1.257 + class MergeEdgeGraphWrapper : public
1.258 + IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
1.259 + public:
1.260 + typedef _Graph1 Graph1;
1.261 + typedef _Graph2 Graph2;
1.262 + typedef IterableGraphExtender<
1.263 + MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
1.264 + protected:
1.265 + MergeEdgeGraphWrapper() { }
1.266 + public:
1.267 + MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1.268 + Parent::Parent1::setGraph(_graph1);
1.269 + Parent::Parent2::setGraph(_graph2);
1.270 + }
1.271 + };
1.272 +
1.273
1.274 template <typename _Graph, typename _EdgeSetGraph>
1.275 class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
2.1 --- a/src/work/marci/merge_node_graph_wrapper_test.cc Thu Nov 18 22:31:21 2004 +0000
2.2 +++ b/src/work/marci/merge_node_graph_wrapper_test.cc Fri Nov 19 17:22:29 2004 +0000
2.3 @@ -1,7 +1,9 @@
2.4 #include <iostream>
2.5 +#include <fstream>
2.6
2.7 #include <lemon/list_graph.h>
2.8 #include <lemon/smart_graph.h>
2.9 +#include <lemon/dimacs.h>
2.10 #include <merge_node_graph_wrapper.h>
2.11
2.12 #include<lemon/concept_check.h>
2.13 @@ -23,22 +25,64 @@
2.14 typedef SmartGraph Graph1;
2.15 typedef ListGraph Graph2;
2.16
2.17 -// {
2.18 -// checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >();
2.19 -// }
2.20 {
2.21 + checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >();
2.22 + }
2.23 + {
2.24 + checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();
2.25 + }
2.26 +
2.27 Graph1 g;
2.28 Graph2 h;
2.29 - typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
2.30 + typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
2.31 GW gw(g, h);
2.32 - Graph1::Node n1=g.addNode();
2.33 - Graph1::Node n2=g.addNode();
2.34 - Graph1::Node n3=g.addNode();
2.35 - Graph2::Node n4=h.addNode();
2.36 - Graph2::Node n5=h.addNode();
2.37 +
2.38 + std::ifstream f1("graph1.dim");
2.39 + std::ifstream f2("graph2.dim");
2.40 + readDimacs(f1, g);
2.41 + readDimacs(f2, h);
2.42 + {
2.43 +
2.44 +// Graph1::Node n1=g.addNode();
2.45 +// Graph1::Node n2=g.addNode();
2.46 +// Graph1::Node n3=g.addNode();
2.47 +// Graph2::Node n4=h.addNode();
2.48 +// Graph2::Node n5=h.addNode();
2.49 +// Graph2::Node n6=h.addNode();
2.50 +// Graph1::Edge e1=g.addEdge(n1, n2);
2.51 +// Graph1::Edge e2=g.addEdge(n1, n3);
2.52 +// Graph2::Edge e3=h.addEdge(n4, n5);
2.53 +// Graph2::Edge e4=h.addEdge(n4, n5);
2.54 //GW::NodeIt n(gw)
2.55 + cout << "1st graph" << endl;
2.56 + cout << " nodes:" << endl;
2.57 + for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
2.58 + cout << " " << g.id(n) << endl;
2.59 + }
2.60 + cout << " edges:" << endl;
2.61 + for (Graph1::EdgeIt n(g); n!=INVALID; ++n) {
2.62 + cout << " " << g.id(n) << ": "
2.63 + << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
2.64 + }
2.65 + cout << "2nd graph" << endl;
2.66 + cout << " nodes:" << endl;
2.67 + for (Graph2::NodeIt n(h); n!=INVALID; ++n) {
2.68 + cout << " " << h.id(n) << endl;
2.69 + }
2.70 + cout << " edges:" << endl;
2.71 + for (Graph2::EdgeIt n(h); n!=INVALID; ++n) {
2.72 + cout << " " << h.id(n) << ": "
2.73 + << h.id(h.source(n)) << "->" << h.id(h.target(n)) << endl;
2.74 + }
2.75 + cout << "merged graph" << endl;
2.76 + cout << " nodes:" << endl;
2.77 for (GW::NodeIt n(gw); n!=INVALID; ++n) {
2.78 - cout << gw.id(n) << endl;
2.79 + cout << " "<< gw.id(n) << endl;
2.80 + }
2.81 + cout << " edges:" << endl;
2.82 + for (GW::EdgeIt n(gw); n!=INVALID; ++n) {
2.83 + cout << " " << gw.id(n) << ": "
2.84 + << gw.id(gw.source(n)) << "->" << gw.id(gw.target(n)) << endl;
2.85 }
2.86
2.87 GW::NodeMap<int> nm(gw);
2.88 @@ -48,13 +92,13 @@
2.89 nm.set(n, i);
2.90 }
2.91 for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
2.92 - cout << nm[n] << endl;
2.93 + cout << nm[GW::Node(n,INVALID,false)] << endl;
2.94 }
2.95 for (Graph2::NodeIt n(h); n!=INVALID; ++n) {
2.96 - cout << nm[n] << endl;
2.97 + cout << nm[GW::Node(INVALID,n,true)] << endl;
2.98 }
2.99
2.100 - gw.print();
2.101 + gw.printNode();
2.102
2.103 {
2.104 // typedef SmartGraph Graph1;
2.105 @@ -64,7 +108,7 @@
2.106 Graph2 h;
2.107 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
2.108 GW gw(g, h);
2.109 - gw.print();
2.110 + gw.printNode();
2.111 }
2.112 {
2.113 // typedef SmartGraph Graph1;
2.114 @@ -74,7 +118,7 @@
2.115 Graph2 h;
2.116 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
2.117 GW gw(g, h);
2.118 - gw.print();
2.119 + gw.printNode();
2.120 }
2.121 {
2.122 // typedef SmartGraph Graph1;
2.123 @@ -84,7 +128,7 @@
2.124 Graph2 h;
2.125 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
2.126 GW gw(g, h);
2.127 - gw.print();
2.128 + gw.printNode();
2.129 }
2.130 }
2.131 {