COIN-OR::LEMON - Graph Library

Changeset 1014:aae850a2394d in lemon-0.x


Ignore:
Timestamp:
11/20/04 15:23:27 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1404
Message:

Modifications for hugo 0.2

Location:
src/work/marci/lp
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/lp/lp_solver_wrapper.h

    r921 r1014  
    1111// #include <stdio>
    1212//#include <stdlib>
     13extern "C" {
    1314#include "glpk.h"
     15}
    1416
    1517#include <iostream>
  • src/work/marci/lp/makefile

    r764 r1014  
    66LDFLAGS  = -L$(GLPKROOT)/lib -lglpk
    77
    8 BINARIES = max_flow_by_lp sample sample2 sample11 sample15
     8BINARIES = max_flow_by_lp# sample sample2 sample11 sample15
    99
    1010#include ../makefile
  • src/work/marci/lp/max_flow_by_lp.cc

    r986 r1014  
    33#include <fstream>
    44
    5 #include <sage_graph.h>
    65#include <lemon/smart_graph.h>
     6#include <lemon/list_graph.h>
    77#include <lemon/dimacs.h>
    88#include <lemon/time_measure.h>
    99//#include <graph_wrapper.h>
    10 #include <lemon/max_flow.h>
     10#include <lemon/preflow.h>
    1111#include <augmenting_flow.h>
    1212//#include <preflow_res.h>
    13 #include <for_each_macros.h>
    1413#include <lp_solver_wrapper.h>
    1514
     
    3433int main(int, char **) {
    3534
    36   typedef SageGraph MutableGraph;
    37   //typedef SmartGraph Graph;
    38   typedef SageGraph Graph;
     35  typedef ListGraph MutableGraph;
     36  typedef SmartGraph Graph;
    3937  typedef Graph::Node Node;
    4038  typedef Graph::EdgeIt EdgeIt;
     
    4846  Timer ts;
    4947  Graph::EdgeMap<int> flow(g); //0 flow
    50   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     48  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    5149    max_flow_test(g, s, t, cap, flow);
    5250  AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     
    6159    std::cout << "elapsed time: " << ts << std::endl;
    6260    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    63     max_flow_test.actMinCut(cut);
    64 
    65     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     61    max_flow_test.minCut(cut);
     62
     63    for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    6664      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
    6765        std::cout << "Slackness does not hold!" << std::endl;
     
    7573//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    7674//     ts.reset();
    77 //     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     75//     max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    7876//     std::cout << "elapsed time: " << ts << std::endl;
    7977//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     
    9896  {
    9997    std::cout << "physical blocking flow augmentation ..." << std::endl;
    100     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     98    for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    10199    ts.reset();
    102100    int i=0;
     
    106104    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    107105
    108     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     106    for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    109107      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
    110108        std::cout << "Slackness does not hold!" << std::endl;
     
    127125  {
    128126    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    129     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     127    for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    130128    ts.reset();
    131129    int i=0;
     
    135133    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    136134
    137     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     135    for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    138136      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
    139137        std::cout << "Slackness does not hold!" << std::endl;
     
    187185  EdgeIndexMap edge_index_map(g);
    188186  PrimalMap<Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
    189   Graph::EdgeIt e;
    190   for (g.first(e); g.valid(e); g.next(e)) {
     187  for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    191188    ColIt col_it=lp.addCol();
    192189    edge_index_map.set(e, col_it);
    193190    lp.setColBounds(col_it, LPX_DB, 0.0, cap[e]);
    194191  }
    195   Graph::NodeIt n;
    196   for (g.first(n); g.valid(n); g.next(n)) {
     192  for (Graph::NodeIt n(g); n!=INVALID; ++n) {
    197193    if (n!=s) {
    198194      //hurokelek miatt
    199195      Graph::EdgeMap<int> coeffs(g, 0);
    200       {
    201         Graph::InEdgeIt e;
    202         for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]+1);
    203       }
    204       {
    205         Graph::OutEdgeIt e;
    206         for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]-1);
    207       }
     196      for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
     197        coeffs.set(e, coeffs[e]+1);
     198      for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
     199        coeffs.set(e, coeffs[e]-1);
    208200      if (n==t) {
    209         Graph::EdgeIt e;
    210         //std::vector< std::pair<ColIt, double> > row;
    211         for (g.first(e); g.valid(e); g.next(e)) {
     201        for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    212202          if (coeffs[e]!=0)
    213203            lp.setObjCoef(edge_index_map[e], coeffs[e]);
     
    215205      } else  {
    216206        RowIt row_it=lp.addRow();
    217         Graph::EdgeIt e;
    218207        std::vector< std::pair<ColIt, double> > row;
    219         for (g.first(e); g.valid(e); g.next(e)) {
     208        for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    220209          if (coeffs[e]!=0)
    221210            row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
Note: See TracChangeset for help on using the changeset viewer.