COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 243:a85fd87460e3 in lemon-0.x for src/work/bfs_iterator.h


Ignore:
Timestamp:
03/25/04 10:42:59 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@342
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/bfs_iterator.h

    r174 r243  
    1010namespace hugo {
    1111
    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//     }
    3131   
    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//   };
    5353
    5454//   template <typename Graph>
    … …  
    545545
    546546
    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// }; 
    631631
    632632
    … …  
    718718  }; 
    719719
    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//   };
    775775
    776776  template <typename GraphWrapper, /*typename OutEdgeIt,*/
Note: See TracChangeset for help on using the changeset viewer.