COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 986:e997802b855c in lemon-0.x for src/work/jacint


Ignore:
Timestamp:
11/13/04 13:53:28 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
Message:

Naming changes:

  • head -> target
  • tail -> source
Location:
src/work/jacint
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/max_flow.h

    r921 r986  
    327327        OutEdgeIt e;
    328328        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    329           Node v=g->head(e);
     329          Node v=g->target(e);
    330330          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    331331            queue.push(v);
    … …  
    336336        InEdgeIt f;
    337337        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    338           Node v=g->tail(f);
     338          Node v=g->source(f);
    339339          if (!M[v] && (*flow)[f] > 0 ) {
    340340            queue.push(v);
    … …  
    371371        InEdgeIt e;
    372372        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    373           Node v=g->tail(e);
     373          Node v=g->source(e);
    374374          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    375375            queue.push(v);
    … …  
    380380        OutEdgeIt f;
    381381        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    382           Node v=g->head(f);
     382          Node v=g->target(f);
    383383          if (M[v] && (*flow)[f] > 0 ) {
    384384            queue.push(v);
    … …  
    434434
    435435        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    436         Node v=g->head(e);
     436        Node v=g->target(e);
    437437
    438438        if( lev > level[v] ) { //Push is allowed now
    … …  
    467467
    468468          if( (*flow)[e] <= 0 ) continue;
    469           Node v=g->tail(e);
     469          Node v=g->source(e);
    470470
    471471          if( lev > level[v] ) { //Push is allowed now
    … …  
    522522            InEdgeIt e;
    523523            for(g->first(e,v); g->valid(e); g->next(e)) {
    524               Node w=g->tail(e);
     524              Node w=g->source(e);
    525525              if ( level[w] == n && w != s ) {
    526526                bfs_queue.push(w);
    … …  
    540540              Num c=(*capacity)[e];
    541541              if ( c <= 0 ) continue;
    542               Node w=g->head(e);
     542              Node w=g->target(e);
    543543              if ( level[w] < n ) {
    544544                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    567567            for(g->first(e,v); g->valid(e); g->next(e)) {
    568568              if ( (*capacity)[e] <= (*flow)[e] ) continue;
    569               Node w=g->tail(e);
     569              Node w=g->source(e);
    570570              if ( level[w] == n && w != s ) {
    571571                bfs_queue.push(w);
    … …  
    581581            for(g->first(f,v); g->valid(f); g->next(f)) {
    582582              if ( 0 >= (*flow)[f] ) continue;
    583               Node w=g->head(f);
     583              Node w=g->target(f);
    584584              if ( level[w] == n && w != s ) {
    585585                bfs_queue.push(w);
    … …  
    600600              Num rem=(*capacity)[e]-(*flow)[e];
    601601              if ( rem <= 0 ) continue;
    602               Node w=g->head(e);
     602              Node w=g->target(e);
    603603              if ( level[w] < n ) {
    604604                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    612612            {
    613613              if ( (*flow)[f] <= 0 ) continue;
    614               Node w=g->tail(f);
     614              Node w=g->source(f);
    615615              if ( level[w] < n ) {
    616616                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    711711      //        return dist[n]; }
    712712      //       bool get(const typename MapGraphWrapper::Edge& e) const {
    713       //        return (dist.get(g->tail(e))<dist.get(g->head(e))); }
     713      //        return (dist.get(g->source(e))<dist.get(g->target(e))); }
    714714      bool operator[](const typename MapGraphWrapper::Edge& e) const {
    715         return (dist[g->tail(e)]<dist[g->head(e)]);
     715        return (dist[g->source(e)]<dist[g->target(e)]);
    716716      }
    717717    };
    … …  
    861861      for(g->first(e,v); g->valid(e); g->next(e)) {
    862862        if ( (*capacity)[e] <= (*flow)[e] ) continue;
    863         Node u=g->tail(e);
     863        Node u=g->source(e);
    864864        if ( level[u] >= n ) {
    865865          bfs_queue.push(u);
    … …  
    872872      for(g->first(f,v); g->valid(f); g->next(f)) {
    873873        if ( 0 >= (*flow)[f] ) continue;
    874         Node u=g->head(f);
     874        Node u=g->target(f);
    875875        if ( level[u] >= n ) {
    876876          bfs_queue.push(u);
    … …  
    926926      ResGWOutEdgeIt e=bfs;
    927927      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    928         Node v=res_graph.tail(e);
    929         Node w=res_graph.head(e);
     928        Node v=res_graph.source(e);
     929        Node w=res_graph.target(e);
    930930        pred.set(w, e);
    931931        if (res_graph.valid(pred[v])) {
    … …  
    934934          free.set(w, res_graph.resCap(e));
    935935        }
    936         if (res_graph.head(e)==t) { _augment=true; break; }
     936        if (res_graph.target(e)==t) { _augment=true; break; }
    937937      }
    938938
    … …  
    946946        ResGWEdge e=pred[n];
    947947        res_graph.augment(e, augment_value);
    948         n=res_graph.tail(e);
     948        n=res_graph.source(e);
    949949      }
    950950    }
    … …  
    984984      ResGWOutEdgeIt e=bfs;
    985985      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    986         Node v=res_graph.tail(e);
    987         Node w=res_graph.head(e);
     986        Node v=res_graph.source(e);
     987        Node w=res_graph.target(e);
    988988        pred.set(w, e);
    989989        if (res_graph.valid(pred[v])) {
    … …  
    992992          free.set(w, res_graph.resCap(e));
    993993        }
    994         if (res_graph.head(e)==t) { _augment=true; break; }
     994        if (res_graph.target(e)==t) { _augment=true; break; }
    995995      }
    996996
    … …  
    10041004        ResGWEdge e=pred[n];
    10051005        res_graph.augment(e, augment_value);
    1006         n=res_graph.tail(e);
     1006        n=res_graph.source(e);
    10071007      }
    10081008    }
    … …  
    10511051      if (res_graph.valid(e)) {
    10521052        if (bfs.isBNodeNewlyReached()) {
    1053           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    1054           typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
    1055                                         res_graph_to_F[res_graph.head(e)]);
     1053          dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
     1054          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)],
     1055                                        res_graph_to_F[res_graph.target(e)]);
    10561056          original_edge.update();
    10571057          original_edge.set(f, e);
    … …  
    10591059          residual_capacity.set(f, res_graph.resCap(e));
    10601060        } else {
    1061           if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
    1062             typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
    1063                                           res_graph_to_F[res_graph.head(e)]);
     1061          if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) {
     1062            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)],
     1063                                          res_graph_to_F[res_graph.target(e)]);
    10641064            original_edge.update();
    10651065            original_edge.set(f, e);
    … …  
    11151115          typename MG::Edge e=pred[n];
    11161116          res_graph.augment(original_edge[e], augment_value);
    1117           n=F.tail(e);
     1117          n=F.source(e);
    11181118          if (residual_capacity[e]==augment_value)
    11191119            F.erase(e);
    … …  
    11481148      ResGWOutEdgeIt e=bfs;
    11491149      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    1150         dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     1150        dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
    11511151      }
    11521152      ++bfs;
    … …  
    12481248          typename ErasingResGW::OutEdgeIt e=pred[n];
    12491249          res_graph.augment(e, augment_value);
    1250           n=erasing_res_graph.tail(e);
     1250          n=erasing_res_graph.source(e);
    12511251          if (res_graph.resCap(e)==0)
    12521252            erasing_res_graph.erase(e);

  • src/work/jacint/max_flow_bug.cc

    r921 r986  
    4343  EdgeIt e;
    4444  for(G.first(e); G.valid(e); G.next(e)) {
    45     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
     45    if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
    4646  }
    4747
    … …  
    5050  int min_cut_value=0;
    5151  for(G.first(e); G.valid(e); G.next(e)) {
    52     if (cut[G.tail(e)] && !cut[G.head(e)])
     52    if (cut[G.source(e)] && !cut[G.target(e)])
    5353      min_cut_value+=cap[e];
    5454  }
    … …  
    5858  int max_min_cut_value=0;
    5959  for(G.first(e); G.valid(e); G.next(e)) {
    60     if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
     60    if (maxcut[G.source(e)] && !maxcut[G.target(e)])
    6161      max_min_cut_value+=cap[e];
    6262      }
    … …  
    8989  int min_min_cut_value2=0;
    9090    for(G.first(e); G.valid(e); G.next(e)) {
    91     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
     91    if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
    9292  }
    9393
    … …  
    9696  int min_cut_value2=0;
    9797  for(G.first(e); G.valid(e); G.next(e)) {
    98     if (cut2[G.tail(e)] && !cut2[G.head(e)])
     98    if (cut2[G.source(e)] && !cut2[G.target(e)])
    9999      min_cut_value2+=cap[e];
    100100  }
    … …  
    104104  int max_min_cut_value2=0;
    105105  for(G.first(e); G.valid(e); G.next(e)) {
    106     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
     106    if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
    107107      max_min_cut_value2+=cap[e];
    108108      }
    … …  
    128128  int min_min_cut_value3=0;
    129129  for(G.first(e); G.valid(e); G.next(e)) {
    130     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
     130    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
    131131  }
    132132
    … …  
    135135  int min_cut_value3=0;
    136136  for(G.first(e); G.valid(e); G.next(e)) {
    137     if (cut3[G.tail(e)] && !cut3[G.head(e)])
     137    if (cut3[G.source(e)] && !cut3[G.target(e)])
    138138      min_cut_value3+=cap[e];
    139139  }
    … …  
    143143  int max_min_cut_value3=0;
    144144  for(G.first(e); G.valid(e); G.next(e)) {
    145     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)])
     145    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
    146146      max_min_cut_value3+=cap[e];
    147147  }

  • src/work/jacint/max_flow_test.cc

    r921 r986  
    4646  EdgeIt e;
    4747  for(G.first(e); G.valid(e); G.next(e)) {
    48     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
     48    if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
    4949  }
    5050
    … …  
    5353  int min_cut_value=0;
    5454  for(G.first(e); G.valid(e); G.next(e)) {
    55     if (cut[G.tail(e)] && !cut[G.head(e)])
     55    if (cut[G.source(e)] && !cut[G.target(e)])
    5656      min_cut_value+=cap[e];
    5757  }
    … …  
    6161  int max_min_cut_value=0;
    6262  for(G.first(e); G.valid(e); G.next(e)) {
    63     if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
     63    if (maxcut[G.source(e)] && !maxcut[G.target(e)])
    6464      max_min_cut_value+=cap[e];
    6565      }
    … …  
    9292  int min_min_cut_value2=0;
    9393    for(G.first(e); G.valid(e); G.next(e)) {
    94     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
     94    if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
    9595  }
    9696
    … …  
    9999  int min_cut_value2=0;
    100100  for(G.first(e); G.valid(e); G.next(e)) {
    101     if (cut2[G.tail(e)] && !cut2[G.head(e)])
     101    if (cut2[G.source(e)] && !cut2[G.target(e)])
    102102      min_cut_value2+=cap[e];
    103103  }
    … …  
    107107  int max_min_cut_value2=0;
    108108  for(G.first(e); G.valid(e); G.next(e)) {
    109     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
     109    if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
    110110      max_min_cut_value2+=cap[e];
    111111      }
    … …  
    131131  int min_min_cut_value3=0;
    132132  for(G.first(e); G.valid(e); G.next(e)) {
    133     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
     133    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
    134134  }
    135135
    … …  
    138138  int min_cut_value3=0;
    139139  for(G.first(e); G.valid(e); G.next(e)) {
    140     if (cut3[G.tail(e)] && !cut3[G.head(e)])
     140    if (cut3[G.source(e)] && !cut3[G.target(e)])
    141141      min_cut_value3+=cap[e];
    142142  }
    … …  
    146146  int max_min_cut_value3=0;
    147147  for(G.first(e); G.valid(e); G.next(e)) {
    148     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)])
     148    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
    149149      max_min_cut_value3+=cap[e];
    150150  }

  • src/work/jacint/max_matching.cc

    r921 r986  
    191191  EdgeIt e;
    192192  for(G.first(e); G.valid(e); G.next(e) ) {
    193     if ( (pos[G.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) ||
    194          (pos[G.head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) )
     193    if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||
     194         (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
    195195      noedge=false;
    196196  }

  • src/work/jacint/max_matching.h

    r921 r986  
    154154        Edge e=map[v];
    155155        if ( G.valid(e) )
    156           G.tail(e) == v ? mate.set(v,G.head(e)) : mate.set(v,G.tail(e));
     156          G.source(e) == v ? mate.set(v,G.target(e)) : mate.set(v,G.source(e));
    157157      }
    158158    }
    … …  
    173173      NodeIt e;
    174174      for( G.first(e); G.valid(e); G.next(e)) {
    175         if ( todo[G.head(e)] && todo[G.tail(e)] ) {
    176           Node u=G.tail(e);
    177           Node v=G.head(e);
     175        if ( todo[G.target(e)] && todo[G.source(e)] ) {
     176          Node u=G.source(e);
     177          Node v=G.target(e);
    178178          if ( mate[u]=v && mate[v]=u ) {
    179179            map.set(u,e);
    … …  
    197197      for( G.first(e); G.valid(e); G.next(e)) {
    198198        if ( G.valid(e) ) {
    199           Node u=G.tail(e);       
    200           Node v=G.head(e);
     199          Node u=G.source(e);     
     200          Node v=G.target(e);
    201201          mate.set(u,v);
    202202          mate.set(v,u);
    … …  
    223223      for( G.first(e); G.valid(e); G.next(e)) {
    224224        map.set(e,false);
    225         if ( todo[G.head(e)] && todo[G.tail(e)] ) {
    226           Node u=G.tail(e);
    227           Node v=G.head(e);
     225        if ( todo[G.target(e)] && todo[G.source(e)] ) {
     226          Node u=G.source(e);
     227          Node v=G.target(e);
    228228          if ( mate[u]=v && mate[v]=u ) {
    229229            map.set(e,true);

  • src/work/jacint/max_save.h

    r921 r986  
    259259        OutEdgeIt e;
    260260        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    261           Node v=g->head(e);
     261          Node v=g->target(e);
    262262          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    263263            queue.push(v);
    … …  
    268268        InEdgeIt f;
    269269        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    270           Node v=g->tail(f);
     270          Node v=g->source(f);
    271271          if (!M[v] && (*flow)[f] > 0 ) {
    272272            queue.push(v);
    … …  
    305305        InEdgeIt e;
    306306        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    307           Node v=g->tail(e);
     307          Node v=g->source(e);
    308308          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    309309            queue.push(v);
    … …  
    314314        OutEdgeIt f;
    315315        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    316           Node v=g->head(f);
     316          Node v=g->target(f);
    317317          if (M[v] && (*flow)[f] > 0 ) {
    318318            queue.push(v);
    … …  
    370370           
    371371        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    372         Node v=g->head(e);           
     372        Node v=g->target(e);           
    373373           
    374374        if( lev > level[v] ) { //Push is allowed now
    … …  
    403403         
    404404          if( (*flow)[e] <= 0 ) continue;
    405           Node v=g->tail(e);
     405          Node v=g->source(e);
    406406         
    407407          if( lev > level[v] ) { //Push is allowed now
    … …  
    457457                                  InEdgeIt e;
    458458                                  for(g->first(e,v); g->valid(e); g->next(e)) {
    459                                     Node w=g->tail(e);
     459                                    Node w=g->source(e);
    460460                                    if ( level[w] == n && w != s ) {
    461461                                      bfs_queue.push(w);
    … …  
    475475                                    Num c=(*capacity)[e];
    476476                                    if ( c <= 0 ) continue;
    477                                     Node w=g->head(e);
     477                                    Node w=g->target(e);
    478478                                    if ( level[w] < n ) {         
    479479                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    502502                                  for(g->first(e,v); g->valid(e); g->next(e)) {
    503503                                    if ( (*capacity)[e] <= (*flow)[e] ) continue;
    504                                     Node w=g->tail(e);
     504                                    Node w=g->source(e);
    505505                                    if ( level[w] == n && w != s ) {
    506506                                      bfs_queue.push(w);
    … …  
    516516                                  for(g->first(f,v); g->valid(f); g->next(f)) {
    517517                                    if ( 0 >= (*flow)[f] ) continue;
    518                                     Node w=g->head(f);
     518                                    Node w=g->target(f);
    519519                                    if ( level[w] == n && w != s ) {
    520520                                      bfs_queue.push(w);
    … …  
    535535                                    Num rem=(*capacity)[e]-(*flow)[e];
    536536                                    if ( rem <= 0 ) continue;
    537                                     Node w=g->head(e);
     537                                    Node w=g->target(e);
    538538                                    if ( level[w] < n ) {         
    539539                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    547547                                  {
    548548                                    if ( (*flow)[f] <= 0 ) continue;
    549                                     Node w=g->tail(f);
     549                                    Node w=g->source(f);
    550550                                    if ( level[w] < n ) {         
    551551                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    645645      //        return dist[n]; }
    646646      //       bool get(const typename MapGraphWrapper::Edge& e) const {
    647       //        return (dist.get(g->tail(e))<dist.get(g->head(e))); }
     647      //        return (dist.get(g->source(e))<dist.get(g->target(e))); }
    648648      bool operator[](const typename MapGraphWrapper::Edge& e) const {
    649         return (dist[g->tail(e)]<dist[g->head(e)]);
     649        return (dist[g->source(e)]<dist[g->target(e)]);
    650650      }
    651651    };
    … …  
    784784      for(g->first(e,v); g->valid(e); g->next(e)) {
    785785        if ( (*capacity)[e] <= (*flow)[e] ) continue;
    786         Node u=g->tail(e);
     786        Node u=g->source(e);
    787787        if ( level[u] >= n ) {
    788788          bfs_queue.push(u);
    … …  
    795795      for(g->first(f,v); g->valid(f); g->next(f)) {
    796796        if ( 0 >= (*flow)[f] ) continue;
    797         Node u=g->head(f);
     797        Node u=g->target(f);
    798798        if ( level[u] >= n ) {
    799799          bfs_queue.push(u);
    … …  
    847847      ResGWOutEdgeIt e=bfs;
    848848      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    849         Node v=res_graph.tail(e);
    850         Node w=res_graph.head(e);
     849        Node v=res_graph.source(e);
     850        Node w=res_graph.target(e);
    851851        pred.set(w, e);
    852852        if (res_graph.valid(pred[v])) {
    … …  
    855855          free.set(w, res_graph.resCap(e));
    856856        }
    857         if (res_graph.head(e)==t) { _augment=true; break; }
     857        if (res_graph.target(e)==t) { _augment=true; break; }
    858858      }
    859859       
    … …  
    867867        ResGWEdge e=pred[n];
    868868        res_graph.augment(e, augment_value);
    869         n=res_graph.tail(e);
     869        n=res_graph.source(e);
    870870      }
    871871    }
    … …  
    920920      if (res_graph.valid(e)) {
    921921        if (bfs.isBNodeNewlyReached()) {
    922           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    923           typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     922          dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
     923          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
    924924          original_edge.update();
    925925          original_edge.set(f, e);
    … …  
    927927          residual_capacity.set(f, res_graph.resCap(e));
    928928        } else {
    929           if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
    930             typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     929          if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) {
     930            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
    931931            original_edge.update();
    932932            original_edge.set(f, e);
    … …  
    982982          typename MG::Edge e=pred[n];
    983983          res_graph.augment(original_edge[e], augment_value);
    984           n=F.tail(e);
     984          n=F.source(e);
    985985          if (residual_capacity[e]==augment_value)
    986986            F.erase(e);
    … …  
    10161016      ResGWOutEdgeIt e=bfs;
    10171017      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    1018         dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     1018        dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
    10191019      }
    10201020      ++bfs;
    … …  
    11131113          typename ErasingResGW::OutEdgeIt e=pred[n];
    11141114          res_graph.augment(e, augment_value);
    1115           n=erasing_res_graph.tail(e);
     1115          n=erasing_res_graph.source(e);
    11161116          if (res_graph.resCap(e)==0)
    11171117            erasing_res_graph.erase(e);

  • src/work/jacint/preflow.cc

    r921 r986  
    4747  for(G.first(e); G.valid(e); G.next(e)) {
    4848    int c=cap[e];
    49     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;
    50     if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c;
    51     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;
     49    if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c;
     50    if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c;
     51    if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c;
    5252  }
    5353
    … …  
    8787  for(G.first(e); G.valid(e); G.next(e)) {
    8888    int c=cap[e];
    89     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;
    90     if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c;
    91     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;
     89    if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c;
     90    if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c;
     91    if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c;
    9292  }
    9393
    … …  
    139139  for(G.first(e); G.valid(e); G.next(e)) {
    140140    int c=cap[e];
    141     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;
    142     if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c;
    143     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;
    144     if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;
     141    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c;
     142    if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c;
     143    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c;
     144    if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c;
    145145  }
    146146
    … …  
    196196  for(G.first(e); G.valid(e); G.next(e)) {
    197197    int c=cap[e];
    198     if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;
    199     if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c;
    200     if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;
     198    if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c;
     199    if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c;
     200    if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c;
    201201  }
    202202
    … …  
    239239  for(G.first(e); G.valid(e); G.next(e)) {
    240240    int c=cap[e];
    241     if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;
    242     if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c;
    243     if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;
     241    if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c;
     242    if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c;
     243    if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c;
    244244  }
    245245

  • src/work/jacint/preflow_excess.h

    r921 r986  
    137137          InEdgeIt e;
    138138          for(G.first(e,v); G.valid(e); G.next(e)) {
    139             Node w=G.tail(e);
     139            Node w=G.source(e);
    140140            if ( level[w] == n && w != s ) {
    141141              bfs_queue.push(w);
    … …  
    155155          T c=capacity[e];
    156156          if ( c == 0 ) continue;
    157           Node w=G.head(e);
     157          Node w=G.target(e);
    158158          if ( level[w] < n ) {   
    159159            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    183183          for(G.first(e,v); G.valid(e); G.next(e)) {
    184184            if ( capacity[e] == flow[e] ) continue;
    185             Node w=G.tail(e);
     185            Node w=G.source(e);
    186186            if ( level[w] == n && w != s ) {
    187187              bfs_queue.push(w);
    … …  
    197197          for(G.first(f,v); G.valid(f); G.next(f)) {
    198198            if ( 0 == flow[f] ) continue;
    199             Node w=G.head(f);
     199            Node w=G.target(f);
    200200            if ( level[w] == n && w != s ) {
    201201              bfs_queue.push(w);
    … …  
    248248          T rem=capacity[e]-flow[e];
    249249          if ( rem == 0 ) continue;
    250           Node w=G.head(e);
     250          Node w=G.target(e);
    251251          if ( level[w] < n ) {   
    252252            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    260260        {
    261261          if ( flow[f] == 0 ) continue;
    262           Node w=G.tail(f);
     262          Node w=G.source(f);
    263263          if ( level[w] < n ) {   
    264264            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    304304              for(G.first(e,v); G.valid(e); G.next(e)) {
    305305                if ( capacity[e] == flow[e] ) continue;
    306                 Node u=G.tail(e);
     306                Node u=G.source(e);
    307307                if ( level[u] >= n ) {
    308308                  bfs_queue.push(u);
    … …  
    315315              for(G.first(f,v); G.valid(f); G.next(f)) {
    316316                if ( 0 == flow[f] ) continue;
    317                 Node u=G.head(f);
     317                Node u=G.target(f);
    318318                if ( level[u] >= n ) {
    319319                  bfs_queue.push(u);
    … …  
    344344           
    345345            if ( flow[e] == capacity[e] ) continue;
    346             Node v=G.head(e);           
     346            Node v=G.target(e);           
    347347            //e=wv         
    348348           
    … …  
    386386           
    387387            if( flow[e] == 0 ) continue;
    388             Node v=G.tail(e); 
     388            Node v=G.source(e); 
    389389            //e=vw
    390390           
    … …  
    570570        OutEdgeIt e;
    571571        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    572           Node v=G.head(e);
     572          Node v=G.target(e);
    573573          if (!M[v] && flow[e] < capacity[e] ) {
    574574            queue.push(v);
    … …  
    579579        InEdgeIt f;
    580580        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    581           Node v=G.tail(f);
     581          Node v=G.source(f);
    582582          if (!M[v] && flow[f] > 0 ) {
    583583            queue.push(v);
    … …  
    610610        InEdgeIt e;
    611611        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    612           Node v=G.tail(e);
     612          Node v=G.source(e);
    613613          if (!M[v] && flow[e] < capacity[e] ) {
    614614            queue.push(v);
    … …  
    619619        OutEdgeIt f;
    620620        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    621           Node v=G.head(f);
     621          Node v=G.target(f);
    622622          if (!M[v] && flow[f] > 0 ) {
    623623            queue.push(v);

  • src/work/jacint/preflow_excess_test.cc

    r921 r986  
    5353  EdgeIt e;
    5454  for(G.first(e); G.valid(e); G.next(e)) {
    55     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
     55    if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
    5656  }
    5757
    … …  
    6060  int min_cut_value=0;
    6161  for(G.first(e); G.valid(e); G.next(e)) {
    62     if (cut[G.tail(e)] && !cut[G.head(e)])
     62    if (cut[G.source(e)] && !cut[G.target(e)])
    6363      min_cut_value+=cap[e];
    6464  }
    … …  
    6868  int max_min_cut_value=0;
    6969  for(G.first(e); G.valid(e); G.next(e)) {
    70     if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
     70    if (maxcut[G.source(e)] && !maxcut[G.target(e)])
    7171      max_min_cut_value+=cap[e];
    7272      }
    … …  
    100100  int min_min_cut_value2=0;
    101101    for(G.first(e); G.valid(e); G.next(e)) {
    102     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
     102    if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
    103103  }
    104104
    … …  
    107107  int min_cut_value2=0;
    108108  for(G.first(e); G.valid(e); G.next(e)) {
    109     if (cut2[G.tail(e)] && !cut2[G.head(e)])
     109    if (cut2[G.source(e)] && !cut2[G.target(e)])
    110110      min_cut_value2+=cap[e];
    111111  }
    … …  
    115115  int max_min_cut_value2=0;
    116116  for(G.first(e); G.valid(e); G.next(e)) {
    117     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
     117    if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
    118118      max_min_cut_value2+=cap[e];
    119119      }
    … …  
    145145  int min_min_cut_value3=0;
    146146  for(G.first(e); G.valid(e); G.next(e)) {
    147     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
     147    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
    148148  }
    149149
    … …  
    152152  int min_cut_value3=0;
    153153  for(G.first(e); G.valid(e); G.next(e)) {
    154     if (cut3[G.tail(e)] && !cut3[G.head(e)])
     154    if (cut3[G.source(e)] && !cut3[G.target(e)])
    155155      min_cut_value3+=cap[e];
    156156  }
    … …  
    160160  int max_min_cut_value3=0;
    161161  for(G.first(e); G.valid(e); G.next(e)) {
    162     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)])
     162    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
    163163      max_min_cut_value3+=cap[e];
    164164      }

  • src/work/jacint/preflow_res.h

    r921 r986  
    103103        for(res_graph.first(e,v); res_graph.valid(e);
    104104            res_graph.next(e)) {
    105           Node w=res_graph.tail(e);
     105          Node w=res_graph.source(e);
    106106          if ( level[w] == n && w != s ) {
    107107            bfs_queue.push(w);
    … …  
    146146      for(res_graph.first(e,s); res_graph.valid(e);
    147147          res_graph.next(e)) {
    148           Node w=res_graph.head(e);
     148          Node w=res_graph.target(e);
    149149          if ( level[w] < n ) {   
    150150            if ( excess[w] == 0 && w!=t ) {
    … …  
    191191              for(res_graph.first(e,v);
    192192                  res_graph.valid(e); res_graph.next(e)) {
    193                 Node u=res_graph.tail(e);
     193                Node u=res_graph.source(e);
    194194                if ( level[u] >= n ) {
    195195                  bfs_queue.push(u);
    … …  
    222222          for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) {
    223223           
    224             Node v=res_graph.head(e);           
     224            Node v=res_graph.target(e);           
    225225            if( lev > level[v] ) {     
    226226              /*Push is allowed now*/
    … …  
    401401        OutEdgeIt e;
    402402        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    403           Node v=G.head(e);
     403          Node v=G.target(e);
    404404          if (!M[v] && flow[e] < capacity[e] ) {
    405405            queue.push(v);
    … …  
    410410        InEdgeIt f;
    411411        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    412           Node v=G.tail(f);
     412          Node v=G.source(f);
    413413          if (!M[v] && flow[f] > 0 ) {
    414414            queue.push(v);
    … …  
    441441        InEdgeIt e;
    442442        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    443           Node v=G.tail(e);
     443          Node v=G.source(e);
    444444          if (!M[v] && flow[e] < capacity[e] ) {
    445445            queue.push(v);
    … …  
    450450        OutEdgeIt f;
    451451        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    452           Node v=G.head(f);
     452          Node v=G.target(f);
    453453          if (!M[v] && flow[f] > 0 ) {
    454454            queue.push(v);

  • src/work/jacint/prim.h

    r921 r986  
    9696          OutEdgeIt e;
    9797          for( G.first(e,v); G.valid(e); G.next(e)) {
    98             Node w=G.head(e);
     98            Node w=G.target(e);
    9999           
    100100            if ( !scanned[w] ) {
    … …  
    112112          InEdgeIt f;
    113113          for( G.first(f,v); G.valid(f); G.next(f)) {
    114             Node w=G.tail(f);
     114            Node w=G.source(f);
    115115           
    116116            if ( !scanned[w] ) {
Note: See TracChangeset for help on using the changeset viewer.