Changeset 243:a85fd87460e3 in lemon0.x for src/work
 Timestamp:
 03/25/04 10:42:59 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@342
 Location:
 src/work
 Files:

 5 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.h
r174 r243 10 10 namespace hugo { 11 11 12 template <typename Graph>13 struct bfs {14 typedef typename Graph::Node Node;15 typedef typename Graph::Edge Edge;16 typedef typename Graph::NodeIt NodeIt;17 typedef typename Graph::OutEdgeIt OutEdgeIt;18 Graph& G;19 Node s;20 typename Graph::NodeMap<bool> reached;21 typename Graph::NodeMap<Edge> pred;22 typename Graph::NodeMap<int> dist;23 std::queue<Node> bfs_queue;24 bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {25 bfs_queue.push(s);26 for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)27 reached.set(i, false);28 reached.set(s, true);29 dist.set(s, 0);30 }12 // template <typename Graph> 13 // struct bfs { 14 // typedef typename Graph::Node Node; 15 // typedef typename Graph::Edge Edge; 16 // typedef typename Graph::NodeIt NodeIt; 17 // typedef typename Graph::OutEdgeIt OutEdgeIt; 18 // Graph& G; 19 // Node s; 20 // typename Graph::NodeMap<bool> reached; 21 // typename Graph::NodeMap<Edge> pred; 22 // typename Graph::NodeMap<int> dist; 23 // std::queue<Node> bfs_queue; 24 // bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 25 // bfs_queue.push(s); 26 // for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) 27 // reached.set(i, false); 28 // reached.set(s, true); 29 // dist.set(s, 0); 30 // } 31 31 32 void run() {33 while (!bfs_queue.empty()) {34 Node v=bfs_queue.front();35 OutEdgeIt e=G.template first<OutEdgeIt>(v);36 bfs_queue.pop();37 for( ; e.valid(); ++e) {38 Node w=G.bNode(e);39 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;40 if (!reached.get(w)) {41 std::cout << G.id(w) << " is newly reached :)" << std::endl;42 bfs_queue.push(w);43 dist.set(w, dist.get(v)+1);44 pred.set(w, e);45 reached.set(w, true);46 } else {47 std::cout << G.id(w) << " is already reached" << std::endl;48 }49 }50 }51 }52 };32 // void run() { 33 // while (!bfs_queue.empty()) { 34 // Node v=bfs_queue.front(); 35 // OutEdgeIt e=G.template first<OutEdgeIt>(v); 36 // bfs_queue.pop(); 37 // for( ; e.valid(); ++e) { 38 // Node w=G.bNode(e); 39 // std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; 40 // if (!reached.get(w)) { 41 // std::cout << G.id(w) << " is newly reached :)" << std::endl; 42 // bfs_queue.push(w); 43 // dist.set(w, dist.get(v)+1); 44 // pred.set(w, e); 45 // reached.set(w, true); 46 // } else { 47 // std::cout << G.id(w) << " is already reached" << std::endl; 48 // } 49 // } 50 // } 51 // } 52 // }; 53 53 54 54 // template <typename Graph> … … 545 545 546 546 547 template <typename Graph, typename OutEdgeIt,548 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >549 class BfsIterator4 {550 typedef typename Graph::Node Node;551 const Graph& G;552 std::queue<Node> bfs_queue;553 ReachedMap& reached;554 bool b_node_newly_reached;555 OutEdgeIt actual_edge;556 bool own_reached_map;557 public:558 BfsIterator4(const Graph& _G, ReachedMap& _reached) :559 G(_G), reached(_reached),560 own_reached_map(false) { }561 BfsIterator4(const Graph& _G) :562 G(_G), reached(*(new ReachedMap(G /*, false*/))),563 own_reached_map(true) { }564 ~BfsIterator4() { if (own_reached_map) delete &reached; }565 void pushAndSetReached(Node s) {566 //std::cout << "mimi" << &reached << std::endl;567 reached.set(s, true);568 //std::cout << "mumus" << std::endl;569 if (bfs_queue.empty()) {570 //std::cout << "bibi1" << std::endl;571 bfs_queue.push(s);572 //std::cout << "zizi" << std::endl;573 G./*getF*/first(actual_edge, s);574 //std::cout << "kiki" << std::endl;575 if (G.valid(actual_edge)/*.valid()*/) {576 Node w=G.bNode(actual_edge);577 if (!reached.get(w)) {578 bfs_queue.push(w);579 reached.set(w, true);580 b_node_newly_reached=true;581 } else {582 b_node_newly_reached=false;583 }584 }585 } else {586 //std::cout << "bibi2" << std::endl;587 bfs_queue.push(s);588 }589 }590 BfsIterator4<Graph, OutEdgeIt, ReachedMap>&591 operator++() {592 if (G.valid(actual_edge)/*.valid()*/) {593 /*++*/G.next(actual_edge);594 if (G.valid(actual_edge)/*.valid()*/) {595 Node w=G.bNode(actual_edge);596 if (!reached.get(w)) {597 bfs_queue.push(w);598 reached.set(w, true);599 b_node_newly_reached=true;600 } else {601 b_node_newly_reached=false;602 }603 }604 } else {605 bfs_queue.pop();606 if (!bfs_queue.empty()) {607 G./*getF*/first(actual_edge, bfs_queue.front());608 if (G.valid(actual_edge)/*.valid()*/) {609 Node w=G.bNode(actual_edge);610 if (!reached.get(w)) {611 bfs_queue.push(w);612 reached.set(w, true);613 b_node_newly_reached=true;614 } else {615 b_node_newly_reached=false;616 }617 }618 }619 }620 return *this;621 }622 bool finished() const { return bfs_queue.empty(); }623 operator OutEdgeIt () const { return actual_edge; }624 bool isBNodeNewlyReached() const { return b_node_newly_reached; }625 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }626 Node aNode() const { return bfs_queue.front(); }627 Node bNode() const { return G.bNode(actual_edge); }628 const ReachedMap& getReachedMap() const { return reached; }629 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }630 };547 // template <typename Graph, typename OutEdgeIt, 548 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 549 // class BfsIterator4 { 550 // typedef typename Graph::Node Node; 551 // const Graph& G; 552 // std::queue<Node> bfs_queue; 553 // ReachedMap& reached; 554 // bool b_node_newly_reached; 555 // OutEdgeIt actual_edge; 556 // bool own_reached_map; 557 // public: 558 // BfsIterator4(const Graph& _G, ReachedMap& _reached) : 559 // G(_G), reached(_reached), 560 // own_reached_map(false) { } 561 // BfsIterator4(const Graph& _G) : 562 // G(_G), reached(*(new ReachedMap(G /*, false*/))), 563 // own_reached_map(true) { } 564 // ~BfsIterator4() { if (own_reached_map) delete &reached; } 565 // void pushAndSetReached(Node s) { 566 // //std::cout << "mimi" << &reached << std::endl; 567 // reached.set(s, true); 568 // //std::cout << "mumus" << std::endl; 569 // if (bfs_queue.empty()) { 570 // //std::cout << "bibi1" << std::endl; 571 // bfs_queue.push(s); 572 // //std::cout << "zizi" << std::endl; 573 // G./*getF*/first(actual_edge, s); 574 // //std::cout << "kiki" << std::endl; 575 // if (G.valid(actual_edge)/*.valid()*/) { 576 // Node w=G.bNode(actual_edge); 577 // if (!reached.get(w)) { 578 // bfs_queue.push(w); 579 // reached.set(w, true); 580 // b_node_newly_reached=true; 581 // } else { 582 // b_node_newly_reached=false; 583 // } 584 // } 585 // } else { 586 // //std::cout << "bibi2" << std::endl; 587 // bfs_queue.push(s); 588 // } 589 // } 590 // BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 591 // operator++() { 592 // if (G.valid(actual_edge)/*.valid()*/) { 593 // /*++*/G.next(actual_edge); 594 // if (G.valid(actual_edge)/*.valid()*/) { 595 // Node w=G.bNode(actual_edge); 596 // if (!reached.get(w)) { 597 // bfs_queue.push(w); 598 // reached.set(w, true); 599 // b_node_newly_reached=true; 600 // } else { 601 // b_node_newly_reached=false; 602 // } 603 // } 604 // } else { 605 // bfs_queue.pop(); 606 // if (!bfs_queue.empty()) { 607 // G./*getF*/first(actual_edge, bfs_queue.front()); 608 // if (G.valid(actual_edge)/*.valid()*/) { 609 // Node w=G.bNode(actual_edge); 610 // if (!reached.get(w)) { 611 // bfs_queue.push(w); 612 // reached.set(w, true); 613 // b_node_newly_reached=true; 614 // } else { 615 // b_node_newly_reached=false; 616 // } 617 // } 618 // } 619 // } 620 // return *this; 621 // } 622 // bool finished() const { return bfs_queue.empty(); } 623 // operator OutEdgeIt () const { return actual_edge; } 624 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } 625 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 626 // Node aNode() const { return bfs_queue.front(); } 627 // Node bNode() const { return G.bNode(actual_edge); } 628 // const ReachedMap& getReachedMap() const { return reached; } 629 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; } 630 // }; 631 631 632 632 … … 718 718 }; 719 719 720 template <typename Graph, typename OutEdgeIt,721 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >722 class DfsIterator4 {723 typedef typename Graph::Node Node;724 const Graph& G;725 std::stack<OutEdgeIt> dfs_stack;726 bool b_node_newly_reached;727 OutEdgeIt actual_edge;728 Node actual_node;729 ReachedMap& reached;730 bool own_reached_map;731 public:732 DfsIterator4(const Graph& _G, ReachedMap& _reached) :733 G(_G), reached(_reached),734 own_reached_map(false) { }735 DfsIterator4(const Graph& _G) :736 G(_G), reached(*(new ReachedMap(G /*, false*/))),737 own_reached_map(true) { }738 ~DfsIterator4() { if (own_reached_map) delete &reached; }739 void pushAndSetReached(Node s) {740 actual_node=s;741 reached.set(s, true);742 dfs_stack.push(G.template first<OutEdgeIt>(s));743 }744 DfsIterator4<Graph, OutEdgeIt, ReachedMap>&745 operator++() {746 actual_edge=dfs_stack.top();747 //actual_node=G.aNode(actual_edge);748 if (G.valid(actual_edge)/*.valid()*/) {749 Node w=G.bNode(actual_edge);750 actual_node=w;751 if (!reached.get(w)) {752 dfs_stack.push(G.template first<OutEdgeIt>(w));753 reached.set(w, true);754 b_node_newly_reached=true;755 } else {756 actual_node=G.aNode(actual_edge);757 /*++*/G.next(dfs_stack.top());758 b_node_newly_reached=false;759 }760 } else {761 //actual_node=G.aNode(dfs_stack.top());762 dfs_stack.pop();763 }764 return *this;765 }766 bool finished() const { return dfs_stack.empty(); }767 operator OutEdgeIt () const { return actual_edge; }768 bool isBNodeNewlyReached() const { return b_node_newly_reached; }769 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }770 Node aNode() const { return actual_node; /*FIXME*/}771 Node bNode() const { return G.bNode(actual_edge); }772 const ReachedMap& getReachedMap() const { return reached; }773 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }774 };720 // template <typename Graph, typename OutEdgeIt, 721 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 722 // class DfsIterator4 { 723 // typedef typename Graph::Node Node; 724 // const Graph& G; 725 // std::stack<OutEdgeIt> dfs_stack; 726 // bool b_node_newly_reached; 727 // OutEdgeIt actual_edge; 728 // Node actual_node; 729 // ReachedMap& reached; 730 // bool own_reached_map; 731 // public: 732 // DfsIterator4(const Graph& _G, ReachedMap& _reached) : 733 // G(_G), reached(_reached), 734 // own_reached_map(false) { } 735 // DfsIterator4(const Graph& _G) : 736 // G(_G), reached(*(new ReachedMap(G /*, false*/))), 737 // own_reached_map(true) { } 738 // ~DfsIterator4() { if (own_reached_map) delete &reached; } 739 // void pushAndSetReached(Node s) { 740 // actual_node=s; 741 // reached.set(s, true); 742 // dfs_stack.push(G.template first<OutEdgeIt>(s)); 743 // } 744 // DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 745 // operator++() { 746 // actual_edge=dfs_stack.top(); 747 // //actual_node=G.aNode(actual_edge); 748 // if (G.valid(actual_edge)/*.valid()*/) { 749 // Node w=G.bNode(actual_edge); 750 // actual_node=w; 751 // if (!reached.get(w)) { 752 // dfs_stack.push(G.template first<OutEdgeIt>(w)); 753 // reached.set(w, true); 754 // b_node_newly_reached=true; 755 // } else { 756 // actual_node=G.aNode(actual_edge); 757 // /*++*/G.next(dfs_stack.top()); 758 // b_node_newly_reached=false; 759 // } 760 // } else { 761 // //actual_node=G.aNode(dfs_stack.top()); 762 // dfs_stack.pop(); 763 // } 764 // return *this; 765 // } 766 // bool finished() const { return dfs_stack.empty(); } 767 // operator OutEdgeIt () const { return actual_edge; } 768 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } 769 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 770 // Node aNode() const { return actual_node; /*FIXME*/} 771 // Node bNode() const { return G.bNode(actual_edge); } 772 // const ReachedMap& getReachedMap() const { return reached; } 773 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 774 // }; 775 775 776 776 template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
src/work/edmonds_karp.h
r206 r243 320 320 321 321 typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 BfsIterator 4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);322 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); 323 323 324 324 bfs.pushAndSetReached(s); … … 363 363 __augment=false; 364 364 //computing blocking flow with dfs 365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;366 DfsIterator 4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);365 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 367 367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 368 pred.set(sF, typename MutableGraph::Edge(INVALID)); … … 421 421 //bfs for distances on the residual graph 422 422 typedef typename AugGraph::NodeMap<bool> ReachedMap; 423 BfsIterator 4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);423 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); 424 424 bfs.pushAndSetReached(s); 425 425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's … … 466 466 __augment=false; 467 467 //computing blocking flow with dfs 468 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;469 DfsIterator 4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);468 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 469 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 470 470 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 471 471 pred.set(sF, typename MutableGraph::Edge(INVALID)); … … 528 528 529 529 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 530 BfsIterator 4<530 BfsIterator5< 531 531 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 532 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,532 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 533 533 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 534 534 … … 553 553 //computing blocking flow with dfs 554 554 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 555 DfsIterator 4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >555 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 556 556 dfs(res_graph); 557 557 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); … … 855 855 856 856 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 857 BfsIterator 4<857 BfsIterator5< 858 858 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 859 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,859 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 860 860 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 861 861 … … 895 895 //computing blocking flow with dfs 896 896 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 897 DfsIterator 4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >897 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 898 898 dfs(res_graph); 899 899 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 
src/work/makefile
r213 r243 2 2 CXXFLAGS = g O Wall $(INCLUDEDIRS) ansi pedantic 3 3 4 BINARIES ?= bin_heap_demo marci_graph_demoiterator_bfs_demo4 BINARIES ?= bin_heap_demo iterator_bfs_demo 5 5 6 6 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam 
src/work/marci/edmonds_karp_demo.cc
r206 r243 35 35 typedef ListGraph MutableGraph; 36 36 37 typedef SmartGraph Graph;38 //typedef ListGraph Graph;37 //typedef SmartGraph Graph; 38 typedef ListGraph Graph; 39 39 typedef Graph::Node Node; 40 40 typedef Graph::EdgeIt EdgeIt; … … 86 86 87 87 { 88 std::cout << "SmartGraph..." << std::endl;88 //std::cout << "SmartGraph..." << std::endl; 89 89 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 90 90 Graph::EdgeMap<int> flow(G); //0 flow … … 115 115 116 116 { 117 std::cout << "SmartGraph..." << std::endl;117 //std::cout << "SmartGraph..." << std::endl; 118 118 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; 119 119 Graph::EdgeMap<int> flow(G); //0 flow 
src/work/marci_graph_demo.cc
r168 r243 3 3 #include <string> 4 4 5 #include <list_graph.h h>6 #include <bfs_iterator.h h>7 #include <edmonds_karp.h h>5 #include <list_graph.h> 6 #include <bfs_iterator.h> 7 #include <edmonds_karp.h> 8 8 9 9 using namespace hugo; … … 11 11 int main (int, char*[]) 12 12 { 13 typedef ListGraph::Node Node; 14 typedef ListGraph::Edge Edge; 13 15 typedef ListGraph::NodeIt NodeIt; 14 16 typedef ListGraph::EdgeIt EdgeIt; 15 typedef ListGraph::EachNodeIt EachNodeIt;16 typedef ListGraph::EachEdgeIt EachEdgeIt;17 17 typedef ListGraph::OutEdgeIt OutEdgeIt; 18 18 typedef ListGraph::InEdgeIt InEdgeIt; 19 19 typedef ListGraph::SymEdgeIt SymEdgeIt; 20 20 ListGraph G; 21 std::vector<Node It> vector_of_NodeIts;22 for(int i=0; i!=8; ++i) vector_of_Node Its.push_back(G.addNode());21 std::vector<Node> vector_of_Nodes; 22 for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode()); 23 23 for(int i=0; i!=8; ++i) 24 24 for(int j=0; j!=8; ++j) 25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Node Its[i], vector_of_NodeIts[j]);25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]); 26 26 27 27 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i>j is arc iff i<j and (i+j)%3." << std::endl; 28 std::cout << "number of nodes: " << count(G.first< EachNodeIt>()) << std::endl;29 30 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {28 std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl; 29 30 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 31 31 std::cout << "node " << G.id(i) << std::endl; 32 32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 34 34 std::cout << "(" << G.id(G.tail(j)) << "" << G.id(j) << ">" << G.id(G.head(j)) << ") "; 35 35 } … … 37 37 38 38 std::cout<< " "; 39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 40 40 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 41 41 std::cout<<std::endl; 42 42 43 43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " "; 44 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {44 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 45 45 std::cout << j << " "; } 46 46 std::cout << std::endl; 47 47 48 48 std::cout<< " "; 49 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {49 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 50 50 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 51 51 std::cout<<std::endl; 52 52 53 53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " "; 54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 55 55 std::cout << j << " "; } 56 56 std::cout<<std::endl; 57 57 58 58 std::cout<< " "; 59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 60 60 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 61 61 std::cout<<std::endl; … … 63 63 64 64 std::cout << "all edges: "; 65 for(E achEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {65 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { 66 66 std::cout << i << " "; 67 67 } … … 70 70 std::cout << "node property array test" << std::endl; 71 71 ListGraph::NodeMap<int> my_property_vector(G); 72 EachNodeIt v;73 G. getFirst(v);72 NodeIt v; 73 G.first(v); 74 74 my_property_vector.set(v, 42); 75 my_property_vector.set( ++G.first<EachNodeIt>(), 314);76 my_property_vector.set( ++++G.first<EachNodeIt>(), 1956);77 my_property_vector.set(vector_of_Node Its[3], 1989);78 my_property_vector.set(vector_of_Node Its[4], 2003);79 my_property_vector.set(vector_of_Node Its[7], 1978);75 my_property_vector.set(G.next(G.first<NodeIt>()), 314); 76 my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956); 77 my_property_vector.set(vector_of_Nodes[3], 1989); 78 my_property_vector.set(vector_of_Nodes[4], 2003); 79 my_property_vector.set(vector_of_Nodes[7], 1978); 80 80 std::cout << "some node property values..." << std::endl; 81 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {81 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 82 82 std::cout << my_property_vector.get(i) << std::endl; 83 83 } … … 85 85 int _ii=1; 86 86 ListGraph::EdgeMap<int> my_edge_property(G); 87 for(E achEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {87 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { 88 88 my_edge_property.set(i, _i); 89 89 _i*=_ii; ++_ii; … … 91 91 92 92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; 93 for(E achEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {93 for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) { 94 94 std::cout << my_property_vector.get(G.tail(j)) << "" << my_edge_property.get(j) << ">" << my_property_vector.get(G.head(j)) << " "; 95 95 } … … 97 97 /* 98 98 std::cout << "bfs from the first node" << std::endl; 99 bfs<ListGraph> bfs_test(G, G.first< EachNodeIt>());99 bfs<ListGraph> bfs_test(G, G.first<NodeIt>()); 100 100 bfs_test.run(); 101 101 std::cout << "reached: "; 102 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {102 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 103 103 std::cout << bfs_test.reached.get(i) << " "; 104 104 } 105 105 std::cout<<std::endl; 106 106 std::cout << "dist: "; 107 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {107 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 108 108 std::cout << bfs_test.dist.get(i) << " "; 109 109 } … … 114 114 ListGraph flowG; 115 115 116 Node Its=flowG.addNode();117 Node Itv1=flowG.addNode();118 Node Itv2=flowG.addNode();119 Node Itv3=flowG.addNode();120 Node Itv4=flowG.addNode();121 Node Itt=flowG.addNode();116 Node s=flowG.addNode(); 117 Node v1=flowG.addNode(); 118 Node v2=flowG.addNode(); 119 Node v3=flowG.addNode(); 120 Node v4=flowG.addNode(); 121 Node t=flowG.addNode(); 122 122 123 123 ListGraph::NodeMap<std::string> node_name(flowG); … … 129 129 node_name.set(t, "t"); 130 130 131 Edge Its_v1=flowG.addEdge(s, v1);132 Edge Its_v2=flowG.addEdge(s, v2);133 Edge Itv1_v2=flowG.addEdge(v1, v2);134 Edge Itv2_v1=flowG.addEdge(v2, v1);135 Edge Itv1_v3=flowG.addEdge(v1, v3);136 Edge Itv3_v2=flowG.addEdge(v3, v2);137 Edge Itv2_v4=flowG.addEdge(v2, v4);138 Edge Itv4_v3=flowG.addEdge(v4, v3);139 Edge Itv3_t=flowG.addEdge(v3, t);140 Edge Itv4_t=flowG.addEdge(v4, t);131 Edge s_v1=flowG.addEdge(s, v1); 132 Edge s_v2=flowG.addEdge(s, v2); 133 Edge v1_v2=flowG.addEdge(v1, v2); 134 Edge v2_v1=flowG.addEdge(v2, v1); 135 Edge v1_v3=flowG.addEdge(v1, v3); 136 Edge v3_v2=flowG.addEdge(v3, v2); 137 Edge v2_v4=flowG.addEdge(v2, v4); 138 Edge v4_v3=flowG.addEdge(v4, v3); 139 Edge v3_t=flowG.addEdge(v3, t); 140 Edge v4_t=flowG.addEdge(v4, t); 141 141 142 142 ListGraph::EdgeMap<int> cap(flowG); … … 155 155 std::cout << "on directed graph graph" << std::endl; //<< flowG; 156 156 std::cout << "names and capacity values" << std::endl; 157 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {157 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 158 158 std::cout << node_name.get(i) << ": "; 159 159 std::cout << "out edges: "; 160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 161 161 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 162 162 std::cout << "in edges: "; 163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 164 164 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 165 165 std::cout << std::endl; … … 175 175 //flowG.setHead(v3_t, s); 176 176 /* 177 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {177 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 178 178 std::cout << node_name.get(i) << ": "; 179 179 std::cout << "out edges: "; 180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 181 181 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 182 182 std::cout << "in edges: "; 183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 184 184 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 185 185 std::cout << std::endl; 186 186 } 187 187 188 for(E achEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {188 for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 189 189 std::cout << node_name.get(flowG.tail(e)) << ""<< cap.get(e) << ">" << node_name.get(flowG.head(e)) << " "; 190 190 } 191 191 */ 192 192 /* 193 while (flowG. first<EachEdgeIt>().valid()) {194 flowG.deleteEdge(flowG.first<E achEdgeIt>());195 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {193 while (flowG.valid(flowG.first<EdgeIt>())) { 194 flowG.deleteEdge(flowG.first<EdgeIt>()); 195 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 196 196 std::cout << node_name.get(i) << ": "; 197 197 std::cout << "out edges: "; 198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 199 199 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 200 200 std::cout << "in edges: "; 201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 202 202 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 203 203 std::cout << std::endl; … … 205 205 } 206 206 207 while (flowG. first<EachNodeIt>().valid()) {208 flowG.deleteNode(flowG.first< EachNodeIt>());209 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {207 while (flowG.valid(flowG.first<NodeIt>())) { 208 flowG.deleteNode(flowG.first<NodeIt>()); 209 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 210 210 std::cout << node_name.get(i) << ": "; 211 211 std::cout << "out edges: "; 212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 213 213 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 214 214 std::cout << "in edges: "; 215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 216 216 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 217 217 std::cout << std::endl; … … 228 228 /* 229 229 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 230 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {230 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 231 231 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 232 232 } 233 233 std::cout<<std::endl; 234 234 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 235 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {235 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 236 236 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 237 237 } … … 241 241 //std::cout << "maximum flow: "<< std::endl; 242 242 while (max_flow_test.augmentOnShortestPath()) { 243 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {243 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 244 244 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 245 245 } … … 250 250 /* 251 251 { 252 std::list<Node It> S;252 std::list<Node> S; 253 253 S.push_back(s); S.push_back(v3); 254 std::list<Node It> T;254 std::list<Node> T; 255 255 T.push_back(t); 256 256 … … 260 260 261 261 std::cout << "maximum flow: "<< std::endl; 262 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {262 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 263 263 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 264 264 }
Note: See TracChangeset
for help on using the changeset viewer.