COIN-OR::LEMON - Graph Library

Changeset 646:bd7a69231cf8 in lemon-0.x


Ignore:
Timestamp:
05/19/04 18:06:57 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@846
Message:

max_flow.h: status flags for actMinCut
leda_graph_wrapper.h: NodeMapWrapper?, EdgeMapWrapper?

Location:
src/work/marci
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bfs_dfs.h

    r615 r646  
    107107      return *this;
    108108    }
    109     /// Guess what?
     109    /// Returns true iff the algorithm is finished.
    110110    bool finished() const { return bfs_queue.empty(); }
    111111    /// The conversion operator makes for converting the bfs-iterator
     
    113113    ///\bug Edge have to be in HUGO 0.2
    114114    operator OutEdgeIt() const { return actual_edge; }
    115     /// Guess what?
     115    /// Returns if b-node has been reached just now.
    116116    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    117     /// Guess what?
     117    /// Returns if a-node is examined.
    118118    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    119     /// Guess what?
     119    /// Returns a-node of the actual edge, so does if the edge is invalid.
    120120    Node aNode() const { return bfs_queue.front(); }
    121     /// Guess what?
     121    /// \pre The actual edge have to be valid.
    122122    Node bNode() const { return graph->bNode(actual_edge); }
    123123    /// Guess what?
     
    250250      return *this;
    251251    }
    252     /// Guess what?
     252    /// Returns true iff the algorithm is finished.
    253253    bool finished() const { return dfs_stack.empty(); }
    254     /// Guess what?
     254    /// The conversion operator makes for converting the bfs-iterator
     255    /// to an \c out-edge-iterator.
     256    ///\bug Edge have to be in HUGO 0.2
    255257    operator OutEdgeIt() const { return actual_edge; }
    256     /// Guess what?
     258    /// Returns if b-node has been reached just now.
    257259    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    258     /// Guess what?
     260    /// Returns if a-node is examined.
    259261    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    260     /// Guess what?
     262    /// Returns a-node of the actual edge, so does if the edge is invalid.
    261263    Node aNode() const { return actual_node; /*FIXME*/}
    262     /// Guess what?
     264    /// Returns b-node of the actual edge.
     265    /// \pre The actual edge have to be valid.
    263266    Node bNode() const { return graph->bNode(actual_edge); }
    264267    /// Guess what?
  • src/work/marci/leda/leda_graph_wrapper.h

    r617 r646  
    4141    template <typename T> class NodeMap;
    4242    template <typename T> class EdgeMap;
     43    template <typename T> class NodeMapWrapper;
     44    template <typename T> class EdgeMapWrapper;
    4345
    4446    class Node;
     
    292294    };
    293295
     296
     297    ///Read/write map from the nodes to type \c T.
     298    template<typename T> class NodeMapWrapper
     299    {
     300      leda_node_map<T>* leda_stuff;
     301    public:
     302      typedef T ValueType;
     303      typedef Node KeyType;
     304
     305      NodeMapWrapper(leda_node_map<T>& _leda_stuff) :
     306        leda_stuff(&_leda_stuff) { }
     307      //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
     308
     309      void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
     310      T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary
     311      T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
     312      const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
     313
     314      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
     315      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
     316    };
     317
     318    ///Read/write map from the edges to type \c T.
     319    template<typename T> class EdgeMapWrapper
     320    {
     321      leda_edge_map<T>* leda_stuff;
     322    public:
     323      typedef T ValueType;
     324      typedef Edge KeyType;
     325
     326      EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) :
     327        leda_stuff(_leda_stuff) { }
     328      //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
     329
     330      void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
     331      T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary
     332      T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
     333      const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
     334
     335      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
     336      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
     337    };
     338
    294339  };
    295340
  • src/work/marci/max_flow_demo.cc

    r642 r646  
    7373  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    7474    max_flow_test(g, s, t, cap, flow);
     75  Graph::NodeMap<bool> cut(g);
    7576
    7677  {
     
    8081    std::cout << "elapsed time: " << ts << std::endl;
    8182    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     83    max_flow_test.actMinCut(cut);
     84
     85    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     86      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     87        std::cout << "Slackness does not hold!" << std::endl;
     88      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     89        std::cout << "Slackness does not hold!" << std::endl;
     90    }
    8291  }
    8392
     
    8998    std::cout << "elapsed time: " << ts << std::endl;
    9099    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     100
     101    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     102      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     103        std::cout << "Slackness does not hold!" << std::endl;
     104      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     105        std::cout << "Slackness does not hold!" << std::endl;
     106    }
    91107  }
    92108
     
    109125    std::cout << "number of augmentation phases: " << i << std::endl;
    110126    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     127
     128    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     129      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     130        std::cout << "Slackness does not hold!" << std::endl;
     131      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     132        std::cout << "Slackness does not hold!" << std::endl;
     133    }
    111134  }
    112135
     
    131154    std::cout << "number of augmentation phases: " << i << std::endl;
    132155    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     156
     157    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     158      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     159        std::cout << "Slackness does not hold!" << std::endl;
     160      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     161        std::cout << "Slackness does not hold!" << std::endl;
     162    }
    133163  }
    134164
     
    142172    std::cout << "number of augmentation phases: " << i << std::endl;
    143173    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    144   }
    145 
     174
     175    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     176      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     177        std::cout << "Slackness does not hold!" << std::endl;
     178      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     179        std::cout << "Slackness does not hold!" << std::endl;
     180    }
     181  }
     182
     183  {
     184    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     185    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     186    ts.reset();
     187    int i=0;
     188    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
     189    std::cout << "elapsed time: " << ts << std::endl;
     190    std::cout << "number of augmentation phases: " << i << std::endl;
     191    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     192
     193    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     194      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     195        std::cout << "Slackness does not hold!" << std::endl;
     196      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     197        std::cout << "Slackness does not hold!" << std::endl;
     198    }
     199  }
    146200
    147201  return 0;
Note: See TracChangeset for help on using the changeset viewer.