COIN-OR::LEMON - Graph Library

Changeset 220:7deda4d6a07a in lemon-0.x


Ignore:
Timestamp:
03/20/04 21:06:23 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@316
Message:

* empty log message *

Location:
src/work/jacint
Files:
1 deleted
5 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.h

    r217 r220  
    8181       
    8282        Node v=heap.top();
    83         T oldvalue=heap[v];
     83        T oldvalue=heap.get(v);
    8484        heap.pop();
    8585        distance.set(v, oldvalue);
     
    9595              heap.push(w,oldvalue+length[e]);
    9696              predecessor.set(w,e);
    97             } else if ( oldvalue+length[e] < heap[w] ) {
     97            } else if ( oldvalue+length[e] < heap.get(w) ) {
    9898              predecessor.set(w,e);
    9999              heap.decrease(w, oldvalue+length[e]);
  • src/work/jacint/fib_heap.h

    r217 r220  
    144144   
    145145
    146 
    147 
    148146    PrioType& operator[](const Item& it) {
    149147      return container[iimap[it]].prio;
    150148    }
     149
    151150   
    152151    const PrioType& operator[](const Item& it) const {
     
    154153    }
    155154
    156 //     const PrioType get(const Item& it) const {
    157 //       return container[iimap[it]].prio;
    158 //     }
    159 
     155
     156    const PrioType get(const Item& it) const {
     157      return container[iimap[it]].prio;
     158    }
     159   
    160160    void pop() {
    161161      /*The first case is that there are only one root.*/
  • src/work/jacint/makefile

    r211 r220  
    11CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
    22CXX2 = g++-2.95
    3 CXXFLAGS = -W -Wall -ansi -pedantic
     3CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include 
    44LEDAROOT ?= /ledasrc/LEDA-4.1
    55
     
    1212
    1313preflow:
    14         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc
     14        $(CXX3) $(CXXFLAGS) -o preflow preflow.cc
    1515
    1616dijkstra:
    17         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o dijkstra dijkstra.cc
     17        $(CXX3) $(CXXFLAGS) -o dijkstra dijkstra.cc
    1818
    1919prim:
    20         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
     20        $(CXX3) $(CXXFLAGS) -o prim prim.cc
    2121
    2222clean:
  • src/work/jacint/preflow.cc

    r211 r220  
    22#include <fstream>
    33
     4#include <smart_graph.h>
    45#include <list_graph.h>
    56#include <dimacs.h>
     
    1213// read_dimacs_demo < dimacs_max_flow_file
    1314int main(int, char **) {
    14   typedef ListGraph::Node Node;
    15   typedef ListGraph::EdgeIt EdgeIt;
     15  typedef SmartGraph::Node Node;
     16  typedef SmartGraph::EdgeIt EdgeIt;
    1617
    17   ListGraph G;
     18  SmartGraph G;
    1819  Node s, t;
    19   ListGraph::EdgeMap<int> cap(G);
     20  SmartGraph::EdgeMap<int> cap(G);
    2021  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2122
     
    2526
    2627  for ( int i=1; i!=11; ++i ) {
    27     ListGraph::EdgeMap<int> flow(G);
     28    SmartGraph::EdgeMap<int> flow(G);
    2829    double pre_time=currTime();
    29     Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     30    Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
    3031    max_flow_test.run();
    3132    double post_time=currTime();
     
    3334  }
    3435
    35   ListGraph::EdgeMap<int> flow(G);
    36   Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     36  SmartGraph::EdgeMap<int> flow(G);
     37  Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
    3738  max_flow_test.run();
    3839 
    39   ListGraph::NodeMap<bool> cut(G);
     40  SmartGraph::NodeMap<bool> cut(G);
    4041  max_flow_test.minCut(cut);
    4142  int min_cut_value=0;
    4243  EdgeIt e;
    4344  for(G.first(e); G.valid(e); G.next(e)) {
    44     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
     45    if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=cap[e];
    4546  }
    4647
    47   ListGraph::NodeMap<bool> cut1(G);
     48  SmartGraph::NodeMap<bool> cut1(G);
    4849  max_flow_test.minMinCut(cut1);
    4950  int min_min_cut_value=0;
    5051  for(G.first(e); G.valid(e); G.next(e)) {
    51     if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
    52       min_min_cut_value+=cap.get(e);
     52    if (cut[G.tail(e)] && !cut[G.head(e)])
     53      min_min_cut_value+=cap[e];
    5354  }
    5455
    55   ListGraph::NodeMap<bool> cut2(G);
     56  SmartGraph::NodeMap<bool> cut2(G);
    5657  max_flow_test.maxMinCut(cut2);
    5758  int max_min_cut_value=0;
    5859  for(G.first(e); G.valid(e); G.next(e)) {
    59     if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
    60       max_min_cut_value+=cap.get(e);
     60    if (cut2[G.tail(e)] && !cut2[G.head(e)])
     61      max_min_cut_value+=cap[e];
    6162      }
    6263 
  • src/work/jacint/prim.cc

    r211 r220  
    22#include <fstream>
    33
     4#include <smart_graph.h>
    45#include <list_graph.h>
    56#include <dimacs.h>
     
    1314
    1415int main(int, char **) {
    15   typedef ListGraph::Node Node;
     16  typedef SmartGraph::Node Node;
    1617
    17   ListGraph G;
     18  SmartGraph G;
    1819  Node s, t;
    19   ListGraph::EdgeMap<int> cap(G);
     20  SmartGraph::EdgeMap<int> cap(G);
    2021  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2122
     
    2324 
    2425  double pre_time=currTime();
    25     Prim<ListGraph, int, FibHeap<ListGraph::Node, int,
    26     ListGraph::NodeMap<int> > > prim_test(G, cap);
     26    Prim<SmartGraph, int, FibHeap<SmartGraph::Node, int,
     27    SmartGraph::NodeMap<int> > > prim_test(G, cap);
    2728    prim_test.run();
    2829  double post_time=currTime();
     
    3233 
    3334  pre_time=currTime();
    34   Prim<ListGraph, int, BinHeap<ListGraph::Node, int,
    35     ListGraph::NodeMap<int> > > prim_test2(G, cap);
     35  Prim<SmartGraph, int, BinHeap<SmartGraph::Node, int,
     36    SmartGraph::NodeMap<int> > > prim_test2(G, cap);
    3637  prim_test2.run();
    3738  post_time=currTime();
Note: See TracChangeset for help on using the changeset viewer.