Changeset 409:7ab7f083760a in lemon-0.x for src
- Timestamp:
- 04/26/04 11:54:24 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@542
- Location:
- src/work
- Files:
-
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/list_graph.h
r389 r409 370 370 371 371 friend std::ostream& operator<<(std::ostream& os, const Node& i) { 372 os << i.node->id; return os; 372 if (i.valid()) 373 os << i.node->id; 374 else 375 os << "invalid"; 376 return os; 373 377 } 374 378 friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 375 os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 379 if (i.valid()) 380 os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 381 else 382 os << "invalid"; 376 383 return os; 377 384 } -
src/work/makefile
r393 r409 1 1 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos} 2 CXXFLAGS = -g -O 0-W -Wall $(INCLUDEDIRS) -ansi -pedantic2 CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic 3 3 4 4 BINARIES ?= bin_heap_demo … … 6 6 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam 7 7 # ismert rendszeren :-) (Misi) 8 #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++)9 CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)8 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++) 9 #CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++) 10 10 CC := $(CXX) 11 11 -
src/work/marci/bfs_iterator.h
r389 r409 29 29 own_reached_map(true) { } 30 30 ~BfsIterator() { if (own_reached_map) delete &reached; } 31 //s is marcked reached. 32 //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe. 33 //is the queue is not empty, then is it pushed. 31 34 void pushAndSetReached(Node s) { 32 35 reached.set(s, true); … … 81 84 } 82 85 bool finished() const { return bfs_queue.empty(); } 83 operator OutEdgeIt 86 operator OutEdgeIt() const { return actual_edge; } 84 87 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 85 88 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } … … 89 92 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } 90 93 }; 94 95 /// Bfs searches from s for the nodes wich are not marked in 96 /// reachedmap 97 template <typename Graph, 98 typename ReachedMap=typename Graph::template NodeMap<bool>, 99 typename PredMap 100 =typename Graph::template NodeMap<typename Graph::Edge>, 101 typename DistMap=typename Graph::template NodeMap<int> > 102 class Bfs : public BfsIterator<Graph, ReachedMap> { 103 typedef BfsIterator<Graph, ReachedMap> Parent; 104 protected: 105 typedef typename Parent::Node Node; 106 PredMap& pred; 107 DistMap& dist; 108 public: 109 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } 110 //s is marked to be reached and pushed in the bfs queue. 111 //if the queue is empty, then the first out-edge is processed 112 //If s was not marked previously, then 113 //in addition its pred is set to be INVALID, and dist to 0. 114 //if s was marked previuosly, then it is simply pushed. 115 void push(Node s) { 116 if (this->reached[s]) { 117 Parent::pushAndSetReached(s); 118 } else { 119 Parent::pushAndSetReached(s); 120 pred.set(s, INVALID); 121 dist.set(s, 0); 122 } 123 } 124 void run(Node s) { 125 push(s); 126 while (!this->finished()) this->operator++(); 127 } 128 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { 129 Parent::operator++(); 130 if (this->graph->valid(actual_edge) && this->b_node_newly_reached) { 131 pred.set(s, actual_edge); 132 dist.set(s, dist[this->aNode()]); 133 } 134 return *this; 135 } 136 const PredMap& getPredMap() const { return pred; } 137 const DistMap& getDistMap() const { return dist; } 138 }; 91 139 92 140 template <typename Graph, /*typename OutEdgeIt,*/ … … 143 191 } 144 192 bool finished() const { return dfs_stack.empty(); } 145 operator OutEdgeIt 193 operator OutEdgeIt() const { return actual_edge; } 146 194 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 147 195 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } -
src/work/marci/bipartite_graph_wrapper_test.cc
r393 r409 25 25 26 26 Graph g; 27 //Node s, t; 28 //Graph::EdgeMap<int> cap(g); 29 //readDimacsMaxFlow(std::cin, g, s, t, cap); 30 std::vector<Graph::Node> s_nodes; 31 std::vector<Graph::Node> t_nodes; 32 for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode()); 33 for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode()); 34 g.addEdge(s_nodes[0], t_nodes[2]); 35 g.addEdge(t_nodes[1], s_nodes[2]); 27 // std::vector<Graph::Node> s_nodes; 28 // std::vector<Graph::Node> t_nodes; 29 // for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode()); 30 // for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode()); 31 // g.addEdge(s_nodes[0], t_nodes[2]); 32 // g.addEdge(t_nodes[1], s_nodes[2]); 33 // g.addEdge(s_nodes[0], t_nodes[1]); 34 35 // Graph::NodeMap<int> ref_map(g, -1); 36 // IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 37 // for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false); 38 // for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true); 39 40 std::vector<Graph::Node> nodes; 41 for (int i=0; i<3; ++i) nodes.push_back(g.addNode()); 42 for (int i=3; i<6; ++i) nodes.push_back(g.addNode()); 43 g.addEdge(nodes[0], nodes[3+2]); 44 g.addEdge(nodes[3+1], nodes[2]); 45 g.addEdge(nodes[0], nodes[3+1]); 36 46 37 47 Graph::NodeMap<int> ref_map(g, -1); 38 48 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 39 for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false); 40 for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true); 49 for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false); 50 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true); 51 52 Graph::Node u; 53 std::cout << "These nodes will be in S:\n"; 54 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 55 //irni 1etlen FOR_EACH-csel. 56 for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 57 std::cout << u << " "; 58 std::cout << "\n"; 59 std::cout << "These nodes will be in T:\n"; 60 for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 61 std::cout << u << " "; 62 std::cout << "\n"; 63 41 64 typedef BipartiteGraphWrapper<Graph> BGW; 42 65 BGW bgw(g, bipartite_map); 66 67 std::cout << "Nodes by NodeIt:\n"; 68 FOR_EACH_LOC(BGW::NodeIt, n, bgw) { 69 std::cout << n << " "; 70 } 71 std::cout << "\n"; 72 std::cout << "Nodes in S by ClassNodeIt:\n"; 73 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { 74 std::cout << n << " "; 75 } 76 std::cout << "\n"; 77 std::cout << "Nodes in T by ClassNodeIt:\n"; 78 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { 79 std::cout << n << " "; 80 } 81 std::cout << "\n"; 82 std::cout << "Edges of the bipartite graph:\n"; 43 83 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { 44 84 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; … … 59 99 s=g.first(si); 60 100 bfs.pushAndSetReached(BGW::Node(s)); 61 while (!bfs.finished()) ++bfs;101 while (!bfs.finished()) { ++bfs; } 62 102 63 BGW::EdgeMap<bool> cap(bgw); 64 BGW::EdgeMap<bool> flow1(bgw); 103 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 104 std::cout << "out-edges of " << n << ":\n"; 105 FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 106 std::cout << " " << e << "\n"; 107 std::cout << " aNode: " << stgw.aNode(e) << "\n"; 108 std::cout << " bNode: " << stgw.bNode(e) << "\n"; 109 } 110 std::cout << "in-edges of " << n << ":\n"; 111 FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 112 std::cout << " " << e << "\n"; 113 std::cout << " aNode: " << stgw.aNode(e) << "\n"; 114 std::cout << " bNode: " << stgw.bNode(e) << "\n"; 115 } 116 } 117 std::cout << "Edges of the stGraphWrapper:\n"; 118 FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 119 std::cout << " " << n << "\n"; 120 } 65 121 66 typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 67 RBGW; 68 RBGW rbgw(bgw, cap, flow1); 69 RBGW::NodeMap<int> u(rbgw); 122 stGW::NodeMap<bool> b(stgw); 123 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 124 std::cout << n << ": " << b[n] <<"\n"; 125 } 126 127 std::cout << "Bfs from s: \n"; 128 BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); 129 bfs_stgw.pushAndSetReached(stgw.S_NODE); 130 while (!bfs_stgw.finished()) { 131 std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; 132 ++bfs_stgw; 133 } 70 134 71 72 135 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 73 136 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 74 max_flow_test.augmentOnShortestPath(); 75 max_flow_test.augmentOnShortestPath(); 137 while (max_flow_test.augmentOnShortestPath()) { } 76 138 77 139 std::cout << max_flow_test.flowValue() << std::endl; -
src/work/marci/edmonds_karp.h
r389 r409 323 323 public: 324 324 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } 325 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } 325 void set(const typename MapGraphWrapper::Node& n, int a) { 326 dist.set(n, a); 327 } 326 328 int operator[](const typename MapGraphWrapper::Node& n) 327 329 { return dist[n]; } -
src/work/marci/for_each_macros.h
r333 r409 5 5 namespace hugo { 6 6 7 #define FOR_EACH (e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))8 #define FOR_EACH_INC (e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))7 #define FOR_EACH_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e))) 8 #define FOR_EACH_INC_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e))) 9 9 10 #define FOR_EACH_EDGE (e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))11 #define FOR_EACH_NODE (e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))12 #define FOR_EACH_INEDGE (e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))13 #define FOR_EACH_OUTEDGE (e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))10 #define FOR_EACH_EDGE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e))) 11 #define FOR_EACH_NODE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e))) 12 #define FOR_EACH_INEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e))) 13 #define FOR_EACH_OUTEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e))) 14 14 15 15 // template<typename It, typename Graph> -
src/work/marci/graph_wrapper.h
r406 r409 924 924 925 925 public: 926 static const bool S_CLASS=false; 927 static const bool T_CLASS=true; 926 //marci 927 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg 928 //static const bool S_CLASS=false; 929 //static const bool T_CLASS=true; 928 930 931 bool S_CLASS; 932 bool T_CLASS; 933 929 934 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 930 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {931 }935 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), 936 S_CLASS(false), T_CLASS(true) { } 932 937 typedef typename GraphWrapper<Graph>::Node Node; 933 938 //using GraphWrapper<Graph>::NodeIt; … … 1103 1108 //invalid, 3, invalid) 1104 1109 template <typename T> class NodeMap; 1105 template <typename T > class EdgeMap;1110 template <typename T, typename Parent> class EdgeMap; 1106 1111 1107 1112 // template <typename T> friend class NodeMap; … … 1142 1147 static_cast<typename Graph::Node>(u)!= 1143 1148 static_cast<typename Graph::Node>(v)); 1144 } 1149 } 1150 friend std::ostream& operator<<(std::ostream& os, const Node& i); 1145 1151 int getSpec() const { return spec; } 1146 1152 }; 1153 1147 1154 class NodeIt { 1148 1155 friend class GraphWrapper<Graph>; … … 1156 1163 NodeIt(const Invalid& i) : n(i), spec(3) { } 1157 1164 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 1158 if (!_G ->valid(n)) spec=1;1165 if (!_G.graph->valid(n)) spec=1; 1159 1166 } 1160 1167 operator Node() const { return Node(n, spec); } 1161 1168 }; 1169 1162 1170 class Edge : public Graph::Edge { 1163 1171 friend class GraphWrapper<Graph>; 1164 1172 friend class stGraphWrapper<Graph>; 1165 template <typename T > friend class EdgeMap;1173 template <typename T, typename Parent> friend class EdgeMap; 1166 1174 int spec; 1167 1175 typename Graph::Node n; … … 1185 1193 u.n!=v.n); 1186 1194 } 1195 friend std::ostream& operator<<(std::ostream& os, const Edge& i); 1187 1196 int getSpec() const { return spec; } 1188 1197 }; 1198 1189 1199 class OutEdgeIt { 1190 1200 friend class GraphWrapper<Graph>; … … 1230 1240 operator Edge() const { return Edge(e, spec, n); } 1231 1241 }; 1242 1232 1243 class InEdgeIt { 1233 1244 friend class GraphWrapper<Graph>; … … 1262 1273 spec=3; 1263 1274 n=INVALID; 1275 break; 1264 1276 case 2: 1265 1277 e=INVALID; 1266 spec= 1;1278 spec=2; 1267 1279 _G.graph->first(n, T_CLASS); //vmi->t; 1268 1280 if (!_G.graph->valid(n)) spec=3; //Ha T ures … … 1272 1284 operator Edge() const { return Edge(e, spec, n); } 1273 1285 }; 1286 1274 1287 class EdgeIt { 1275 1288 friend class GraphWrapper<Graph>; … … 1335 1348 switch (i.spec) { 1336 1349 case 0: //normal edge 1337 this->graph->aNode(i.e);1350 v=this->graph->aNode(i.e); 1338 1351 this->graph->next(i.e); 1339 1352 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk … … 1448 1461 bool valid(const Edge& e) const { return (e.spec<3); } 1449 1462 1450 // int nodeNum() const { return this->graph->nodeNum(); } 1451 // int edgeNum() const { return this->graph->edgeNum(); } 1463 int nodeNum() const { return this->graph->nodeNum()+2; } 1464 int edgeNum() const { 1465 return this->graph->edgeNum()+this->graph->nodeNum(); 1466 } 1452 1467 1453 1468 Node aNode(const OutEdgeIt& e) const { return tail(e); } … … 1455 1470 Node bNode(const OutEdgeIt& e) const { return head(e); } 1456 1471 Node bNode(const InEdgeIt& e) const { return tail(e); } 1457 1472 1473 void addNode() const { } 1474 void addEdge() const { } 1475 1458 1476 // Node addNode() const { return Node(this->graph->addNode()); } 1459 1477 // Edge addEdge(const Node& tail, const Node& head) const { … … 1469 1487 T s_value, t_value; 1470 1488 public: 1471 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G) { } 1489 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 1490 s_value(), 1491 t_value() { } 1472 1492 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 1473 1493 s_value(a), … … 1503 1523 }; 1504 1524 1505 template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 1506 typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; 1525 template<typename T, 1526 typename Parent= 1527 typename GraphWrapper<Graph>::template EdgeMap<T> > 1528 class EdgeMap : public Parent { 1529 //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; 1507 1530 typename GraphWrapper<Graph>::template NodeMap<T> node_value; 1508 1531 public: … … 1528 1551 switch (e.spec) { 1529 1552 case 0: 1530 GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);1553 Parent::set(e, t); 1531 1554 break; 1532 1555 case 1: … … 1540 1563 } 1541 1564 }; 1565 1566 // template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 1567 // typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; 1568 // typename GraphWrapper<Graph>::template NodeMap<T> node_value; 1569 // public: 1570 // EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 1571 // node_value(_G) { } 1572 // EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 1573 // node_value(_G, a) { } 1574 // T operator[](const Edge& e) const { 1575 // switch (e.spec) { 1576 // case 0: 1577 // return Parent::operator[](e); 1578 // break; 1579 // case 1: 1580 // return node_value[e.n]; 1581 // break; 1582 // case 2: 1583 // default: 1584 // return node_value[e.n]; 1585 // break; 1586 // } 1587 // } 1588 // void set(const Edge& e, T t) { 1589 // switch (e.spec) { 1590 // case 0: 1591 // GraphWrapper<Graph>::template EdgeMap<T>::set(e, t); 1592 // break; 1593 // case 1: 1594 // node_value.set(e.n, t); 1595 // break; 1596 // case 2: 1597 // default: 1598 // node_value.set(e.n, t); 1599 // break; 1600 // } 1601 // } 1602 // }; 1603 1604 friend std::ostream& operator<<(std::ostream& os, const Node& i) { 1605 os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 1606 return os; 1607 } 1608 friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 1609 os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 1610 " node: " << i.n << ")"; 1611 return os; 1612 } 1613 1542 1614 }; 1543 1615 -
src/work/marci/leda_graph_wrapper.h
r198 r409 23 23 // @{ 24 24 25 /// A n empty graph class.25 /// A graph wrapperstructure for wrapping LEDA graphs in HUGO. 26 26 27 /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph 28 /// and then the generic algorithms and wrappers of HUGO can be used 29 /// with LEDA graphs. 27 30 /// This class provides all the common features of a grapf structure, 28 31 /// however completely without implementations or real data structures … … 195 198 } 196 199 197 template< typename It >198 It first() const {199 It e;200 first(e);201 return e;202 }203 204 template< typename It >205 It first(Node v) const {206 It e;207 first(e, v);208 return e;209 }200 // template< typename It > 201 // It first() const { 202 // It e; 203 // first(e); 204 // return e; 205 // } 206 207 // template< typename It > 208 // It first(Node v) const { 209 // It e; 210 // first(e, v); 211 // return e; 212 // } 210 213 211 214 ///Gives back the head node of an edge. -
src/work/marci/macro_test.cc
r330 r409 15 15 Graph::Node n2=g.addNode(); 16 16 Graph::NodeIt n; 17 FOR_EACH (n, g) {17 FOR_EACH_GLOB(n, g) { 18 18 std::cout << g.id(n) << " "; 19 19 } -
src/work/marci/makefile
r389 r409 10 10 11 11 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 12 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test 12 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try 13 13 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda 14 14
Note: See TracChangeset
for help on using the changeset viewer.