src/work/marci/oldies/marci_graph_demo.cc
changeset 1229 aa65e46aebc3
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 */