COIN-OR::LEMON - Graph Library

Changeset 99:f26897fb91fd in lemon-0.x


Ignore:
Timestamp:
02/18/04 16:58:28 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@128
Message:

dfs iterator: DfsIterator4 improved version

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r75 r99  
    284284    operator OutEdgeIt () { return actual_edge; }
    285285    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
    286     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
     286    bool aNodeIsExamined() { return !(actual_edge.valid()); }
    287287  };
    288288
     
    615615
    616616
     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
    617683  template <typename GraphWrapper, typename ReachedMap>
    618684  class BfsIterator5 {
  • src/work/iterator_bfs_demo.cc

    r75 r99  
    8080  }
    8181
     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
    82113  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
    83114  CTGW wG(G);
  • src/work/makefile

    r51 r99  
    22CXXFLAGS=-g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
    33
    4 BINARIES = bfsdemo bfsdemo2 bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo proba
     4BINARIES = bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2
    55
    66# Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
Note: See TracChangeset for help on using the changeset viewer.