COIN-OR::LEMON - Graph Library

Changeset 854:baf0b6e40211 in lemon-0.x


Ignore:
Timestamp:
09/15/04 12:34:12 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1153
Message:

correction of SubGraphWrapper? bug.

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r849 r854  
    379379      NodeIt(Invalid i) : Node(i) { }
    380380      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
    381         Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
     381        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
     382        while (*static_cast<Node*>(this)!=INVALID &&
     383               !(*(gw->edge_filter_map))[*this])
     384          *(static_cast<Node*>(this))=
     385            ++(typename Graph::NodeIt(*(gw->graph), *this));
     386      }
    382387      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    383388             const Node& n) :
     
    402407      OutEdgeIt(Invalid i) : Edge(i) { }
    403408      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    404         Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     409        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     410        while (*static_cast<Edge*>(this)!=INVALID &&
     411               !(*(gw->edge_filter_map))[*this])
     412          *(static_cast<Edge*>(this))=
     413            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     414      }
    405415      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    406416             const Edge& e) :
     
    424434      InEdgeIt(Invalid i) : Edge(i) { }
    425435      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    426         Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     436        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     437        while (*static_cast<Edge*>(this)!=INVALID &&
     438               !(*(gw->edge_filter_map))[*this])
     439          *(static_cast<Edge*>(this))=
     440            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     441      }
    427442      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    428443             const Edge& e) :
     
    446461      EdgeIt(Invalid i) : Edge(i) { }
    447462      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
    448         Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
     463        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
     464        while (*static_cast<Edge*>(this)!=INVALID &&
     465               !(*(gw->edge_filter_map))[*this])
     466          *(static_cast<Edge*>(this))=
     467            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     468      }
    449469      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    450470             const Edge& e) :
  • src/work/makefile

    r773 r854  
    11INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
    2 CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     2CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
    33
    44BINARIES ?= bin_heap_demo
  • src/work/marci/augmenting_flow.h

    r777 r854  
    12621262          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
    12631263                                        res_graph_to_F[res_graph.head(e)]);
    1264           original_edge.update();
     1264          //original_edge.update();
    12651265          original_edge.set(f, e);
    1266           residual_capacity.update();
     1266          //residual_capacity.update();
    12671267          residual_capacity.set(f, res_graph.resCap(e));
    12681268        } else {
     
    12701270            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
    12711271                                          res_graph_to_F[res_graph.head(e)]);
    1272             original_edge.update();
     1272            //original_edge.update();
    12731273            original_edge.set(f, e);
    1274             residual_capacity.update();
     1274            //residual_capacity.update();
    12751275            residual_capacity.set(f, res_graph.resCap(e));
    12761276          }
     
    12951295      while (!dfs.finished()) {
    12961296        ++dfs;
    1297         if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
     1297        if (typename MG::Edge(dfs)!=INVALID) {
    12981298          if (dfs.isBNodeNewlyReached()) {
    12991299            typename MG::Node v=F.tail(dfs);
     
    13121312
    13131313          } else {
    1314             F.erase(/*typename MG::OutEdgeIt*/(dfs));
     1314            F.erase(typename MG::Edge(dfs));
    13151315          }
    13161316        }
  • src/work/marci/max_flow_demo.cc

    r849 r854  
    44// max_flow_demo < dimacs_max_flow_file
    55
    6 
    76#include <iostream>
    87#include <fstream>
    98
    10 #include <sage_graph.h>
    119#include <hugo/smart_graph.h>
     10#include <hugo/list_graph.h>
    1211#include <hugo/dimacs.h>
    1312#include <hugo/time_measure.h>
    14 //#include <graph_wrapper.h>
    1513#include <hugo/preflow.h>
    1614#include <augmenting_flow.h>
    17 //#include <preflow_res.h>
    18 #include <for_each_macros.h>
    1915#include <graph_concept.h>
    2016
     
    2319int main(int, char **) {
    2420
    25   typedef SageGraph MutableGraph;
    26 
    27   //typedef FullFeatureGraphConcept Graph;
    28   //typedef SmartGraph Graph;
    29   typedef SageGraph Graph;
     21  typedef ListGraph MutableGraph;
     22  typedef SmartGraph Graph;
    3023  typedef Graph::Node Node;
    3124  typedef Graph::EdgeIt EdgeIt;
     
    5447    max_flow_test.minCut(cut);
    5548
    56     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     49    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    5750      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    5851        std::cout << "Slackness does not hold!" << std::endl;
     
    6457  {
    6558    std::cout << "preflow ..." << std::endl;
    66     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     59    for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    6760    ts.reset();
    68     max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     61    max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    6962    std::cout << "elapsed time: " << ts << std::endl;
    7063    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    7164
    72     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     65    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    7366      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    7467        std::cout << "Slackness does not hold!" << std::endl;
     
    8982  {
    9083    std::cout << "physical blocking flow augmentation ..." << std::endl;
    91     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     84    for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    9285    ts.reset();
    9386    int i=0;
     
    9790    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    9891
    99     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     92    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    10093      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    10194        std::cout << "Slackness does not hold!" << std::endl;
     
    107100  {
    108101    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    109     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     102    for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    110103    ts.reset();
    111104    int i=0;
     
    115108    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    116109
    117     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     110    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    118111      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    119112        std::cout << "Slackness does not hold!" << std::endl;
     
    125118  {
    126119    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    127     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     120    for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    128121    ts.reset();
    129122    int i=0;
     
    133126    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    134127
    135     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     128    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    136129      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    137130        std::cout << "Slackness does not hold!" << std::endl;
     
    143136  {
    144137    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    145     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     138    for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    146139    ts.reset();
    147140    int i=0;
     
    151144    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    152145
    153     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     146    for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
    154147      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    155148        std::cout << "Slackness does not hold!" << std::endl;
Note: See TracChangeset for help on using the changeset viewer.