COIN-OR::LEMON - Graph Library

Changeset 243:a85fd87460e3 in lemon-0.x


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:

.

Location:
src/work
Files:
5 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,*/
  • src/work/edmonds_karp.h

    r206 r243  
    320320
    321321      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    322       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     322      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
    323323
    324324      bfs.pushAndSetReached(s);
     
    363363        __augment=false;
    364364        //computing blocking flow with dfs
    365         typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
    366         DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     365        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
     366        DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    367367        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    368368        pred.set(sF, typename MutableGraph::Edge(INVALID));
     
    421421      //bfs for distances on the residual graph
    422422      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    423       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     423      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
    424424      bfs.pushAndSetReached(s);
    425425      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     
    466466        __augment=false;
    467467        //computing blocking flow with dfs
    468         typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
    469         DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     468        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
     469        DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    470470        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    471471        pred.set(sF, typename MutableGraph::Edge(INVALID));
     
    528528
    529529      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    530       BfsIterator4<
     530      BfsIterator5<
    531531        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    532         typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     532        /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    533533        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    534534     
     
    553553        //computing blocking flow with dfs
    554554        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    555         DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     555        DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    556556          dfs(res_graph);
    557557        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
     
    855855
    856856      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    857       BfsIterator4<
     857      BfsIterator5<
    858858        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    859         typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     859        /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    860860        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    861861
     
    895895        //computing blocking flow with dfs
    896896        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    897         DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     897        DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    898898          dfs(res_graph);
    899899        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
  • src/work/makefile

    r213 r243  
    22CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
    33
    4 BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_demo
     4BINARIES ?= bin_heap_demo iterator_bfs_demo
    55
    66# Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
  • src/work/marci/edmonds_karp_demo.cc

    r206 r243  
    3535  typedef ListGraph MutableGraph;
    3636
    37   typedef SmartGraph Graph;
    38   //typedef ListGraph Graph;
     37  //typedef SmartGraph Graph;
     38  typedef ListGraph Graph;
    3939  typedef Graph::Node Node;
    4040  typedef Graph::EdgeIt EdgeIt;
     
    8686
    8787  {
    88     std::cout << "SmartGraph..." << std::endl;
     88    //std::cout << "SmartGraph..." << std::endl;
    8989    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    9090    Graph::EdgeMap<int> flow(G); //0 flow
     
    115115
    116116  {
    117     std::cout << "SmartGraph..." << std::endl;
     117    //std::cout << "SmartGraph..." << std::endl;
    118118    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    119119    Graph::EdgeMap<int> flow(G); //0 flow
  • src/work/marci_graph_demo.cc

    r168 r243  
    33#include <string>
    44
    5 #include <list_graph.hh>
    6 #include <bfs_iterator.hh>
    7 #include <edmonds_karp.hh>
     5#include <list_graph.h>
     6#include <bfs_iterator.h>
     7#include <edmonds_karp.h>
    88
    99using namespace hugo;
     
    1111int main (int, char*[])
    1212{
     13  typedef ListGraph::Node Node;
     14  typedef ListGraph::Edge Edge;
    1315  typedef ListGraph::NodeIt NodeIt;
    1416  typedef ListGraph::EdgeIt EdgeIt;
    15   typedef ListGraph::EachNodeIt EachNodeIt;
    16   typedef ListGraph::EachEdgeIt EachEdgeIt;
    1717  typedef ListGraph::OutEdgeIt OutEdgeIt;
    1818  typedef ListGraph::InEdgeIt InEdgeIt;
    1919  typedef ListGraph::SymEdgeIt SymEdgeIt;
    2020  ListGraph G;
    21   std::vector<NodeIt> vector_of_NodeIts;
    22   for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
     21  std::vector<Node> vector_of_Nodes;
     22  for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
    2323  for(int i=0; i!=8; ++i)
    2424    for(int j=0; j!=8; ++j)
    25       if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
     25      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
    2626
    2727  std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
    28   std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
    29 
    30   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     28  std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
     29
     30  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    3131    std::cout << "node " << G.id(i) << std::endl;
    3232    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
    33     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
     33    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
    3434      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
    3535    }
     
    3737
    3838    std::cout<< " ";
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
     39    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
    4040      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    4141    std::cout<<std::endl;
    4242
    4343    std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
    44     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
     44    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
    4545      std::cout << j << " "; }
    4646    std::cout << std::endl;
    4747
    4848    std::cout<< " ";
    49     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
     49    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
    5050      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    5151    std::cout<<std::endl;
    5252
    5353    std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
    54     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
     54    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
    5555      std::cout << j << " "; }
    5656    std::cout<<std::endl;
    5757
    5858    std::cout<< " ";
    59     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
     59    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
    6060      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    6161    std::cout<<std::endl;
     
    6363
    6464  std::cout << "all edges: ";
    65   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     65  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
    6666    std::cout << i << " ";
    6767  }
     
    7070  std::cout << "node property array test" << std::endl;
    7171  ListGraph::NodeMap<int> my_property_vector(G);
    72   EachNodeIt v;
    73   G.getFirst(v);
     72  NodeIt v;
     73  G.first(v);
    7474  my_property_vector.set(v, 42);
    75   my_property_vector.set(++G.first<EachNodeIt>(), 314);
    76   my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
    77   my_property_vector.set(vector_of_NodeIts[3], 1989);
    78   my_property_vector.set(vector_of_NodeIts[4], 2003);
    79   my_property_vector.set(vector_of_NodeIts[7], 1978);
     75  my_property_vector.set(G.next(G.first<NodeIt>()), 314);
     76  my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
     77  my_property_vector.set(vector_of_Nodes[3], 1989);
     78  my_property_vector.set(vector_of_Nodes[4], 2003);
     79  my_property_vector.set(vector_of_Nodes[7], 1978);
    8080  std::cout << "some node property values..." << std::endl;
    81   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     81  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    8282    std::cout << my_property_vector.get(i) << std::endl;
    8383  }
     
    8585  int _ii=1;
    8686  ListGraph::EdgeMap<int> my_edge_property(G);
    87   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     87  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
    8888    my_edge_property.set(i, _i);
    8989    _i*=_ii; ++_ii;
     
    9191
    9292  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
    93   for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
     93  for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
    9494    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
    9595  }
     
    9797/*
    9898  std::cout << "bfs from the first node" << std::endl;
    99   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
     99  bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
    100100  bfs_test.run();
    101101  std::cout << "reached: ";
    102   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     102  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    103103    std::cout << bfs_test.reached.get(i) << " ";
    104104  }
    105105  std::cout<<std::endl;
    106106  std::cout << "dist: ";
    107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     107  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    108108    std::cout << bfs_test.dist.get(i) << " ";
    109109  }
     
    114114  ListGraph flowG;
    115115
    116   NodeIt s=flowG.addNode();
    117   NodeIt v1=flowG.addNode();
    118   NodeIt v2=flowG.addNode();
    119   NodeIt v3=flowG.addNode();
    120   NodeIt v4=flowG.addNode();
    121   NodeIt t=flowG.addNode();
     116  Node s=flowG.addNode();
     117  Node v1=flowG.addNode();
     118  Node v2=flowG.addNode();
     119  Node v3=flowG.addNode();
     120  Node v4=flowG.addNode();
     121  Node t=flowG.addNode();
    122122 
    123123  ListGraph::NodeMap<std::string> node_name(flowG);
     
    129129  node_name.set(t, "t");
    130130
    131   EdgeIt s_v1=flowG.addEdge(s, v1);
    132   EdgeIt s_v2=flowG.addEdge(s, v2);
    133   EdgeIt v1_v2=flowG.addEdge(v1, v2);
    134   EdgeIt v2_v1=flowG.addEdge(v2, v1);
    135   EdgeIt v1_v3=flowG.addEdge(v1, v3);
    136   EdgeIt v3_v2=flowG.addEdge(v3, v2);
    137   EdgeIt v2_v4=flowG.addEdge(v2, v4);
    138   EdgeIt v4_v3=flowG.addEdge(v4, v3);
    139   EdgeIt v3_t=flowG.addEdge(v3, t);
    140   EdgeIt v4_t=flowG.addEdge(v4, t);
     131  Edge s_v1=flowG.addEdge(s, v1);
     132  Edge s_v2=flowG.addEdge(s, v2);
     133  Edge v1_v2=flowG.addEdge(v1, v2);
     134  Edge v2_v1=flowG.addEdge(v2, v1);
     135  Edge v1_v3=flowG.addEdge(v1, v3);
     136  Edge v3_v2=flowG.addEdge(v3, v2);
     137  Edge v2_v4=flowG.addEdge(v2, v4);
     138  Edge v4_v3=flowG.addEdge(v4, v3);
     139  Edge v3_t=flowG.addEdge(v3, t);
     140  Edge v4_t=flowG.addEdge(v4, t);
    141141
    142142  ListGraph::EdgeMap<int> cap(flowG);
     
    155155  std::cout << "on directed graph graph" << std::endl; //<< flowG;
    156156  std::cout << "names and capacity values" << std::endl;
    157   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     157  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    158158    std::cout << node_name.get(i) << ": ";
    159159    std::cout << "out edges: ";
    160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     160    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    161161      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    162162    std::cout << "in edges: ";
    163     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     163    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    164164      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    165165    std::cout << std::endl;
     
    175175  //flowG.setHead(v3_t, s);
    176176/*
    177   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     177  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    178178    std::cout << node_name.get(i) << ": ";
    179179    std::cout << "out edges: ";
    180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     180    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    181181      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    182182    std::cout << "in edges: ";
    183     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     183    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    184184      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    185185    std::cout << std::endl;
    186186  }
    187187 
    188   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
     188  for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    189189    std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
    190190  }
    191191*/
    192192  /*
    193   while (flowG.first<EachEdgeIt>().valid()) {
    194     flowG.deleteEdge(flowG.first<EachEdgeIt>());
    195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     193  while (flowG.valid(flowG.first<EdgeIt>())) {
     194    flowG.deleteEdge(flowG.first<EdgeIt>());
     195    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    196196      std::cout << node_name.get(i) << ": ";
    197197      std::cout << "out edges: ";
    198       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     198      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    199199        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    200200      std::cout << "in edges: ";
    201       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     201      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    202202        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    203203      std::cout << std::endl;
     
    205205  }
    206206 
    207   while (flowG.first<EachNodeIt>().valid()) {
    208     flowG.deleteNode(flowG.first<EachNodeIt>());
    209     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     207  while (flowG.valid(flowG.first<NodeIt>())) {
     208    flowG.deleteNode(flowG.first<NodeIt>());
     209    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    210210      std::cout << node_name.get(i) << ": ";
    211211      std::cout << "out edges: ";
    212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     212      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    213213        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    214214      std::cout << "in edges: ";
    215       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     215      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    216216        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    217217      std::cout << std::endl;
     
    228228    /*
    229229    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    230     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     230    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    231231      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    232232    }
    233233    std::cout<<std::endl;
    234234    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    235     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     235    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    236236      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    237237    }
     
    241241    //std::cout << "maximum flow: "<< std::endl;
    242242    while (max_flow_test.augmentOnShortestPath()) {
    243       for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     243      for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    244244        std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    245245      }
     
    250250/*
    251251  {
    252     std::list<NodeIt> S;
     252    std::list<Node> S;
    253253    S.push_back(s); S.push_back(v3);
    254     std::list<NodeIt> T;
     254    std::list<Node> T;
    255255    T.push_back(t);
    256256
     
    260260   
    261261    std::cout << "maximum flow: "<< std::endl;
    262     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     262    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    263263      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    264264    }
Note: See TracChangeset for help on using the changeset viewer.