COIN-OR::LEMON - Graph Library

Changeset 30:10a3f2e0928c in lemon-0.x


Ignore:
Timestamp:
01/21/04 15:51:05 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@43
Message:

is_valid changed to valid

Location:
src/work
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_graph_concept.txt

    r19 r30  
    11ETIK-OL-NOLIB-NEGRES graph concept-ek.
    22
    3  Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok.
     3 Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
    44A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
    5 operacio elegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
     5operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
    66ujakra van szukseg.
    77
     
    2727trivialis node iterator, csak cimezni lehet vele, pl property vectort
    2828
     29<<<<<<< marci_graph_concept.txt
     30class each_node_iterator
     31node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
     32=======
    2933class each_node_iterator;
    3034node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
     35>>>>>>> 1.3
    3136
    3237class edge_iterator;
     
    3641edge iterator a graf osszes elenek bejarasara
    3742
     43<<<<<<< marci_graph_concept.txt
     44class out_edge_iterator
     45edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
     46=======
    3847class out_edge_iterator;
    3948edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
    40 
     49>>>>>>> 1.3
     50
     51<<<<<<< marci_graph_concept.txt
     52class in_edge_iterator
     53edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
     54=======
    4155class in_edge_iterator;
    4256edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
     57>>>>>>> 1.3
    4358     
     59<<<<<<< marci_graph_concept.txt
     60class sym_edge_iterator
     61edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
     62konvertalhato
     63=======
    4464class sym_edge_iterator;
    4565edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
     66>>>>>>> 1.3
    4667
    4768default constructor:
  • src/work/preflow_push_hl.hh

    r20 r30  
    8484      reverse_bfs<list_graph> bfs(G, t);
    8585      bfs.run();
    86       for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
     86      for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
    8787        level.put(v, bfs.dist(v));
    8888        //std::cout << "the level of " << v << " is " << bfs.dist(v);
     
    9898      /* Starting flow. It is everywhere 0 at the moment. */
    9999     
    100       for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i)
     100      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
    101101        {
    102102          node_iterator w=G.head(i);
     
    130130          int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
    131131       
    132           for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
     132          for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
    133133            node_iterator v=G.head(e);
    134134            /*e is the edge wv.*/
     
    171171            } //if (flow.get(e)<capacity.get(e))
    172172         
    173           } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e)
     173          } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
    174174         
    175175
    176176
    177           for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
     177          for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
    178178            node_iterator v=G.tail(e);
    179179            /*e is the edge vw.*/
     
    289289        queue.pop();
    290290
    291         for(in_edge_iterator e=G.first_in_edge(w) ; e.is_valid(); ++e) {
     291        for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
    292292          node_iterator v=G.tail(e);
    293293          if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
     
    297297        } // for
    298298
    299         for(out_edge_iterator e=G.first_out_edge(w) ; e.is_valid(); ++e) {
     299        for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
    300300          node_iterator v=G.head(e);
    301301          if (mincutvector.get(v) && flow.get(e) > 0 ) {
  • src/work/preflow_push_max_flow.hh

    r21 r30  
    8181      reverse_bfs<list_graph> bfs(G, t);
    8282      bfs.run();
    83       for(each_node_iterator v=G.first_node(); v.is_valid(); ++v)
     83      for(each_node_iterator v=G.first_node(); v.valid(); ++v)
    8484        {
    8585          int dist=bfs.dist(v);
     
    9494      /* Starting flow. It is everywhere 0 at the moment. */
    9595     
    96       for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i)
     96      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
    9797        {
    9898          node_iterator w=G.head(i);
     
    127127          int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
    128128       
    129           for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
     129          for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
    130130            node_iterator v=G.head(e);
    131131            /*e is the edge wv.*/
     
    168168            } //if (flow.get(e)<capacity.get(e))
    169169         
    170           } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e)
     170          } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
    171171         
    172172
    173173
    174           for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
     174          for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
    175175            node_iterator v=G.tail(e);
    176176            /*e is the edge vw.*/
     
    244244                /*If the level of w gets empty.*/
    245245             
    246                 for (each_node_iterator v=G.first_node() ; v.is_valid() ; ++v) {
     246                for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
    247247                  if (level.get(v) >= l ) {
    248248                    level.put(v,n); 
     
    278278        else break;
    279279      }
    280       for (each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
     280      for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
    281281        if (level.get(v) > e) mincutvector.put(v, true);
    282282      }
  • src/work/proba.cc

    r23 r30  
    99#include <preflow_push_max_flow.hh>
    1010#include <reverse_bfs.hh>
     11//#include <dijkstra.hh>
    1112
    1213using namespace marci;
     
    2526  list_graph flow_test;
    2627 
    27   //Ahuja könyv példája, maxflowvalue=13
     28  /*  //Ahuja könyv példája, maxflowvalue=13
    2829  node_iterator s=flow_test.add_node();
    2930  node_iterator v1=flow_test.add_node();
     
    4647  edge_iterator s_v2=flow_test.add_edge(s, v2);
    4748  edge_iterator s_v3=flow_test.add_edge(s, v3);
    48  
    4949  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    5050  edge_iterator v2_v5=flow_test.add_edge(v2, v5);
    51 
    5251  edge_iterator v3_v5=flow_test.add_edge(v3, v5);
    53 
    5452  edge_iterator v4_t=flow_test.add_edge(v4, t);
    5553  edge_iterator v5_t=flow_test.add_edge(v5, t);
     54  edge_iterator v2_s=flow_test.add_edge(v2, s);
    5655 
    5756  edge_property_vector<list_graph, int> cap(flow_test); 
     
    6463  cap.put(v4_t, 8);
    6564  cap.put(v5_t, 8);
    66 
     65  cap.put(v2_s, 0);
     66*/
    6767
    6868 
    6969  //Marci példája, maxflowvalue=23
    70   /*   node_iterator s=flow_test.add_node();
     70     node_iterator s=flow_test.add_node();
    7171  node_iterator v1=flow_test.add_node();
    7272  node_iterator v2=flow_test.add_node();
     
    9898  edge_iterator v3_v3=flow_test.add_edge(v3, v3);
    9999  edge_iterator s_w=flow_test.add_edge(s, w);
     100  edge_iterator v2_s=flow_test.add_edge(v2, s);
    100101 
    101102
     
    114115  cap.put(v3_v3, 4);
    115116  cap.put(s_w, 4);
    116   */
     117  cap.put(v2_s, 0);
    117118
    118119
     
    156157  bfs_test.run();
    157158
    158   for (each_node_iterator w=flow_test.first_node(); w.is_valid(); ++w) {
     159  for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
    159160    std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
    160161    }
     
    175176
    176177  edge_property_vector<list_graph, int> flow=preflow_push_test.allflow(); 
    177   for (each_edge_iterator e=flow_test.first_edge(); e.is_valid(); ++e) {
     178  for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
    178179    std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
    179180    }
     
    182183  node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
    183184
    184   for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
     185  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
    185186      if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
    186187    }
     
    202203  node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
    203204
    204   for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
     205  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
    205206    if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
    206207  }
     
    210211
    211212
     213//    std::cout << "Testing dijkstra..." << std::endl;
     214 
     215//    dijkstra<list_graph, int> dijkstra_test(flow_test, s, cap);
     216
     217//    dijkstra_test.run();
     218
     219//    for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
     220//      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w) <<std::endl;
     221//      }
     222
     223
     224
     225
    212226  return 0;
    213227}
  • src/work/reverse_bfs.hh

    r22 r30  
    6868        bfs_queue.pop();
    6969
    70         for(in_edge_iterator e=G.first_in_edge(v); e.is_valid(); ++e) {
     70        for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
    7171          node_iterator w=G.tail(e);
    7272          if (!reached.get(w)) {
Note: See TracChangeset for help on using the changeset viewer.