7 #include <utility> |
7 #include <utility> |
8 #include <graph_wrapper.h> |
8 #include <graph_wrapper.h> |
9 |
9 |
10 namespace hugo { |
10 namespace hugo { |
11 |
11 |
12 template <typename Graph> |
12 // template <typename Graph> |
13 struct bfs { |
13 // struct bfs { |
14 typedef typename Graph::Node Node; |
14 // typedef typename Graph::Node Node; |
15 typedef typename Graph::Edge Edge; |
15 // typedef typename Graph::Edge Edge; |
16 typedef typename Graph::NodeIt NodeIt; |
16 // typedef typename Graph::NodeIt NodeIt; |
17 typedef typename Graph::OutEdgeIt OutEdgeIt; |
17 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
18 Graph& G; |
18 // Graph& G; |
19 Node s; |
19 // Node s; |
20 typename Graph::NodeMap<bool> reached; |
20 // typename Graph::NodeMap<bool> reached; |
21 typename Graph::NodeMap<Edge> pred; |
21 // typename Graph::NodeMap<Edge> pred; |
22 typename Graph::NodeMap<int> dist; |
22 // typename Graph::NodeMap<int> dist; |
23 std::queue<Node> bfs_queue; |
23 // std::queue<Node> bfs_queue; |
24 bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
24 // bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
25 bfs_queue.push(s); |
25 // bfs_queue.push(s); |
26 for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) |
26 // for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) |
27 reached.set(i, false); |
27 // reached.set(i, false); |
28 reached.set(s, true); |
28 // reached.set(s, true); |
29 dist.set(s, 0); |
29 // dist.set(s, 0); |
30 } |
30 // } |
31 |
31 |
32 void run() { |
32 // void run() { |
33 while (!bfs_queue.empty()) { |
33 // while (!bfs_queue.empty()) { |
34 Node v=bfs_queue.front(); |
34 // Node v=bfs_queue.front(); |
35 OutEdgeIt e=G.template first<OutEdgeIt>(v); |
35 // OutEdgeIt e=G.template first<OutEdgeIt>(v); |
36 bfs_queue.pop(); |
36 // bfs_queue.pop(); |
37 for( ; e.valid(); ++e) { |
37 // for( ; e.valid(); ++e) { |
38 Node w=G.bNode(e); |
38 // Node w=G.bNode(e); |
39 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; |
39 // std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; |
40 if (!reached.get(w)) { |
40 // if (!reached.get(w)) { |
41 std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
41 // std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
42 bfs_queue.push(w); |
42 // bfs_queue.push(w); |
43 dist.set(w, dist.get(v)+1); |
43 // dist.set(w, dist.get(v)+1); |
44 pred.set(w, e); |
44 // pred.set(w, e); |
45 reached.set(w, true); |
45 // reached.set(w, true); |
46 } else { |
46 // } else { |
47 std::cout << G.id(w) << " is already reached" << std::endl; |
47 // std::cout << G.id(w) << " is already reached" << std::endl; |
48 } |
48 // } |
49 } |
49 // } |
50 } |
50 // } |
51 } |
51 // } |
52 }; |
52 // }; |
53 |
53 |
54 // template <typename Graph> |
54 // template <typename Graph> |
55 // struct bfs_visitor { |
55 // struct bfs_visitor { |
56 // typedef typename Graph::Node Node; |
56 // typedef typename Graph::Node Node; |
57 // typedef typename Graph::Edge Edge; |
57 // typedef typename Graph::Edge Edge; |
542 // const ReachedMap& getReachedMap() const { return reached; } |
542 // const ReachedMap& getReachedMap() const { return reached; } |
543 // //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } |
543 // //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } |
544 // }; |
544 // }; |
545 |
545 |
546 |
546 |
547 template <typename Graph, typename OutEdgeIt, |
547 // template <typename Graph, typename OutEdgeIt, |
548 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
548 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
549 class BfsIterator4 { |
549 // class BfsIterator4 { |
550 typedef typename Graph::Node Node; |
550 // typedef typename Graph::Node Node; |
551 const Graph& G; |
551 // const Graph& G; |
552 std::queue<Node> bfs_queue; |
552 // std::queue<Node> bfs_queue; |
553 ReachedMap& reached; |
553 // ReachedMap& reached; |
554 bool b_node_newly_reached; |
554 // bool b_node_newly_reached; |
555 OutEdgeIt actual_edge; |
555 // OutEdgeIt actual_edge; |
556 bool own_reached_map; |
556 // bool own_reached_map; |
557 public: |
557 // public: |
558 BfsIterator4(const Graph& _G, ReachedMap& _reached) : |
558 // BfsIterator4(const Graph& _G, ReachedMap& _reached) : |
559 G(_G), reached(_reached), |
559 // G(_G), reached(_reached), |
560 own_reached_map(false) { } |
560 // own_reached_map(false) { } |
561 BfsIterator4(const Graph& _G) : |
561 // BfsIterator4(const Graph& _G) : |
562 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
562 // G(_G), reached(*(new ReachedMap(G /*, false*/))), |
563 own_reached_map(true) { } |
563 // own_reached_map(true) { } |
564 ~BfsIterator4() { if (own_reached_map) delete &reached; } |
564 // ~BfsIterator4() { if (own_reached_map) delete &reached; } |
565 void pushAndSetReached(Node s) { |
565 // void pushAndSetReached(Node s) { |
566 //std::cout << "mimi" << &reached << std::endl; |
566 // //std::cout << "mimi" << &reached << std::endl; |
567 reached.set(s, true); |
567 // reached.set(s, true); |
568 //std::cout << "mumus" << std::endl; |
568 // //std::cout << "mumus" << std::endl; |
569 if (bfs_queue.empty()) { |
569 // if (bfs_queue.empty()) { |
570 //std::cout << "bibi1" << std::endl; |
570 // //std::cout << "bibi1" << std::endl; |
571 bfs_queue.push(s); |
571 // bfs_queue.push(s); |
572 //std::cout << "zizi" << std::endl; |
572 // //std::cout << "zizi" << std::endl; |
573 G./*getF*/first(actual_edge, s); |
573 // G./*getF*/first(actual_edge, s); |
574 //std::cout << "kiki" << std::endl; |
574 // //std::cout << "kiki" << std::endl; |
575 if (G.valid(actual_edge)/*.valid()*/) { |
575 // if (G.valid(actual_edge)/*.valid()*/) { |
576 Node w=G.bNode(actual_edge); |
576 // Node w=G.bNode(actual_edge); |
577 if (!reached.get(w)) { |
577 // if (!reached.get(w)) { |
578 bfs_queue.push(w); |
578 // bfs_queue.push(w); |
579 reached.set(w, true); |
579 // reached.set(w, true); |
580 b_node_newly_reached=true; |
580 // b_node_newly_reached=true; |
581 } else { |
581 // } else { |
582 b_node_newly_reached=false; |
582 // b_node_newly_reached=false; |
583 } |
583 // } |
584 } |
584 // } |
585 } else { |
585 // } else { |
586 //std::cout << "bibi2" << std::endl; |
586 // //std::cout << "bibi2" << std::endl; |
587 bfs_queue.push(s); |
587 // bfs_queue.push(s); |
588 } |
588 // } |
589 } |
589 // } |
590 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
590 // BfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
591 operator++() { |
591 // operator++() { |
592 if (G.valid(actual_edge)/*.valid()*/) { |
592 // if (G.valid(actual_edge)/*.valid()*/) { |
593 /*++*/G.next(actual_edge); |
593 // /*++*/G.next(actual_edge); |
594 if (G.valid(actual_edge)/*.valid()*/) { |
594 // if (G.valid(actual_edge)/*.valid()*/) { |
595 Node w=G.bNode(actual_edge); |
595 // Node w=G.bNode(actual_edge); |
596 if (!reached.get(w)) { |
596 // if (!reached.get(w)) { |
597 bfs_queue.push(w); |
597 // bfs_queue.push(w); |
598 reached.set(w, true); |
598 // reached.set(w, true); |
599 b_node_newly_reached=true; |
599 // b_node_newly_reached=true; |
600 } else { |
600 // } else { |
601 b_node_newly_reached=false; |
601 // b_node_newly_reached=false; |
602 } |
602 // } |
603 } |
603 // } |
604 } else { |
604 // } else { |
605 bfs_queue.pop(); |
605 // bfs_queue.pop(); |
606 if (!bfs_queue.empty()) { |
606 // if (!bfs_queue.empty()) { |
607 G./*getF*/first(actual_edge, bfs_queue.front()); |
607 // G./*getF*/first(actual_edge, bfs_queue.front()); |
608 if (G.valid(actual_edge)/*.valid()*/) { |
608 // if (G.valid(actual_edge)/*.valid()*/) { |
609 Node w=G.bNode(actual_edge); |
609 // Node w=G.bNode(actual_edge); |
610 if (!reached.get(w)) { |
610 // if (!reached.get(w)) { |
611 bfs_queue.push(w); |
611 // bfs_queue.push(w); |
612 reached.set(w, true); |
612 // reached.set(w, true); |
613 b_node_newly_reached=true; |
613 // b_node_newly_reached=true; |
614 } else { |
614 // } else { |
615 b_node_newly_reached=false; |
615 // b_node_newly_reached=false; |
616 } |
616 // } |
617 } |
617 // } |
618 } |
618 // } |
619 } |
619 // } |
620 return *this; |
620 // return *this; |
621 } |
621 // } |
622 bool finished() const { return bfs_queue.empty(); } |
622 // bool finished() const { return bfs_queue.empty(); } |
623 operator OutEdgeIt () const { return actual_edge; } |
623 // operator OutEdgeIt () const { return actual_edge; } |
624 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
624 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
625 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
625 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
626 Node aNode() const { return bfs_queue.front(); } |
626 // Node aNode() const { return bfs_queue.front(); } |
627 Node bNode() const { return G.bNode(actual_edge); } |
627 // Node bNode() const { return G.bNode(actual_edge); } |
628 const ReachedMap& getReachedMap() const { return reached; } |
628 // const ReachedMap& getReachedMap() const { return reached; } |
629 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
629 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
630 }; |
630 // }; |
631 |
631 |
632 |
632 |
633 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
633 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
634 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
634 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
635 class BfsIterator5 { |
635 class BfsIterator5 { |
715 Node bNode() const { return G.bNode(actual_edge); } |
715 Node bNode() const { return G.bNode(actual_edge); } |
716 const ReachedMap& getReachedMap() const { return reached; } |
716 const ReachedMap& getReachedMap() const { return reached; } |
717 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
717 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
718 }; |
718 }; |
719 |
719 |
720 template <typename Graph, typename OutEdgeIt, |
720 // template <typename Graph, typename OutEdgeIt, |
721 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
721 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
722 class DfsIterator4 { |
722 // class DfsIterator4 { |
723 typedef typename Graph::Node Node; |
723 // typedef typename Graph::Node Node; |
724 const Graph& G; |
724 // const Graph& G; |
725 std::stack<OutEdgeIt> dfs_stack; |
725 // std::stack<OutEdgeIt> dfs_stack; |
726 bool b_node_newly_reached; |
726 // bool b_node_newly_reached; |
727 OutEdgeIt actual_edge; |
727 // OutEdgeIt actual_edge; |
728 Node actual_node; |
728 // Node actual_node; |
729 ReachedMap& reached; |
729 // ReachedMap& reached; |
730 bool own_reached_map; |
730 // bool own_reached_map; |
731 public: |
731 // public: |
732 DfsIterator4(const Graph& _G, ReachedMap& _reached) : |
732 // DfsIterator4(const Graph& _G, ReachedMap& _reached) : |
733 G(_G), reached(_reached), |
733 // G(_G), reached(_reached), |
734 own_reached_map(false) { } |
734 // own_reached_map(false) { } |
735 DfsIterator4(const Graph& _G) : |
735 // DfsIterator4(const Graph& _G) : |
736 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
736 // G(_G), reached(*(new ReachedMap(G /*, false*/))), |
737 own_reached_map(true) { } |
737 // own_reached_map(true) { } |
738 ~DfsIterator4() { if (own_reached_map) delete &reached; } |
738 // ~DfsIterator4() { if (own_reached_map) delete &reached; } |
739 void pushAndSetReached(Node s) { |
739 // void pushAndSetReached(Node s) { |
740 actual_node=s; |
740 // actual_node=s; |
741 reached.set(s, true); |
741 // reached.set(s, true); |
742 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
742 // dfs_stack.push(G.template first<OutEdgeIt>(s)); |
743 } |
743 // } |
744 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
744 // DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
745 operator++() { |
745 // operator++() { |
746 actual_edge=dfs_stack.top(); |
746 // actual_edge=dfs_stack.top(); |
747 //actual_node=G.aNode(actual_edge); |
747 // //actual_node=G.aNode(actual_edge); |
748 if (G.valid(actual_edge)/*.valid()*/) { |
748 // if (G.valid(actual_edge)/*.valid()*/) { |
749 Node w=G.bNode(actual_edge); |
749 // Node w=G.bNode(actual_edge); |
750 actual_node=w; |
750 // actual_node=w; |
751 if (!reached.get(w)) { |
751 // if (!reached.get(w)) { |
752 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
752 // dfs_stack.push(G.template first<OutEdgeIt>(w)); |
753 reached.set(w, true); |
753 // reached.set(w, true); |
754 b_node_newly_reached=true; |
754 // b_node_newly_reached=true; |
755 } else { |
755 // } else { |
756 actual_node=G.aNode(actual_edge); |
756 // actual_node=G.aNode(actual_edge); |
757 /*++*/G.next(dfs_stack.top()); |
757 // /*++*/G.next(dfs_stack.top()); |
758 b_node_newly_reached=false; |
758 // b_node_newly_reached=false; |
759 } |
759 // } |
760 } else { |
760 // } else { |
761 //actual_node=G.aNode(dfs_stack.top()); |
761 // //actual_node=G.aNode(dfs_stack.top()); |
762 dfs_stack.pop(); |
762 // dfs_stack.pop(); |
763 } |
763 // } |
764 return *this; |
764 // return *this; |
765 } |
765 // } |
766 bool finished() const { return dfs_stack.empty(); } |
766 // bool finished() const { return dfs_stack.empty(); } |
767 operator OutEdgeIt () const { return actual_edge; } |
767 // operator OutEdgeIt () const { return actual_edge; } |
768 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
768 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
769 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
769 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
770 Node aNode() const { return actual_node; /*FIXME*/} |
770 // Node aNode() const { return actual_node; /*FIXME*/} |
771 Node bNode() const { return G.bNode(actual_edge); } |
771 // Node bNode() const { return G.bNode(actual_edge); } |
772 const ReachedMap& getReachedMap() const { return reached; } |
772 // const ReachedMap& getReachedMap() const { return reached; } |
773 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
773 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
774 }; |
774 // }; |
775 |
775 |
776 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
776 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
777 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
777 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
778 class DfsIterator5 { |
778 class DfsIterator5 { |
779 typedef typename GraphWrapper::Node Node; |
779 typedef typename GraphWrapper::Node Node; |