COIN-OR::LEMON - Graph Library

Changeset 2514:57143c09dc20 in lemon-0.x for demo


Ignore:
Timestamp:
11/17/07 21:58:11 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
Message:

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

Location:
demo
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • demo/disjoint_paths_demo.cc

    r2392 r2514  
    6464  Graph::EdgeMap<int> flow(graph);
    6565
    66   Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
     66  Preflow<Graph, Capacity> preflow(graph, capacity, source, target);
    6767 
    6868  preflow.run();
     
    7373    title("edge disjoint paths").scaleToA4().
    7474    copyright("(C) 2003-2007 LEMON Project").drawArrows().
    75     edgeColors(composeMap(functorMap(color), flow)).
     75    edgeColors(composeMap(functorMap(color), preflow.flowMap())).
    7676    coords(coords).run();
    7777
     
    8888  SGraph::EdgeMap<int> sflow(sgraph);
    8989
    90   Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
    91                                            SGraph::inNode(target),
    92                                            scapacity, sflow);
     90  Preflow<SGraph, SCapacity> spreflow(sgraph, scapacity,
     91                                      SGraph::outNode(source),
     92                                      SGraph::inNode(target));
    9393
    9494  spreflow.run();
     
    100100    title("node disjoint paths").scaleToA4().
    101101    copyright("(C) 2003-2007 LEMON Project").drawArrows().
    102     edgeColors(composeMap(functorMap(color), sflow)).
     102    edgeColors(composeMap(functorMap(color), spreflow.flowMap())).
    103103    coords(SGraph::combinedNodeMap(coords,
    104104                                   shiftMap(coords,
  • demo/sub_graph_adaptor_demo.cc

    r2391 r2514  
    110110
    111111  ConstMap<Edge, int> const_1_map(1);
    112   Graph::EdgeMap<int> flow(g, 0);
    113112  // Max flow between s and t in the graph of tight edges.
    114   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
    115     preflow(gw, s, t, const_1_map, flow);
     113  Preflow<SubGW, ConstMap<Edge, int> > preflow(gw, const_1_map, s, t);
    116114  preflow.run();
    117115
     
    121119       << endl;
    122120  for(EdgeIt e(g); e!=INVALID; ++e)
    123     if (flow[e])
     121    if (preflow.flow(e) != 0)
    124122      cout << " " << g.id(e) << ", "
    125123           << g.id(g.source(e)) << "--"
Note: See TracChangeset for help on using the changeset viewer.