Changeset 99:f26897fb91fd in lemon-0.x for src/work
- Timestamp:
- 02/18/04 16:58:28 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@128
- Location:
- src/work
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/bfs_iterator.hh
r75 r99 284 284 operator OutEdgeIt () { return actual_edge; } 285 285 bool bNodeIsNewlyReached() { return b_node_newly_reached; } 286 bool aNodeIs Leaved() { return !(actual_edge.valid()); }286 bool aNodeIsExamined() { return !(actual_edge.valid()); } 287 287 }; 288 288 … … 615 615 616 616 617 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 618 struct DfsIterator4 { 619 typedef typename Graph::NodeIt NodeIt; 620 const Graph& G; 621 std::stack<OutEdgeIt> dfs_stack; 622 //ReachedMap& reached; 623 bool b_node_newly_reached; 624 OutEdgeIt actual_edge; 625 NodeIt actual_node; 626 ReachedMap reached; 627 DfsIterator4(const Graph& _G 628 /*, std::stack<OutEdgeIt>& _bfs_queue, 629 ReachedMap& _reached*/) : 630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 631 //actual_edge=bfs_queue.top(); 632 //if (actual_edge.valid()) { 633 // NodeIt w=G.bNode(actual_edge); 634 //if (!reached.get(w)) { 635 // bfs_queue.push(OutEdgeIt(G, w)); 636 // reached.set(w, true); 637 // b_node_newly_reached=true; 638 //} else { 639 // ++(bfs_queue.top()); 640 // b_node_newly_reached=false; 641 //} 642 //} else { 643 // bfs_queue.pop(); 644 //} 645 } 646 void pushAndSetReached(NodeIt s) { 647 reached.set(s, true); 648 dfs_stack.push(G.template first<OutEdgeIt>(s)); 649 } 650 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 651 operator++() { 652 actual_edge=dfs_stack.top(); 653 //actual_node=G.aNode(actual_edge); 654 if (actual_edge.valid()) { 655 NodeIt w=G.bNode(actual_edge); 656 actual_node=w; 657 if (!reached.get(w)) { 658 dfs_stack.push(G.template first<OutEdgeIt>(w)); 659 reached.set(w, true); 660 b_node_newly_reached=true; 661 } else { 662 ++(dfs_stack.top()); 663 b_node_newly_reached=false; 664 } 665 } else { 666 //actual_node=G.aNode(dfs_stack.top()); 667 dfs_stack.pop(); 668 } 669 return *this; 670 } 671 bool finished() const { return dfs_stack.empty(); } 672 operator OutEdgeIt () const { return actual_edge; } 673 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 674 bool isANodeExamined() const { return !(actual_edge.valid()); } 675 NodeIt aNode() const { return actual_node; } 676 NodeIt bNode() const { return G.bNode(actual_edge); } 677 const ReachedMap& getReachedMap() const { return reached; } 678 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 679 }; 680 681 682 617 683 template <typename GraphWrapper, typename ReachedMap> 618 684 class BfsIterator5 { -
src/work/iterator_bfs_demo.cc
r75 r99 80 80 } 81 81 82 { 83 std::cout << "iterator dfs demo 4 ..." << std::endl; 84 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 85 dfs.pushAndSetReached(s); 86 while (!dfs.finished()) { 87 ++dfs; 88 if (OutEdgeIt(dfs).valid()) { 89 std::cout << "OutEdgeIt: " << dfs; 90 std::cout << " aNode: " << G.aNode(dfs); 91 std::cout << " bNode: " << G.bNode(dfs) << " "; 92 } else { 93 std::cout << "OutEdgeIt: " << "invalid"; 94 std::cout << " aNode: " << dfs.aNode(); 95 std::cout << " bNode: " << "invalid" << " "; 96 } 97 if (dfs.isBNodeNewlyReached()) { 98 std::cout << "bNodeIsNewlyReached "; 99 } else { 100 std::cout << "bNodeIsNotNewlyReached "; 101 } 102 if (dfs.isANodeExamined()) { 103 std::cout << "aNodeIsExamined "; 104 } else { 105 std::cout << "aNodeIsNotExamined "; 106 } 107 std::cout<<std::endl; 108 //++dfs; 109 } 110 } 111 112 82 113 typedef ConstTrivGraphWrapper<ListGraph> CTGW; 83 114 CTGW wG(G); -
src/work/makefile
r51 r99 2 2 CXXFLAGS=-g -O -Wall $(INCLUDEDIRS) -ansi -pedantic 3 3 4 BINARIES = b fsdemo bfsdemo2 bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo proba4 BINARIES = bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2 5 5 6 6 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
Note: See TracChangeset
for help on using the changeset viewer.