1.1 --- a/src/work/marci/bipartite_matching_leda.cc Mon Apr 26 16:02:09 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,219 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -#include <vector>
1.8 -#include <cstdlib>
1.9 -
1.10 -#include <LEDA/graph.h>
1.11 -#include <LEDA/mcb_matching.h>
1.12 -#include <LEDA/list.h>
1.13 -
1.14 -#include <leda_graph_wrapper.h>
1.15 -#include <list_graph.h>
1.16 -//#include <smart_graph.h>
1.17 -//#include <dimacs.h>
1.18 -#include <time_measure.h>
1.19 -#include <for_each_macros.h>
1.20 -//#include <bfs_iterator.h>
1.21 -#include <graph_wrapper.h>
1.22 -#include <maps.h>
1.23 -#include <edmonds_karp.h>
1.24 -#include <preflow.h>
1.25 -
1.26 -/**
1.27 - * Inicializalja a veletlenszamgeneratort.
1.28 - * Figyelem, ez nem jo igazi random szamokhoz,
1.29 - * erre ne bizzad a titkaidat!
1.30 - */
1.31 -void random_init()
1.32 -{
1.33 - unsigned int seed = getpid();
1.34 - seed |= seed << 15;
1.35 - seed ^= time(0);
1.36 -
1.37 - srand(seed);
1.38 -}
1.39 -
1.40 -/**
1.41 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
1.42 - */
1.43 -int random(int m)
1.44 -{
1.45 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
1.46 -}
1.47 -
1.48 -using namespace hugo;
1.49 -
1.50 -int main() {
1.51 - //for leda graph
1.52 - leda::graph lg;
1.53 - //lg.make_undirected();
1.54 - typedef LedaGraphWrapper<leda::graph> Graph;
1.55 - Graph g(lg);
1.56 -
1.57 - //for UndirListGraph
1.58 - //typedef UndirListGraph Graph;
1.59 - //Graph g;
1.60 -
1.61 - typedef Graph::Node Node;
1.62 - typedef Graph::NodeIt NodeIt;
1.63 - typedef Graph::Edge Edge;
1.64 - typedef Graph::EdgeIt EdgeIt;
1.65 - typedef Graph::OutEdgeIt OutEdgeIt;
1.66 -
1.67 - std::vector<Graph::Node> s_nodes;
1.68 - std::vector<Graph::Node> t_nodes;
1.69 -
1.70 - int a;
1.71 - std::cout << "number of nodes in the first color class=";
1.72 - std::cin >> a;
1.73 - int b;
1.74 - std::cout << "number of nodes in the second color class=";
1.75 - std::cin >> b;
1.76 - int m;
1.77 - std::cout << "number of edges=";
1.78 - std::cin >> m;
1.79 -
1.80 -
1.81 - for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
1.82 - for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
1.83 -
1.84 - random_init();
1.85 - for(int i=0; i<m; ++i) {
1.86 - g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
1.87 - }
1.88 -
1.89 - Graph::NodeMap<int> ref_map(g, -1);
1.90 -
1.91 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.92 - for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
1.93 - for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
1.94 -
1.95 -// Graph::Node u;
1.96 -// std::cout << "These nodes will be in S:\n";
1.97 -// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
1.98 -// //irni 1etlen FOR_EACH-csel.
1.99 -// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
1.100 -// std::cout << u << " ";
1.101 -// std::cout << "\n";
1.102 -// std::cout << "These nodes will be in T:\n";
1.103 -// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
1.104 -// std::cout << u << " ";
1.105 -// std::cout << "\n";
1.106 -
1.107 - typedef BipartiteGraphWrapper<Graph> BGW;
1.108 - BGW bgw(g, bipartite_map);
1.109 -
1.110 -// std::cout << "Nodes by NodeIt:\n";
1.111 -// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
1.112 -// std::cout << n << " ";
1.113 -// }
1.114 -// std::cout << "\n";
1.115 -// std::cout << "Nodes in S by ClassNodeIt:\n";
1.116 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
1.117 -// std::cout << n << " ";
1.118 -// }
1.119 -// std::cout << "\n";
1.120 -// std::cout << "Nodes in T by ClassNodeIt:\n";
1.121 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
1.122 -// std::cout << n << " ";
1.123 -// }
1.124 -// std::cout << "\n";
1.125 -// std::cout << "Edges of the bipartite graph:\n";
1.126 -// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
1.127 -// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
1.128 -// }
1.129 -
1.130 - BGW::NodeMap<int> dbyj(bgw);
1.131 - BGW::EdgeMap<int> dbyxcj(bgw);
1.132 -
1.133 - typedef stGraphWrapper<BGW> stGW;
1.134 - stGW stgw(bgw);
1.135 - ConstMap<stGW::Edge, int> const1map(1);
1.136 -// stGW::NodeMap<int> ize(stgw);
1.137 -
1.138 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.139 -// Graph::NodeIt si;
1.140 -// Graph::Node s;
1.141 -// s=g.first(si);
1.142 -// bfs.pushAndSetReached(BGW::Node(s));
1.143 -// while (!bfs.finished()) { ++bfs; }
1.144 -
1.145 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.146 -// std::cout << "out-edges of " << n << ":\n";
1.147 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.148 -// std::cout << " " << e << "\n";
1.149 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.150 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.151 -// }
1.152 -// std::cout << "in-edges of " << n << ":\n";
1.153 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.154 -// std::cout << " " << e << "\n";
1.155 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.156 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.157 -// }
1.158 -// }
1.159 -// std::cout << "Edges of the stGraphWrapper:\n";
1.160 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.161 -// std::cout << " " << n << "\n";
1.162 -// }
1.163 -
1.164 -// stGW::NodeMap<bool> b(stgw);
1.165 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.166 -// std::cout << n << ": " << b[n] <<"\n";
1.167 -// }
1.168 -
1.169 -// std::cout << "Bfs from s: \n";
1.170 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.171 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.172 -// while (!bfs_stgw.finished()) {
1.173 -// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
1.174 -// ++bfs_stgw;
1.175 -// }
1.176 -
1.177 -
1.178 - Timer ts;
1.179 - ts.reset();
1.180 - stGW::EdgeMap<int> max_flow(stgw);
1.181 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.182 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
1.183 -// while (max_flow_test.augmentOnShortestPath()) { }
1.184 - typedef ListGraph MutableGraph;
1.185 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.186 - while (max_flow_test.augmentOnBlockingFlow2()) {
1.187 - std::cout << max_flow_test.flowValue() << std::endl;
1.188 - }
1.189 - std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
1.190 - std::cout << "elapsed time: " << ts << std::endl;
1.191 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.192 -// std::cout << e << ": " << max_flow[e] << "\n";
1.193 -// }
1.194 -// std::cout << "\n";
1.195 -
1.196 - ts.reset();
1.197 - stGW::EdgeMap<int> pre_flow(stgw);
1.198 - Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.199 - pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
1.200 - pre_flow_test.run();
1.201 - std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
1.202 - std::cout << "elapsed time: " << ts << std::endl;
1.203 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.204 -// std::cout << e << ": " << pre_flow[e] << "\n";
1.205 -// }
1.206 -// std::cout << "\n";
1.207 -
1.208 - ts.reset();
1.209 - leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
1.210 - // stGW::EdgeMap<int> pre_flow(stgw);
1.211 - //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.212 - // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
1.213 - //pre_flow_test.run();
1.214 - std::cout << "leda matching value: " << ml.size() << std::endl;
1.215 - std::cout << "elapsed time: " << ts << std::endl;
1.216 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.217 -// std::cout << e << ": " << pre_flow[e] << "\n";
1.218 -// }
1.219 -// std::cout << "\n";
1.220 -
1.221 - return 0;
1.222 -}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/leda/bipartite_matching_leda.cc Mon Apr 26 16:08:46 2004 +0000
2.3 @@ -0,0 +1,219 @@
2.4 +// -*- c++ -*-
2.5 +#include <iostream>
2.6 +#include <fstream>
2.7 +#include <vector>
2.8 +#include <cstdlib>
2.9 +
2.10 +#include <LEDA/graph.h>
2.11 +#include <LEDA/mcb_matching.h>
2.12 +#include <LEDA/list.h>
2.13 +
2.14 +#include <leda_graph_wrapper.h>
2.15 +#include <list_graph.h>
2.16 +//#include <smart_graph.h>
2.17 +//#include <dimacs.h>
2.18 +#include <time_measure.h>
2.19 +#include <for_each_macros.h>
2.20 +//#include <bfs_iterator.h>
2.21 +#include <graph_wrapper.h>
2.22 +#include <maps.h>
2.23 +#include <edmonds_karp.h>
2.24 +#include <preflow.h>
2.25 +
2.26 +/**
2.27 + * Inicializalja a veletlenszamgeneratort.
2.28 + * Figyelem, ez nem jo igazi random szamokhoz,
2.29 + * erre ne bizzad a titkaidat!
2.30 + */
2.31 +void random_init()
2.32 +{
2.33 + unsigned int seed = getpid();
2.34 + seed |= seed << 15;
2.35 + seed ^= time(0);
2.36 +
2.37 + srand(seed);
2.38 +}
2.39 +
2.40 +/**
2.41 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
2.42 + */
2.43 +int random(int m)
2.44 +{
2.45 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
2.46 +}
2.47 +
2.48 +using namespace hugo;
2.49 +
2.50 +int main() {
2.51 + //for leda graph
2.52 + leda::graph lg;
2.53 + //lg.make_undirected();
2.54 + typedef LedaGraphWrapper<leda::graph> Graph;
2.55 + Graph g(lg);
2.56 +
2.57 + //for UndirListGraph
2.58 + //typedef UndirListGraph Graph;
2.59 + //Graph g;
2.60 +
2.61 + typedef Graph::Node Node;
2.62 + typedef Graph::NodeIt NodeIt;
2.63 + typedef Graph::Edge Edge;
2.64 + typedef Graph::EdgeIt EdgeIt;
2.65 + typedef Graph::OutEdgeIt OutEdgeIt;
2.66 +
2.67 + std::vector<Graph::Node> s_nodes;
2.68 + std::vector<Graph::Node> t_nodes;
2.69 +
2.70 + int a;
2.71 + std::cout << "number of nodes in the first color class=";
2.72 + std::cin >> a;
2.73 + int b;
2.74 + std::cout << "number of nodes in the second color class=";
2.75 + std::cin >> b;
2.76 + int m;
2.77 + std::cout << "number of edges=";
2.78 + std::cin >> m;
2.79 +
2.80 +
2.81 + for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
2.82 + for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
2.83 +
2.84 + random_init();
2.85 + for(int i=0; i<m; ++i) {
2.86 + g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.87 + }
2.88 +
2.89 + Graph::NodeMap<int> ref_map(g, -1);
2.90 +
2.91 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
2.92 + for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
2.93 + for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
2.94 +
2.95 +// Graph::Node u;
2.96 +// std::cout << "These nodes will be in S:\n";
2.97 +// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
2.98 +// //irni 1etlen FOR_EACH-csel.
2.99 +// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
2.100 +// std::cout << u << " ";
2.101 +// std::cout << "\n";
2.102 +// std::cout << "These nodes will be in T:\n";
2.103 +// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
2.104 +// std::cout << u << " ";
2.105 +// std::cout << "\n";
2.106 +
2.107 + typedef BipartiteGraphWrapper<Graph> BGW;
2.108 + BGW bgw(g, bipartite_map);
2.109 +
2.110 +// std::cout << "Nodes by NodeIt:\n";
2.111 +// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
2.112 +// std::cout << n << " ";
2.113 +// }
2.114 +// std::cout << "\n";
2.115 +// std::cout << "Nodes in S by ClassNodeIt:\n";
2.116 +// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
2.117 +// std::cout << n << " ";
2.118 +// }
2.119 +// std::cout << "\n";
2.120 +// std::cout << "Nodes in T by ClassNodeIt:\n";
2.121 +// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
2.122 +// std::cout << n << " ";
2.123 +// }
2.124 +// std::cout << "\n";
2.125 +// std::cout << "Edges of the bipartite graph:\n";
2.126 +// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
2.127 +// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
2.128 +// }
2.129 +
2.130 + BGW::NodeMap<int> dbyj(bgw);
2.131 + BGW::EdgeMap<int> dbyxcj(bgw);
2.132 +
2.133 + typedef stGraphWrapper<BGW> stGW;
2.134 + stGW stgw(bgw);
2.135 + ConstMap<stGW::Edge, int> const1map(1);
2.136 +// stGW::NodeMap<int> ize(stgw);
2.137 +
2.138 +// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
2.139 +// Graph::NodeIt si;
2.140 +// Graph::Node s;
2.141 +// s=g.first(si);
2.142 +// bfs.pushAndSetReached(BGW::Node(s));
2.143 +// while (!bfs.finished()) { ++bfs; }
2.144 +
2.145 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.146 +// std::cout << "out-edges of " << n << ":\n";
2.147 +// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
2.148 +// std::cout << " " << e << "\n";
2.149 +// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.150 +// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.151 +// }
2.152 +// std::cout << "in-edges of " << n << ":\n";
2.153 +// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
2.154 +// std::cout << " " << e << "\n";
2.155 +// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.156 +// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.157 +// }
2.158 +// }
2.159 +// std::cout << "Edges of the stGraphWrapper:\n";
2.160 +// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
2.161 +// std::cout << " " << n << "\n";
2.162 +// }
2.163 +
2.164 +// stGW::NodeMap<bool> b(stgw);
2.165 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.166 +// std::cout << n << ": " << b[n] <<"\n";
2.167 +// }
2.168 +
2.169 +// std::cout << "Bfs from s: \n";
2.170 +// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
2.171 +// bfs_stgw.pushAndSetReached(stgw.S_NODE);
2.172 +// while (!bfs_stgw.finished()) {
2.173 +// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
2.174 +// ++bfs_stgw;
2.175 +// }
2.176 +
2.177 +
2.178 + Timer ts;
2.179 + ts.reset();
2.180 + stGW::EdgeMap<int> max_flow(stgw);
2.181 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.182 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
2.183 +// while (max_flow_test.augmentOnShortestPath()) { }
2.184 + typedef ListGraph MutableGraph;
2.185 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.186 + while (max_flow_test.augmentOnBlockingFlow2()) {
2.187 + std::cout << max_flow_test.flowValue() << std::endl;
2.188 + }
2.189 + std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
2.190 + std::cout << "elapsed time: " << ts << std::endl;
2.191 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.192 +// std::cout << e << ": " << max_flow[e] << "\n";
2.193 +// }
2.194 +// std::cout << "\n";
2.195 +
2.196 + ts.reset();
2.197 + stGW::EdgeMap<int> pre_flow(stgw);
2.198 + Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.199 + pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
2.200 + pre_flow_test.run();
2.201 + std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
2.202 + std::cout << "elapsed time: " << ts << std::endl;
2.203 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.204 +// std::cout << e << ": " << pre_flow[e] << "\n";
2.205 +// }
2.206 +// std::cout << "\n";
2.207 +
2.208 + ts.reset();
2.209 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
2.210 + // stGW::EdgeMap<int> pre_flow(stgw);
2.211 + //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.212 + // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
2.213 + //pre_flow_test.run();
2.214 + std::cout << "leda matching value: " << ml.size() << std::endl;
2.215 + std::cout << "elapsed time: " << ts << std::endl;
2.216 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.217 +// std::cout << e << ": " << pre_flow[e] << "\n";
2.218 +// }
2.219 +// std::cout << "\n";
2.220 +
2.221 + return 0;
2.222 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h Mon Apr 26 16:08:46 2004 +0000
3.3 @@ -0,0 +1,321 @@
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 + /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
3.29 +
3.30 + /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
3.31 + /// and then the generic algorithms and wrappers of HUGO can be used
3.32 + /// with LEDA graphs.
3.33 + /// This class provides all the common features of a grapf structure,
3.34 + /// however completely without implementations or real data structures
3.35 + /// behind the interface.
3.36 + /// All graph algorithms should compile with this class, but it will not
3.37 + /// run properly, of course.
3.38 + ///
3.39 + /// It can be used for checking the interface compatibility,
3.40 + /// or it can serve as a skeleton of a new graph structure.
3.41 + ///
3.42 + /// Also, you will find here the full documentation of a certain graph
3.43 + /// feature, the documentation of a real graph imlementation
3.44 + /// like @ref ListGraph or
3.45 + /// @ref SmartGraph will just refer to this structure.
3.46 + template<typename Graph>
3.47 + class LedaGraphWrapper
3.48 + {
3.49 + Graph* _graph;
3.50 + public:
3.51 +
3.52 + //LedaGraphWrapper() { }
3.53 + LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
3.54 + LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
3.55 +
3.56 + template <typename T> class NodeMap;
3.57 + template <typename T> class EdgeMap;
3.58 +
3.59 + /// The base type of the node iterators.
3.60 + class Node {
3.61 + friend class LedaGraphWrapper;
3.62 + //friend class Edge;
3.63 + friend class EdgeIt;
3.64 + friend class InEdgeIt;
3.65 + friend class OutEdgeIt;
3.66 + protected:
3.67 + template <typename T> friend class NodeMap;
3.68 + leda_node _n;
3.69 + Node(leda_node __n) : _n(__n) { }
3.70 + public:
3.71 + /// @warning The default constructor sets the iterator
3.72 + /// to an undefined value.
3.73 + Node() {} //FIXME
3.74 + /// Initialize the iterator to be invalid
3.75 + Node(Invalid) : _n(0) { }
3.76 + //Node(const Node &) {}
3.77 + bool operator==(Node n) const { return _n==n._n; } //FIXME
3.78 + bool operator!=(Node n) const { return _n!=n._n; } //FIXME
3.79 + operator leda_node () { return _n; }
3.80 + };
3.81 +
3.82 + /// This iterator goes through each node.
3.83 + class NodeIt : public Node {
3.84 + public:
3.85 + /// @warning The default constructor sets the iterator
3.86 + /// to an undefined value.
3.87 + NodeIt() {} //FIXME
3.88 + /// Initialize the iterator to be invalid
3.89 + NodeIt(Invalid i) : Node(i) {}
3.90 + /// Sets the iterator to the first node of \c G.
3.91 + NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
3.92 + //NodeIt(const NodeIt &) {} //FIXME
3.93 + };
3.94 +
3.95 + /// The base type of the edge iterators.
3.96 + class Edge {
3.97 + friend class LedaGraphWrapper;
3.98 + protected:
3.99 + template <typename T> friend class EdgeMap;
3.100 + leda_edge _e;
3.101 + Edge(leda_edge __e) : _e(__e) { }
3.102 + public:
3.103 + /// @warning The default constructor sets the iterator
3.104 + /// to an undefined value.
3.105 + Edge() {} //FIXME
3.106 + /// Initialize the iterator to be invalid
3.107 + Edge(Invalid) : _e(0) {}
3.108 + //Edge(const Edge &) {}
3.109 + bool operator==(Edge e) const { return _e==e._e; } //FIXME
3.110 + bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
3.111 + operator leda_edge () { return _e; }
3.112 + };
3.113 +
3.114 + /// This iterator goes trought the outgoing edges of a certain graph.
3.115 +
3.116 + class OutEdgeIt : public Edge {
3.117 + public:
3.118 + /// @warning The default constructor sets the iterator
3.119 + /// to an undefined value.
3.120 + OutEdgeIt() {}
3.121 + /// Initialize the iterator to be invalid
3.122 + OutEdgeIt(Invalid i) : Edge(i) {}
3.123 + /// This constructor sets the iterator to first outgoing edge.
3.124 +
3.125 + /// This constructor set the iterator to the first outgoing edge of
3.126 + /// node
3.127 + ///@param n the node
3.128 + ///@param G the graph
3.129 + OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
3.130 + };
3.131 +
3.132 + class InEdgeIt : public Edge {
3.133 + public:
3.134 + /// @warning The default constructor sets the iterator
3.135 + /// to an undefined value.
3.136 + InEdgeIt() {}
3.137 + /// Initialize the iterator to be invalid
3.138 + InEdgeIt(Invalid i) : Edge(i) {}
3.139 + InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
3.140 + };
3.141 +
3.142 + // class SymEdgeIt : public Edge {};
3.143 + class EdgeIt : public Edge {
3.144 + public:
3.145 + /// @warning The default constructor sets the iterator
3.146 + /// to an undefined value.
3.147 + EdgeIt() {}
3.148 + /// Initialize the iterator to be invalid
3.149 + EdgeIt(Invalid i) : Edge(i) {}
3.150 + EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
3.151 + };
3.152 +
3.153 + /// First node of the graph.
3.154 +
3.155 + /// \post \c i and the return value will be the first node.
3.156 + ///
3.157 + NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
3.158 +
3.159 + /// The first outgoing edge.
3.160 + InEdgeIt &first(InEdgeIt &i, Node n) const {
3.161 + i=InEdgeIt(*this, n);
3.162 + return i;
3.163 + }
3.164 + /// The first incoming edge.
3.165 + OutEdgeIt &first(OutEdgeIt &i, Node n) const {
3.166 + i=OutEdgeIt(*this, n);
3.167 + return i;
3.168 + }
3.169 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
3.170 + /// The first edge of the Graph.
3.171 + EdgeIt &first(EdgeIt &i) const {
3.172 + i=EdgeIt(*this);
3.173 + return i; }
3.174 +
3.175 +// Node getNext(Node) const {}
3.176 +// InEdgeIt getNext(InEdgeIt) const {}
3.177 +// OutEdgeIt getNext(OutEdgeIt) const {}
3.178 +// //SymEdgeIt getNext(SymEdgeIt) const {}
3.179 +// EdgeIt getNext(EdgeIt) const {}
3.180 +
3.181 + /// Go to the next node.
3.182 + NodeIt &next(NodeIt &i) const {
3.183 + i._n=_graph->succ_node(i._n);
3.184 + return i;
3.185 + }
3.186 + /// Go to the next incoming edge.
3.187 + InEdgeIt &next(InEdgeIt &i) const {
3.188 + i._e=_graph->in_succ(i._e);
3.189 + return i;
3.190 + }
3.191 + /// Go to the next outgoing edge.
3.192 + OutEdgeIt &next(OutEdgeIt &i) const {
3.193 + i._e=_graph->adj_succ(i._e);
3.194 + return i;
3.195 + }
3.196 + //SymEdgeIt &next(SymEdgeIt &) const {}
3.197 + /// Go to the next edge.
3.198 + EdgeIt &next(EdgeIt &i) const {
3.199 + i._e=_graph->succ_edge(i._e);
3.200 + return i;
3.201 + }
3.202 +
3.203 +// template< typename It >
3.204 +// It first() const {
3.205 +// It e;
3.206 +// first(e);
3.207 +// return e;
3.208 +// }
3.209 +
3.210 +// template< typename It >
3.211 +// It first(Node v) const {
3.212 +// It e;
3.213 +// first(e, v);
3.214 +// return e;
3.215 +// }
3.216 +
3.217 + ///Gives back the head node of an edge.
3.218 + Node head(Edge e) const {
3.219 + return Node(_graph->target(e._e));
3.220 + }
3.221 + ///Gives back the tail node of an edge.
3.222 + Node tail(Edge e) const {
3.223 + return Node(_graph->source(e._e));
3.224 + }
3.225 +
3.226 + Node aNode(InEdgeIt e) const { return head(e); }
3.227 + Node aNode(OutEdgeIt e) const { return tail(e); }
3.228 + // Node aNode(SymEdgeIt) const {}
3.229 +
3.230 + Node bNode(InEdgeIt e) const { return tail(e); }
3.231 + Node bNode(OutEdgeIt e) const { return head(e); }
3.232 + // Node bNode(SymEdgeIt) const {}
3.233 +
3.234 + /// Checks if a node iterator is valid
3.235 + bool valid(Node n) const { return n._n; }
3.236 + /// Checks if an edge iterator is valid
3.237 + bool valid(Edge e) const { return e._e; }
3.238 +
3.239 + ///Gives back the \e id of a node.
3.240 + int id(Node n) const { return n._n->id(); }
3.241 + ///Gives back the \e id of an edge.
3.242 + int id(Edge e) const { return e._e->id(); }
3.243 +
3.244 + //void setInvalid(Node &) const {};
3.245 + //void setInvalid(Edge &) const {};
3.246 +
3.247 + Node addNode() const { return Node(_graph->new_node()); }
3.248 + Edge addEdge(Node tail, Node head) const {
3.249 + return Edge(_graph->new_edge(tail._n, head._n));
3.250 + }
3.251 +
3.252 + void erase(Node n) const { _graph->del_node(n._n); }
3.253 + void erase(Edge e) const { _graph->del_edge(e._e); }
3.254 +
3.255 + void clear() const { _graph->clear(); }
3.256 +
3.257 + int nodeNum() const { return _graph->number_of_nodes(); }
3.258 + int edgeNum() const { return _graph->number_of_edges(); }
3.259 +
3.260 + ///Read/write map from the nodes to type \c T.
3.261 + template<typename T> class NodeMap
3.262 + {
3.263 + leda_node_map<T> leda_stuff;
3.264 + public:
3.265 + typedef T ValueType;
3.266 + typedef Node KeyType;
3.267 +
3.268 + NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
3.269 + NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
3.270 +
3.271 + void set(Node i, T t) { leda_stuff[i._n]=t; }
3.272 + T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
3.273 + T &operator[](Node i) { return leda_stuff[i._n]; }
3.274 + const T &operator[](Node i) const { return leda_stuff[i._n]; }
3.275 +
3.276 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
3.277 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
3.278 + };
3.279 +
3.280 + ///Read/write map from the edges to type \c T.
3.281 + template<typename T> class EdgeMap
3.282 + {
3.283 + leda_edge_map<T> leda_stuff;
3.284 + public:
3.285 + typedef T ValueType;
3.286 + typedef Edge KeyType;
3.287 +
3.288 + EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
3.289 + EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
3.290 +
3.291 + void set(Edge i, T t) { leda_stuff[i._e]=t; }
3.292 + T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
3.293 + T &operator[](Edge i) { return leda_stuff[i._e]; }
3.294 + const T &operator[](Edge i) const { return leda_stuff[i._e]; }
3.295 +
3.296 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
3.297 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
3.298 + };
3.299 +
3.300 + };
3.301 +
3.302 + // @}
3.303 +
3.304 +} //namespace hugo
3.305 +
3.306 +
3.307 +
3.308 +// class EmptyBipGraph : public EmptyGraph
3.309 +// {
3.310 +// class ANode {};
3.311 +// class BNode {};
3.312 +
3.313 +// ANode &next(ANode &) {}
3.314 +// BNode &next(BNode &) {}
3.315 +
3.316 +// ANode &getFirst(ANode &) const {}
3.317 +// BNode &getFirst(BNode &) const {}
3.318 +
3.319 +// enum NodeClass { A = 0, B = 1 };
3.320 +// NodeClass getClass(Node n) {}
3.321 +
3.322 +// }
3.323 +
3.324 +#endif // HUGO_LEDA_GRAPH_WRAPPER_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/marci/leda/makefile Mon Apr 26 16:08:46 2004 +0000
4.3 @@ -0,0 +1,86 @@
4.4 +CXX2 = g++-2.95
4.5 +#CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
4.6 +CXX3=$(CXX)
4.7 +#CXX=$(CXX3)
4.8 +#CC=$(CXX)
4.9 +#LEDAROOT ?= /ledasrc/LEDA-4.1
4.10 +BOOSTROOT ?= /home/marci/boost
4.11 +INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
4.12 +#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
4.13 +#CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
4.14 +
4.15 +LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
4.16 +BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
4.17 +#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
4.18 +
4.19 +include ../makefile
4.20 +#all: $(BINARIES)
4.21 +
4.22 +#.depend dep depend:
4.23 +# -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
4.24 +# -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
4.25 +
4.26 +
4.27 +
4.28 +#makefile: .depend
4.29 +#sinclude .depend
4.30 +
4.31 +leda_graph_demo.o:
4.32 + $(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c leda_graph_demo.cc
4.33 +
4.34 +leda_graph_demo: leda_graph_demo.o
4.35 + $(CXX3) -Wall -O -L$(LEDAROOT) -o leda_graph_demo leda_graph_demo.o -lG -lL -lm
4.36 +
4.37 +bipartite_matching_leda.o:
4.38 + $(CXX3) $(CXXFLAGS) -I$(LEDAROOT)/incl -c bipartite_matching_leda.cc
4.39 +
4.40 +bipartite_matching_leda: bipartite_matching_leda.o
4.41 + $(CXX3) $(CXXFLAGS) -L$(LEDAROOT) -o bipartite_matching_leda bipartite_matching_leda.o -lG -lL -lm
4.42 +
4.43 +max_bipartite_matching_demo.o:
4.44 + $(CXX3) $(CXXFLAGS) -I$(LEDAROOT)/incl -c max_bipartite_matching_demo.cc
4.45 +
4.46 +max_bipartite_matching_demo: max_bipartite_matching_demo.o
4.47 + $(CXX3) $(CXXFLAGS) -L$(LEDAROOT) -o max_bipartite_matching_demo max_bipartite_matching_demo.o -lG -lL -lm
4.48 +
4.49 +leda_bfs_dfs.o:
4.50 + $(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c leda_bfs_dfs.cc
4.51 +
4.52 +leda_bfs_dfs: leda_bfs_dfs.o
4.53 + $(CXX3) -Wall -O -L$(LEDAROOT) -o leda_bfs_dfs leda_bfs_dfs.o -lG -lL -lm
4.54 +
4.55 +#edmonds_karp_demo:
4.56 +# $(CXX3) $(CXXFLAGS) -o edmonds_karp_demo edmonds_karp_demo.cc
4.57 +# $(CXX3) $(CXXFLAGS) -pg -o edmonds_karp_demo_prof edmonds_karp_demo.cc
4.58 +
4.59 +gw_vs_not:
4.60 + $(CXX3) $(CXXFLAGS) -o gw_vs_not gw_vs_not.cc
4.61 +
4.62 +#lg_vs_sg:
4.63 +# $(CXX3) $(CXXFLAGS) -g -I. -I.. -o lg_vs_sg lg_vs_sg.cc
4.64 +
4.65 +edmonds_karp_demo_alpar:
4.66 + $(CXX3) $(CXXFLAGS) -I. -I.. -I../alpar -o edmonds_karp_demo_alpar edmonds_karp_demo_alpar.cc
4.67 +
4.68 +preflow_demo_leda:
4.69 + $(CXX2) -W -Wall -03 -DLEDA_PREFIX -I. -I$(LEDAROOT)/incl -L$(LEDAROOT) -o preflow_demo_leda preflow_demo_leda.cc -lP -lm -lL -lG
4.70 +
4.71 +preflow_demo_leda_uj:
4.72 + $(CXX3) -Wall -O3 -I$(LEDAROOT)/incl -I. -L$(LEDAROOT) -o preflow_demo_leda_uj preflow_demo_leda_uj.cc -lG -lL -lm
4.73 +
4.74 +preflow_demo_boost:
4.75 + $(CXX2) -ftemplate-depth-30 -O3 -I. -I/home/marci/boost -o preflow_demo_boost preflow_demo_boost.cc
4.76 +
4.77 +edmonds_karp_demo_boost:
4.78 + $(CXX2) -ftemplate-depth-30 -O3 -I. -I/home/marci/boost -o edmonds_karp_demo_boost edmonds_karp_demo_boost.cc
4.79 +
4.80 +preflow_demo_jacint:
4.81 + $(CXX3) $(CXXFLAGS) -I. -I.. -I../jacint -o preflow_demo_jacint preflow_demo_jacint.cc
4.82 +
4.83 +preflow_demo_athos:
4.84 + $(CXX3) $(CXXFLAGS) -I. -I.. -I../athos -o preflow_demo_athos preflow_demo_athos.cc
4.85 +
4.86 +#clean:
4.87 +# $(RM) *.o $(BINARIES) .depend
4.88 +#
4.89 +#.PHONY: all clean dep depend
5.1 --- a/src/work/marci/leda_graph_wrapper.h Mon Apr 26 16:02:09 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,321 +0,0 @@
5.4 -// -*- c++ -*-
5.5 -#ifndef HUGO_LEDA_GRAPH_WRAPPER_H
5.6 -#define HUGO_LEDA_GRAPH_WRAPPER_H
5.7 -
5.8 -#include <LEDA/graph.h>
5.9 -#include <LEDA/node_array.h>
5.10 -#include <LEDA/edge_array.h>
5.11 -#include <LEDA/node_map.h>
5.12 -#include <LEDA/edge_map.h>
5.13 -//#include <LEDA/graph_alg.h>
5.14 -//#include <LEDA/dimacs.h>
5.15 -
5.16 -//#if defined(LEDA_NAMESPACE)
5.17 -//using namespace leda;
5.18 -//#endif
5.19 -
5.20 -#include <invalid.h>
5.21 -
5.22 -/// The namespace of HugoLib
5.23 -namespace hugo {
5.24 -
5.25 - // @defgroup empty_graph The LedaGraphWrapper class
5.26 - // @{
5.27 -
5.28 - /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
5.29 -
5.30 - /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
5.31 - /// and then the generic algorithms and wrappers of HUGO can be used
5.32 - /// with LEDA graphs.
5.33 - /// This class provides all the common features of a grapf structure,
5.34 - /// however completely without implementations or real data structures
5.35 - /// behind the interface.
5.36 - /// All graph algorithms should compile with this class, but it will not
5.37 - /// run properly, of course.
5.38 - ///
5.39 - /// It can be used for checking the interface compatibility,
5.40 - /// or it can serve as a skeleton of a new graph structure.
5.41 - ///
5.42 - /// Also, you will find here the full documentation of a certain graph
5.43 - /// feature, the documentation of a real graph imlementation
5.44 - /// like @ref ListGraph or
5.45 - /// @ref SmartGraph will just refer to this structure.
5.46 - template<typename Graph>
5.47 - class LedaGraphWrapper
5.48 - {
5.49 - Graph* _graph;
5.50 - public:
5.51 -
5.52 - //LedaGraphWrapper() { }
5.53 - LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
5.54 - LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
5.55 -
5.56 - template <typename T> class NodeMap;
5.57 - template <typename T> class EdgeMap;
5.58 -
5.59 - /// The base type of the node iterators.
5.60 - class Node {
5.61 - friend class LedaGraphWrapper;
5.62 - //friend class Edge;
5.63 - friend class EdgeIt;
5.64 - friend class InEdgeIt;
5.65 - friend class OutEdgeIt;
5.66 - protected:
5.67 - template <typename T> friend class NodeMap;
5.68 - leda_node _n;
5.69 - Node(leda_node __n) : _n(__n) { }
5.70 - public:
5.71 - /// @warning The default constructor sets the iterator
5.72 - /// to an undefined value.
5.73 - Node() {} //FIXME
5.74 - /// Initialize the iterator to be invalid
5.75 - Node(Invalid) : _n(0) { }
5.76 - //Node(const Node &) {}
5.77 - bool operator==(Node n) const { return _n==n._n; } //FIXME
5.78 - bool operator!=(Node n) const { return _n!=n._n; } //FIXME
5.79 - operator leda_node () { return _n; }
5.80 - };
5.81 -
5.82 - /// This iterator goes through each node.
5.83 - class NodeIt : public Node {
5.84 - public:
5.85 - /// @warning The default constructor sets the iterator
5.86 - /// to an undefined value.
5.87 - NodeIt() {} //FIXME
5.88 - /// Initialize the iterator to be invalid
5.89 - NodeIt(Invalid i) : Node(i) {}
5.90 - /// Sets the iterator to the first node of \c G.
5.91 - NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
5.92 - //NodeIt(const NodeIt &) {} //FIXME
5.93 - };
5.94 -
5.95 - /// The base type of the edge iterators.
5.96 - class Edge {
5.97 - friend class LedaGraphWrapper;
5.98 - protected:
5.99 - template <typename T> friend class EdgeMap;
5.100 - leda_edge _e;
5.101 - Edge(leda_edge __e) : _e(__e) { }
5.102 - public:
5.103 - /// @warning The default constructor sets the iterator
5.104 - /// to an undefined value.
5.105 - Edge() {} //FIXME
5.106 - /// Initialize the iterator to be invalid
5.107 - Edge(Invalid) : _e(0) {}
5.108 - //Edge(const Edge &) {}
5.109 - bool operator==(Edge e) const { return _e==e._e; } //FIXME
5.110 - bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
5.111 - operator leda_edge () { return _e; }
5.112 - };
5.113 -
5.114 - /// This iterator goes trought the outgoing edges of a certain graph.
5.115 -
5.116 - class OutEdgeIt : public Edge {
5.117 - public:
5.118 - /// @warning The default constructor sets the iterator
5.119 - /// to an undefined value.
5.120 - OutEdgeIt() {}
5.121 - /// Initialize the iterator to be invalid
5.122 - OutEdgeIt(Invalid i) : Edge(i) {}
5.123 - /// This constructor sets the iterator to first outgoing edge.
5.124 -
5.125 - /// This constructor set the iterator to the first outgoing edge of
5.126 - /// node
5.127 - ///@param n the node
5.128 - ///@param G the graph
5.129 - OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
5.130 - };
5.131 -
5.132 - class InEdgeIt : public Edge {
5.133 - public:
5.134 - /// @warning The default constructor sets the iterator
5.135 - /// to an undefined value.
5.136 - InEdgeIt() {}
5.137 - /// Initialize the iterator to be invalid
5.138 - InEdgeIt(Invalid i) : Edge(i) {}
5.139 - InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
5.140 - };
5.141 -
5.142 - // class SymEdgeIt : public Edge {};
5.143 - class EdgeIt : public Edge {
5.144 - public:
5.145 - /// @warning The default constructor sets the iterator
5.146 - /// to an undefined value.
5.147 - EdgeIt() {}
5.148 - /// Initialize the iterator to be invalid
5.149 - EdgeIt(Invalid i) : Edge(i) {}
5.150 - EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
5.151 - };
5.152 -
5.153 - /// First node of the graph.
5.154 -
5.155 - /// \post \c i and the return value will be the first node.
5.156 - ///
5.157 - NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
5.158 -
5.159 - /// The first outgoing edge.
5.160 - InEdgeIt &first(InEdgeIt &i, Node n) const {
5.161 - i=InEdgeIt(*this, n);
5.162 - return i;
5.163 - }
5.164 - /// The first incoming edge.
5.165 - OutEdgeIt &first(OutEdgeIt &i, Node n) const {
5.166 - i=OutEdgeIt(*this, n);
5.167 - return i;
5.168 - }
5.169 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
5.170 - /// The first edge of the Graph.
5.171 - EdgeIt &first(EdgeIt &i) const {
5.172 - i=EdgeIt(*this);
5.173 - return i; }
5.174 -
5.175 -// Node getNext(Node) const {}
5.176 -// InEdgeIt getNext(InEdgeIt) const {}
5.177 -// OutEdgeIt getNext(OutEdgeIt) const {}
5.178 -// //SymEdgeIt getNext(SymEdgeIt) const {}
5.179 -// EdgeIt getNext(EdgeIt) const {}
5.180 -
5.181 - /// Go to the next node.
5.182 - NodeIt &next(NodeIt &i) const {
5.183 - i._n=_graph->succ_node(i._n);
5.184 - return i;
5.185 - }
5.186 - /// Go to the next incoming edge.
5.187 - InEdgeIt &next(InEdgeIt &i) const {
5.188 - i._e=_graph->in_succ(i._e);
5.189 - return i;
5.190 - }
5.191 - /// Go to the next outgoing edge.
5.192 - OutEdgeIt &next(OutEdgeIt &i) const {
5.193 - i._e=_graph->adj_succ(i._e);
5.194 - return i;
5.195 - }
5.196 - //SymEdgeIt &next(SymEdgeIt &) const {}
5.197 - /// Go to the next edge.
5.198 - EdgeIt &next(EdgeIt &i) const {
5.199 - i._e=_graph->succ_edge(i._e);
5.200 - return i;
5.201 - }
5.202 -
5.203 -// template< typename It >
5.204 -// It first() const {
5.205 -// It e;
5.206 -// first(e);
5.207 -// return e;
5.208 -// }
5.209 -
5.210 -// template< typename It >
5.211 -// It first(Node v) const {
5.212 -// It e;
5.213 -// first(e, v);
5.214 -// return e;
5.215 -// }
5.216 -
5.217 - ///Gives back the head node of an edge.
5.218 - Node head(Edge e) const {
5.219 - return Node(_graph->target(e._e));
5.220 - }
5.221 - ///Gives back the tail node of an edge.
5.222 - Node tail(Edge e) const {
5.223 - return Node(_graph->source(e._e));
5.224 - }
5.225 -
5.226 - Node aNode(InEdgeIt e) const { return head(e); }
5.227 - Node aNode(OutEdgeIt e) const { return tail(e); }
5.228 - // Node aNode(SymEdgeIt) const {}
5.229 -
5.230 - Node bNode(InEdgeIt e) const { return tail(e); }
5.231 - Node bNode(OutEdgeIt e) const { return head(e); }
5.232 - // Node bNode(SymEdgeIt) const {}
5.233 -
5.234 - /// Checks if a node iterator is valid
5.235 - bool valid(Node n) const { return n._n; }
5.236 - /// Checks if an edge iterator is valid
5.237 - bool valid(Edge e) const { return e._e; }
5.238 -
5.239 - ///Gives back the \e id of a node.
5.240 - int id(Node n) const { return n._n->id(); }
5.241 - ///Gives back the \e id of an edge.
5.242 - int id(Edge e) const { return e._e->id(); }
5.243 -
5.244 - //void setInvalid(Node &) const {};
5.245 - //void setInvalid(Edge &) const {};
5.246 -
5.247 - Node addNode() const { return Node(_graph->new_node()); }
5.248 - Edge addEdge(Node tail, Node head) const {
5.249 - return Edge(_graph->new_edge(tail._n, head._n));
5.250 - }
5.251 -
5.252 - void erase(Node n) const { _graph->del_node(n._n); }
5.253 - void erase(Edge e) const { _graph->del_edge(e._e); }
5.254 -
5.255 - void clear() const { _graph->clear(); }
5.256 -
5.257 - int nodeNum() const { return _graph->number_of_nodes(); }
5.258 - int edgeNum() const { return _graph->number_of_edges(); }
5.259 -
5.260 - ///Read/write map from the nodes to type \c T.
5.261 - template<typename T> class NodeMap
5.262 - {
5.263 - leda_node_map<T> leda_stuff;
5.264 - public:
5.265 - typedef T ValueType;
5.266 - typedef Node KeyType;
5.267 -
5.268 - NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
5.269 - NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
5.270 -
5.271 - void set(Node i, T t) { leda_stuff[i._n]=t; }
5.272 - T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
5.273 - T &operator[](Node i) { return leda_stuff[i._n]; }
5.274 - const T &operator[](Node i) const { return leda_stuff[i._n]; }
5.275 -
5.276 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
5.277 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
5.278 - };
5.279 -
5.280 - ///Read/write map from the edges to type \c T.
5.281 - template<typename T> class EdgeMap
5.282 - {
5.283 - leda_edge_map<T> leda_stuff;
5.284 - public:
5.285 - typedef T ValueType;
5.286 - typedef Edge KeyType;
5.287 -
5.288 - EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
5.289 - EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
5.290 -
5.291 - void set(Edge i, T t) { leda_stuff[i._e]=t; }
5.292 - T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
5.293 - T &operator[](Edge i) { return leda_stuff[i._e]; }
5.294 - const T &operator[](Edge i) const { return leda_stuff[i._e]; }
5.295 -
5.296 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
5.297 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
5.298 - };
5.299 -
5.300 - };
5.301 -
5.302 - // @}
5.303 -
5.304 -} //namespace hugo
5.305 -
5.306 -
5.307 -
5.308 -// class EmptyBipGraph : public EmptyGraph
5.309 -// {
5.310 -// class ANode {};
5.311 -// class BNode {};
5.312 -
5.313 -// ANode &next(ANode &) {}
5.314 -// BNode &next(BNode &) {}
5.315 -
5.316 -// ANode &getFirst(ANode &) const {}
5.317 -// BNode &getFirst(BNode &) const {}
5.318 -
5.319 -// enum NodeClass { A = 0, B = 1 };
5.320 -// NodeClass getClass(Node n) {}
5.321 -
5.322 -// }
5.323 -
5.324 -#endif // HUGO_LEDA_GRAPH_WRAPPER_H