1.1 --- a/src/work/bfs_iterator.hh	Wed Feb 18 14:43:01 2004 +0000
     1.2 +++ b/src/work/bfs_iterator.hh	Wed Feb 18 15:58:28 2004 +0000
     1.3 @@ -283,7 +283,7 @@
     1.4      bool finished() { return bfs_queue.empty(); }
     1.5      operator OutEdgeIt () { return actual_edge; }
     1.6      bool bNodeIsNewlyReached() { return b_node_newly_reached; }
     1.7 -    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
     1.8 +    bool aNodeIsExamined() { return !(actual_edge.valid()); }
     1.9    };
    1.10  
    1.11    template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    1.12 @@ -614,6 +614,72 @@
    1.13   };
    1.14  
    1.15  
    1.16 +  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    1.17 +  struct DfsIterator4 {
    1.18 +    typedef typename Graph::NodeIt NodeIt;
    1.19 +    const Graph& G;
    1.20 +    std::stack<OutEdgeIt> dfs_stack;
    1.21 +    //ReachedMap& reached;
    1.22 +    bool b_node_newly_reached;
    1.23 +    OutEdgeIt actual_edge;
    1.24 +    NodeIt actual_node;
    1.25 +    ReachedMap reached;
    1.26 +    DfsIterator4(const Graph& _G 
    1.27 +		 /*, std::stack<OutEdgeIt>& _bfs_queue, 
    1.28 +		   ReachedMap& _reached*/) : 
    1.29 +      G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 
    1.30 +      //actual_edge=bfs_queue.top();
    1.31 +      //if (actual_edge.valid()) { 
    1.32 +      //	NodeIt w=G.bNode(actual_edge);
    1.33 +      //if (!reached.get(w)) {
    1.34 +      //  bfs_queue.push(OutEdgeIt(G, w));
    1.35 +      //  reached.set(w, true);
    1.36 +      //  b_node_newly_reached=true;
    1.37 +      //} else {
    1.38 +      //  ++(bfs_queue.top());
    1.39 +      //  b_node_newly_reached=false;
    1.40 +      //}
    1.41 +      //} else {
    1.42 +      //	bfs_queue.pop();
    1.43 +      //}
    1.44 +    }
    1.45 +    void pushAndSetReached(NodeIt s) { 
    1.46 +      reached.set(s, true);
    1.47 +      dfs_stack.push(G.template first<OutEdgeIt>(s)); 
    1.48 +    }
    1.49 +    DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
    1.50 +    operator++() { 
    1.51 +      actual_edge=dfs_stack.top();
    1.52 +      //actual_node=G.aNode(actual_edge);
    1.53 +      if (actual_edge.valid()) { 
    1.54 +	NodeIt w=G.bNode(actual_edge);
    1.55 +	actual_node=w;
    1.56 +	if (!reached.get(w)) {
    1.57 +	  dfs_stack.push(G.template first<OutEdgeIt>(w));
    1.58 +	  reached.set(w, true);
    1.59 +	  b_node_newly_reached=true;
    1.60 +	} else {
    1.61 +	  ++(dfs_stack.top());
    1.62 +	  b_node_newly_reached=false;
    1.63 +	}
    1.64 +      } else {
    1.65 +	//actual_node=G.aNode(dfs_stack.top());
    1.66 +	dfs_stack.pop();
    1.67 +      }
    1.68 +      return *this;
    1.69 +    }
    1.70 +    bool finished() const { return dfs_stack.empty(); }
    1.71 +    operator OutEdgeIt () const { return actual_edge; }
    1.72 +    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    1.73 +    bool isANodeExamined() const { return !(actual_edge.valid()); }
    1.74 +    NodeIt aNode() const { return actual_node; }
    1.75 +    NodeIt bNode() const { return G.bNode(actual_edge); }
    1.76 +    const ReachedMap& getReachedMap() const { return reached; }
    1.77 +    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
    1.78 +  };
    1.79 +
    1.80 +
    1.81 +
    1.82    template <typename GraphWrapper, typename ReachedMap>
    1.83    class BfsIterator5 {
    1.84      typedef typename GraphWrapper::NodeIt NodeIt;

     2.1 --- a/src/work/iterator_bfs_demo.cc	Wed Feb 18 14:43:01 2004 +0000
     2.2 +++ b/src/work/iterator_bfs_demo.cc	Wed Feb 18 15:58:28 2004 +0000
     2.3 @@ -79,6 +79,37 @@
     2.4      }
     2.5    }
     2.6  
     2.7 +  {
     2.8 +    std::cout << "iterator dfs demo 4 ..." << std::endl;
     2.9 +    DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
    2.10 +    dfs.pushAndSetReached(s);
    2.11 +    while (!dfs.finished()) {
    2.12 +      ++dfs;
    2.13 +      if (OutEdgeIt(dfs).valid()) {
    2.14 +	std::cout << "OutEdgeIt: " << dfs; 
    2.15 +	std::cout << " aNode: " << G.aNode(dfs); 
    2.16 +	std::cout << " bNode: " << G.bNode(dfs) << " ";
    2.17 +      } else { 
    2.18 +	std::cout << "OutEdgeIt: " << "invalid"; 
    2.19 +	std::cout << " aNode: " << dfs.aNode(); 
    2.20 +	std::cout << " bNode: " << "invalid" << " ";
    2.21 +      }
    2.22 +      if (dfs.isBNodeNewlyReached()) { 
    2.23 +	std::cout << "bNodeIsNewlyReached ";
    2.24 +      } else { 
    2.25 +	std::cout << "bNodeIsNotNewlyReached ";
    2.26 +      } 
    2.27 +      if (dfs.isANodeExamined()) { 
    2.28 +	std::cout << "aNodeIsExamined ";
    2.29 +      } else { 
    2.30 +	std::cout << "aNodeIsNotExamined ";
    2.31 +      } 
    2.32 +      std::cout<<std::endl;
    2.33 +      //++dfs;
    2.34 +    }
    2.35 +  }
    2.36 +
    2.37 +
    2.38    typedef ConstTrivGraphWrapper<ListGraph> CTGW;
    2.39    CTGW wG(G);
    2.40  

     3.1 --- a/src/work/makefile	Wed Feb 18 14:43:01 2004 +0000
     3.2 +++ b/src/work/makefile	Wed Feb 18 15:58:28 2004 +0000
     3.3 @@ -1,7 +1,7 @@
     3.4  INCLUDEDIRS=-I../include -I. -I./jacint
     3.5  CXXFLAGS=-g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
     3.6  
     3.7 -BINARIES = bfsdemo bfsdemo2 bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo proba
     3.8 +BINARIES = bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2
     3.9  
    3.10  # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
    3.11  # ismert rendszeren :-)  (Misi)