COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
11/13/04 13:53:28 (16 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/marci/oldies
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/oldies/edmonds_karp.h

    r921 r986  
    6060        ResGWOutEdgeIt e=bfs;
    6161        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    62           Node v=res_graph.tail(e);
    63           Node w=res_graph.head(e);
     62          Node v=res_graph.source(e);
     63          Node w=res_graph.target(e);
    6464          pred.set(w, e);
    6565          if (res_graph.valid(pred[v])) {
     
    6868            free.set(w, res_graph.resCap(e));
    6969          }
    70           if (res_graph.head(e)==t) { _augment=true; break; }
     70          if (res_graph.target(e)==t) { _augment=true; break; }
    7171        }
    7272       
     
    8080          ResGWEdge e=pred[n];
    8181          res_graph.augment(e, augment_value);
    82           n=res_graph.tail(e);
     82          n=res_graph.source(e);
    8383        }
    8484      }
     
    102102//      return dist[n]; }
    103103//       bool get(const typename MapGraphWrapper::Edge& e) const {
    104 //      return (dist.get(g->tail(e))<dist.get(g->head(e))); }
     104//      return (dist.get(g->source(e))<dist.get(g->target(e))); }
    105105      bool operator[](const typename MapGraphWrapper::Edge& e) const {
    106         return (dist[g->tail(e)]<dist[g->head(e)]);
     106        return (dist[g->source(e)]<dist[g->target(e)]);
    107107      }
    108108    };
     
    124124        ResGWOutEdgeIt e=bfs;
    125125        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    126           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     126          dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
    127127        }
    128128        ++bfs;
     
    153153        typename FilterResGW::EdgeIt e;
    154154        for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
    155           //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    156           typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     155          //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
     156          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
    157157          original_edge.update();
    158158          original_edge.set(f, e);
     
    207207            typename MG::Edge e=pred[n];
    208208            res_graph.augment(original_edge[e], augment_value);
    209             n=F.tail(e);
     209            n=F.source(e);
    210210            if (residual_capacity[e]==augment_value)
    211211              F.erase(e);
     
    255255        if (res_graph.valid(e)) {
    256256          if (bfs.isBNodeNewlyReached()) {
    257             dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    258             typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     257            dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
     258            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
    259259            original_edge.update();
    260260            original_edge.set(f, e);
     
    262262            residual_capacity.set(f, res_graph.resCap(e));
    263263          } else {
    264             if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
    265               typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     264            if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) {
     265              typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
    266266              original_edge.update();
    267267              original_edge.set(f, e);
     
    317317            typename MG::Edge e=pred[n];
    318318            res_graph.augment(original_edge[e], augment_value);
    319             n=F.tail(e);
     319            n=F.source(e);
    320320            if (residual_capacity[e]==augment_value)
    321321              F.erase(e);
     
    344344        ResGWOutEdgeIt e=bfs;
    345345        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    346           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     346          dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
    347347        }
    348348        ++bfs;
     
    441441            typename ErasingResGW::OutEdgeIt e=pred[n];
    442442            res_graph.augment(e, augment_value);
    443             n=erasing_res_graph.tail(e);
     443            n=erasing_res_graph.source(e);
    444444            if (res_graph.resCap(e)==0)
    445445              erasing_res_graph.erase(e);
     
    536536//      AugOutEdgeIt e=bfs;
    537537//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    538 //        Node v=res_graph.tail(e);
    539 //        Node w=res_graph.head(e);
     538//        Node v=res_graph.source(e);
     539//        Node w=res_graph.target(e);
    540540//        pred.set(w, e);
    541541//        if (res_graph.valid(pred.get(v))) {
     
    544544//          free.set(w, res_graph.free(e));
    545545//        }
    546 //        n=res_graph.head(e);
     546//        n=res_graph.target(e);
    547547//        if (T->get(n) && (used.get(n)<1) ) {
    548548//          //Num u=0;
     
    566566//        AugEdge e=pred.get(n);
    567567//        res_graph.augment(e, augment_value);
    568 //        n=res_graph.tail(e);
     568//        n=res_graph.source(e);
    569569//      }
    570570//      used.set(n, 1); //mind2 vegen jav
     
    607607// //   AugOutEdgeIt e=bfs;
    608608// //   if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    609 // //     dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     609// //     dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
    610610// //   }
    611611       
     
    629629// //       //which are in some shortest paths
    630630// //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
    631 // //   if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    632 // //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     631// //   if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
     632// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
    633633// //     original_edge.update();
    634634// //     original_edge.set(f, e);
     
    682682// //       typename MutableGraph::Edge e=pred.get(n);
    683683// //       res_graph.augment(original_edge.get(e), augment_value);
    684 // //       n=F.tail(e);
     684// //       n=F.source(e);
    685685// //       if (residual_capacity.get(e)==augment_value)
    686686// //         F.erase(e);
     
    733733//      typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
    734734//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    735 //        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     735//        dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
    736736//      }
    737737//      ++bfs; 
     
    810810//          EAugEdge e=pred.get(n);
    811811//          res_graph.augment(e, augment_value);
    812 //          n=res_graph.tail(e);
     812//          n=res_graph.source(e);
    813813//          if (res_graph.free(e)==0)
    814814//            res_graph.erase(e);
     
    903903// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    904904// //   if (e.valid() && bfs.isBNodeNewlyReached()) {
    905 // //     Node v=res_graph.tail(e);
    906 // //     Node w=res_graph.head(e);
     905// //     Node v=res_graph.source(e);
     906// //     Node w=res_graph.target(e);
    907907// //     pred.set(w, e);
    908908// //     if (pred.get(v).valid()) {
     
    911911// //       free.set(w, e.free());
    912912// //     }
    913 // //     if (TMap.get(res_graph.head(e))) {
     913// //     if (TMap.get(res_graph.target(e))) {
    914914// //       _augment=true;
    915 // //       reached_t_node=res_graph.head(e);
     915// //       reached_t_node=res_graph.target(e);
    916916// //       break;
    917917// //     }
     
    927927// //     AugEdge e=pred.get(n);
    928928// //     e.augment(augment_value);
    929 // //     n=res_graph.tail(e);
     929// //     n=res_graph.source(e);
    930930// //   }
    931931// //       }
  • src/work/marci/oldies/marci_graph_demo.cc

    r921 r986  
    3232    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
    3333    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
    34       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
     34      std::cout << "(" << G.id(G.source(j)) << "--" << G.id(j) << "->" << G.id(G.target(j)) << ") ";
    3535    }
    3636    std::cout << std::endl;
     
    9090  }
    9191
    92   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
     92  std::cout << "node and edge property values on the sources and targets of edges..." << std::endl;
    9393  for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
    94     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
     94    std::cout << my_property_vector.get(G.source(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.target(j)) << " ";
    9595  }
    9696  std::cout << std::endl;
     
    159159    std::cout << "out edges: ";
    160160    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    161       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     161      std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    162162    std::cout << "in edges: ";
    163163    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    164       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     164      std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    165165    std::cout << std::endl;
    166166  }
     
    172172 
    173173
    174   //flowG.setTail(v3_t, v2);
    175   //flowG.setHead(v3_t, s);
     174  //flowG.setSource(v3_t, v2);
     175  //flowG.setTarget(v3_t, s);
    176176/*
    177177  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
     
    179179    std::cout << "out edges: ";
    180180    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    181       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     181      std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    182182    std::cout << "in edges: ";
    183183    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    184       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     184      std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    185185    std::cout << std::endl;
    186186  }
    187187 
    188188  for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    189     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
     189    std::cout << node_name.get(flowG.source(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.target(e)) << " ";
    190190  }
    191191*/
     
    197197      std::cout << "out edges: ";
    198198      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    199         std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     199        std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    200200      std::cout << "in edges: ";
    201201      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    202         std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     202        std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    203203      std::cout << std::endl;
    204204    }
     
    211211      std::cout << "out edges: ";
    212212      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    213         std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     213        std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    214214      std::cout << "in edges: ";
    215215      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    216         std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     216        std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " ";
    217217      std::cout << std::endl;
    218218    }
     
    229229    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    230230    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    231       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     231      std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") ";
    232232    }
    233233    std::cout<<std::endl;
    234234    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    235235    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    236       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     236      std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") ";
    237237    }
    238238    std::cout<<std::endl;*/
     
    242242    while (max_flow_test.augmentOnShortestPath()) {
    243243      for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    244         std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     244        std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") ";
    245245      }
    246246      std::cout<<std::endl;
     
    261261    std::cout << "maximum flow: "<< std::endl;
    262262    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    263       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     263      std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") ";
    264264    }
    265265    std::cout<<std::endl;
Note: See TracChangeset for help on using the changeset viewer.