Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/oldies/marci_graph_demo.cc
changeset 1252 4fee8e9d9014
parent 921 818510fa3d99
equal deleted inserted replaced
1:a3aebefe4e2f 2:1a8a8b276066 
    29 
    29 
    30   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
    30   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
    31     std::cout << "node " << G.id(i) << std::endl;
 
    31     std::cout << "node " << G.id(i) << std::endl;
 
    32     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
    32     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
    33     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
    33     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)) << ") ";
 
    35     }
 
    35     }
 
    36     std::cout << std::endl; 
    36     std::cout << std::endl; 
    37 
    37 
    38     std::cout<< " ";
 
    38     std::cout<< " ";
 
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
    87   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
 
    87   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
 
    88     my_edge_property.set(i, _i);
 
    88     my_edge_property.set(i, _i);
 
    89     _i*=_ii; ++_ii;
 
    89     _i*=_ii; ++_ii;
 
    90   }
 
    90   }
 
    91 
    91 
    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;
 
    93   for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
 
    93   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)) << " ";
 
    95   }
 
    95   }
 
    96   std::cout << std::endl;
 
    96   std::cout << std::endl;
 
    97 /*
 
    97 /*
 
    98   std::cout << "bfs from the first node" << std::endl;
 
    98   std::cout << "bfs from the first node" << std::endl;
 
    99   bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
 
    99   bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
 
   156   std::cout << "names and capacity values" << std::endl; 
   156   std::cout << "names and capacity values" << std::endl; 
   157   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   157   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   158     std::cout << node_name.get(i) << ": ";
 
   158     std::cout << node_name.get(i) << ": ";
 
   159     std::cout << "out edges: ";
 
   159     std::cout << "out edges: ";
 
   160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   160     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)) << " ";
 
   162     std::cout << "in edges: ";
 
   162     std::cout << "in edges: ";
 
   163     for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   163     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)) << " ";
 
   165     std::cout << std::endl;
 
   165     std::cout << std::endl;
 
   166   }
 
   166   }
 
   167 
   167 
   168   //flowG.deleteEdge(s_v1);
 
   168   //flowG.deleteEdge(s_v1);
 
   169   //flowG.deleteEdge(s_v2);
 
   169   //flowG.deleteEdge(s_v2);
 
   170   //flowG.deleteEdge(v1_v2);
 
   170   //flowG.deleteEdge(v1_v2);
 
   171   //flowG.deleteEdge(v1_v3);
 
   171   //flowG.deleteEdge(v1_v3);
 
   172   
   172   
   173 
   173 
   174   //flowG.setTail(v3_t, v2);
 
   174   //flowG.setSource(v3_t, v2);
 
   175   //flowG.setHead(v3_t, s);
 
   175   //flowG.setTarget(v3_t, s);
 
   176 /*
 
   176 /*
 
   177   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   177   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   178     std::cout << node_name.get(i) << ": ";
 
   178     std::cout << node_name.get(i) << ": ";
 
   179     std::cout << "out edges: ";
 
   179     std::cout << "out edges: ";
 
   180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   180     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)) << " ";
 
   182     std::cout << "in edges: ";
 
   182     std::cout << "in edges: ";
 
   183     for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   183     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)) << " ";
 
   185     std::cout << std::endl;
 
   185     std::cout << std::endl;
 
   186   }
 
   186   }
 
   187   
   187   
   188   for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
 
   188   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)) << " ";
 
   190   }
 
   190   }
 
   191 */
 
   191 */
 
   192   /*
 
   192   /*
 
   193   while (flowG.valid(flowG.first<EdgeIt>())) {
 
   193   while (flowG.valid(flowG.first<EdgeIt>())) {
 
   194     flowG.deleteEdge(flowG.first<EdgeIt>());
 
   194     flowG.deleteEdge(flowG.first<EdgeIt>());
 
   195     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   195     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   196       std::cout << node_name.get(i) << ": ";
 
   196       std::cout << node_name.get(i) << ": ";
 
   197       std::cout << "out edges: ";
 
   197       std::cout << "out edges: ";
 
   198       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   198       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)) << " ";
 
   200       std::cout << "in edges: ";
 
   200       std::cout << "in edges: ";
 
   201       for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   201       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)) << " ";
 
   203       std::cout << std::endl;
 
   203       std::cout << std::endl;
 
   204     }
 
   204     }
 
   205   }
 
   205   }
 
   206   
   206   
   207   while (flowG.valid(flowG.first<NodeIt>())) {
 
   207   while (flowG.valid(flowG.first<NodeIt>())) {
 
   208     flowG.deleteNode(flowG.first<NodeIt>());
 
   208     flowG.deleteNode(flowG.first<NodeIt>());
 
   209     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   209     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   210       std::cout << node_name.get(i) << ": ";
 
   210       std::cout << node_name.get(i) << ": ";
 
   211       std::cout << "out edges: ";
 
   211       std::cout << "out edges: ";
 
   212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   212       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)) << " ";
 
   214       std::cout << "in edges: ";
 
   214       std::cout << "in edges: ";
 
   215       for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
   215       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)) << " ";
 
   217       std::cout << std::endl;
 
   217       std::cout << std::endl;
 
   218     }
 
   218     }
 
   219   }
 
   219   }
 
   220   */
 
   220   */
 
   221 
   221 
   226     ListGraph::EdgeMap<int> flow(flowG, 0);
 
   226     ListGraph::EdgeMap<int> flow(flowG, 0);
 
   227     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
 
   227     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
 
   228     /*
 
   228     /*
 
   229     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   229     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   230     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
   230     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)<<") ";
 
   232     }
 
   232     }
 
   233     std::cout<<std::endl;
 
   233     std::cout<<std::endl;
 
   234     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   234     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   235     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
   235     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)<<") ";
 
   237     }
 
   237     }
 
   238     std::cout<<std::endl;*/
 
   238     std::cout<<std::endl;*/
 
   239     //max_flow_test.run();
 
   239     //max_flow_test.run();
 
   240     
   240     
   241     //std::cout << "maximum flow: "<< std::endl;
 
   241     //std::cout << "maximum flow: "<< std::endl;
 
   242     while (max_flow_test.augmentOnShortestPath()) {
 
   242     while (max_flow_test.augmentOnShortestPath()) {
 
   243       for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
   243       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)<<") ";
 
   245       }
 
   245       }
 
   246       std::cout<<std::endl;
 
   246       std::cout<<std::endl;
 
   247     }
 
   247     }
 
   248     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   248     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   249   }
 
   249   }
 
   258     MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
 
   258     MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
 
   259     max_flow_test.run();
 
   259     max_flow_test.run();
 
   260     
   260     
   261     std::cout << "maximum flow: "<< std::endl;
 
   261     std::cout << "maximum flow: "<< std::endl;
 
   262     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
   262     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)<<") ";
 
   264     }
 
   264     }
 
   265     std::cout<<std::endl;
 
   265     std::cout<<std::endl;
 
   266     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   266     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   267   }
 
   267   }
 
   268 */
 
   268 */
lemon-0.x