COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 577:e8703f0a6e2f in lemon-0.x


Ignore:
Timestamp:
05/07/04 13:57:34 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@753
Message:

top-sort, dimacs mods.

Location:
src/work
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • src/work/makefile

    r493 r577  
    11INCLUDEDIRS ?= -I../include -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/bfs_dfs_misc.h

    r552 r577  
    4040  /// I think the final version will work as an iterator
    4141  /// if the graph is not a acyclic, the na pre-topological order is obtained
    42   /// (see Schrijver's book)
    43   template<typename Graph>
    44   void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
     42  /// (see Schrijver's book).
     43  /// PredMap have to be a writtable node-map.
     44  /// If the graph is directed and not acyclic,
     45  /// then going back from the returned node via the pred information, a
     46  /// cycle is obtained.
     47  template<typename Graph, typename PredMap>
     48  typename Graph::Node
     49  topSort(const Graph& g, std::list<typename Graph::Node>& l,
     50               PredMap& pred) {
    4551    l.clear();
    4652    typedef typename Graph::template NodeMap<bool> ReachedMap;
     53    typedef typename Graph::template NodeMap<bool> ExaminedMap;   
    4754    ReachedMap reached(g/*, false*/);
     55    ExaminedMap examined(g/*, false*/);
    4856    DfsIterator<Graph, ReachedMap> dfs(g, reached);
    4957    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    5058      if (!reached[n]) {
    5159        dfs.pushAndSetReached(n);
     60        pred.set(n, INVALID);
    5261        while (!dfs.finished()) {
    5362          ++dfs;
     63          if (dfs.isBNodeNewlyReached()) {
     64            ///\bug hugo 0.2-ben Edge kell
     65            pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
     66          } else {
     67            ///\bug ugyanaz
     68            if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
     69                !examined[dfs.bNode()]) {
     70              ///\bug hugo 0.2-ben Edge kell
     71              pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
     72              return dfs.aNode();
     73            }
     74          }
    5475          if (dfs.isANodeExamined()) {
    5576            l.push_back(dfs.aNode());
     77            examined.set(dfs.aNode(), true);
    5678          }
    5779        }
    5880      }
    5981    }
     82    return INVALID;
    6083  }
    6184} //namespace hugo

  • src/work/marci/bfsit_vs_byhand.cc

    r555 r577  
    2020  typedef Graph::OutEdgeIt OutEdgeIt;
    2121
    22   Graph G;
     22  Graph g;
    2323  Node s, t;
    24   Graph::EdgeMap<int> cap(G);
    25   readDimacsMaxFlow(std::cin, G, s, t, cap);
    26   Graph::NodeMap<OutEdgeIt> pred(G);
     24  Graph::EdgeMap<int> cap(g);
     25  //readDimacsMaxFlow(std::cin, g, s, t, cap);
     26  readDimacs(std::cin, g);
     27
     28  Graph::NodeMap<OutEdgeIt> pred(g);
    2729  Timer ts;
    2830  {
    2931    ts.reset();
    30     Graph::NodeMap<bool> reached(G);
     32    Graph::NodeMap<bool> reached(g);
    3133    reached.set(s, true);
    3234    pred.set(s, INVALID);
    … …  
    3739      bfs_queue.pop();
    3840      OutEdgeIt e;
    39       for(G.first(e,v); G.valid(e); G.next(e)) {
    40         Node w=G.head(e);
     41      for(g.first(e,v); g.valid(e); g.next(e)) {
     42        Node w=g.head(e);
    4143        if (!reached[w]) {
    4244          bfs_queue.push(w);
    … …  
    5254  {
    5355    ts.reset();     
    54     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
     56    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
    5557    bfs.pushAndSetReached(s);
    5658    pred.set(s, INVALID);
    5759    while (!bfs.finished()) {
    5860      ++bfs;
    59       if (G.valid(bfs) && bfs.isBNodeNewlyReached())
     61      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
    6062        pred.set(bfs.bNode(), bfs);
    6163    }

  • src/work/marci/lg_vs_sg.cc

    r555 r577  
    2626    typedef Graph::EdgeIt EdgeIt;
    2727
    28     Graph G;
     28    Graph g;
    2929    Node s, t;
    30     Graph::EdgeMap<int> cap(G);
     30    Graph::EdgeMap<int> cap(g);
    3131    std::ifstream ins(in.c_str());
    32     readDimacsMaxFlow(ins, G, s, t, cap);
     32    //readDimacsMaxFlow(ins, g, s, t, cap);
     33    readDimacs(ins, g, cap, s, t);
    3334
    3435    Timer ts;
    35     Graph::EdgeMap<int> flow(G); //0 flow
     36    Graph::EdgeMap<int> flow(g); //0 flow
    3637    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    37       max_flow_test(G, s, t, cap, flow/*, true*/);
     38      max_flow_test(g, s, t, cap, flow/*, true*/);
    3839
    3940    std::cout << "ListGraph ..." << std::endl;
    … …  
    4950    {
    5051      std::cout << "physical blocking flow augmentation ..." << std::endl;
    51       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     52      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    5253      ts.reset();
    5354      int i=0;
    … …  
    6061//     {
    6162//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    62 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     63//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    6364//       ts.reset();
    6465//       int i=0;
    … …  
    7172    {
    7273      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    73       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     74      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    7475      ts.reset();
    7576      int i=0;
    … …  
    8283    {
    8384      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    84       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     85      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    8586      ts.reset();
    8687      int i=0;
    … …  
    9899    typedef Graph::EdgeIt EdgeIt;
    99100
    100     Graph G;
     101    Graph g;
    101102    Node s, t;
    102     Graph::EdgeMap<int> cap(G);
     103    Graph::EdgeMap<int> cap(g);
    103104    std::ifstream ins(in.c_str());
    104     readDimacsMaxFlow(ins, G, s, t, cap);
     105    //readDimacsMaxFlow(ins, g, s, t, cap);
     106    readDimacs(ins, g, cap, s, t);
    105107
    106108    Timer ts;
    107     Graph::EdgeMap<int> flow(G); //0 flow
     109    Graph::EdgeMap<int> flow(g); //0 flow
    108110    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    109       max_flow_test(G, s, t, cap, flow/*, true*/);
     111      max_flow_test(g, s, t, cap, flow/*, true*/);
    110112    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    111     //  max_flow_test(G, s, t, cap, flow);
     113    //  max_flow_test(g, s, t, cap, flow);
    112114
    113115    std::cout << "SmatrGraph ..." << std::endl;
    … …  
    115117    {
    116118      std::cout << "preflow ..." << std::endl;
    117       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     119      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    118120      ts.reset();
    119121      max_flow_test.run();
    … …  
    124126    {
    125127      std::cout << "physical blocking flow augmentation ..." << std::endl;
    126       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     128      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    127129      ts.reset();
    128130      int i=0;
    … …  
    135137//     {
    136138//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    137 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     139//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    138140//       ts.reset();
    139141//       int i=0;
    … …  
    146148    {
    147149      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    148       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     150      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    149151      ts.reset();
    150152      int i=0;
    … …  
    157159    {
    158160      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    159       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     161      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    160162      ts.reset();
    161163      int i=0;

  • src/work/marci/max_flow_demo.cc

    r555 r577  
    6464
    6565
    66   Graph G;
     66  Graph g;
    6767  Node s, t;
    68   Graph::EdgeMap<int> cap(G);
    69   readDimacsMaxFlow(std::cin, G, s, t, cap);
     68  Graph::EdgeMap<int> cap(g);
     69  //readDimacsMaxFlow(std::cin, g, s, t, cap);
     70  readDimacs(std::cin, g, cap, s, t);
    7071  Timer ts;
    71   Graph::EdgeMap<int> flow(G); //0 flow
     72  Graph::EdgeMap<int> flow(g); //0 flow
    7273  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    73     max_flow_test(G, s, t, cap, flow);
     74    max_flow_test(g, s, t, cap, flow);
    7475
    7576  {
    … …  
    8384  {
    8485    std::cout << "preflow ..." << std::endl;
    85     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     86    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    8687    ts.reset();
    8788    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    … …  
    9293//   {
    9394//     std::cout << "wrapped preflow ..." << std::endl;
    94 //     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     95//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    9596//     ts.reset();
    9697//     pre_flow_res.run();
    … …  
    101102  {
    102103    std::cout << "physical blocking flow augmentation ..." << std::endl;
    103     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     104    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    104105    ts.reset();
    105106    int i=0;
    … …  
    112113//   {
    113114//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    114 //     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     115//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    115116//     ts.reset();
    116117//     int i=0;
    … …  
    123124  {
    124125    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    125     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     126    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    126127    ts.reset();
    127128    int i=0;
    … …  
    134135  {
    135136    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    136     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     137    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    137138    ts.reset();
    138139    int i=0;

  • src/work/marci/top_sort.dim

    r552 r577  
    33a 2 3
    44a 3 5
    5 a 3 4
     5a 4 3
    66a 5 4

  • src/work/marci/top_sort_test.cc

    r557 r577  
    88#include <list_graph.h>
    99#include <hugo/graph_wrapper.h>
     10#include <hugo/maps.h>
    1011
    1112using namespace hugo;
    … …  
    1718  {
    1819    std::list<Graph::Node> l;
    19     topSort(g, l);
     20    NullMap<Graph::Node, Graph::Edge> pred;
     21    topSort(g, l, pred);
    2022    std::cout << "Leaving order of dfs which is pretopological..." << std::endl;
    2123    for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
    … …  
    2931    GW gw(g);
    3032    std::list<GW::Node> l;
    31     topSort(gw, l);
     33    NullMap<GW::Node, GW::Edge> pred;
     34    topSort(gw, l, pred);
    3235    std::cout << "Same in the revered oriented graph..." << std::endl;
    3336    for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
Note: See TracChangeset for help on using the changeset viewer.