Changeset 49:f00a4f7e2149 in lemon-0.x for src

Timestamp:

01/30/04 15:55:10 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@64

Message:

marci_graph_demo in new concept

File:

• src/work/marci_graph_demo.cc (modified) (5 diffs)

src/work/marci_graph_demo.cc

@@ -3 +3 @@
 #include <string>
 
-#include <marci_list_graph.hh>
-#include <marci_property_vector.hh>
-#include <marci_bfs.hh>
-#include <marci_max_flow.hh>
+#include <list_graph.hh>
+#include <bfs_iterator.hh>
+#include <edmonds_karp.hh>
 
 using namespace marci;
@@ -12 +11 @@
 int main (int, char*[])
 {
-  typedef list_graph::node_iterator node_iterator;
-  typedef list_graph::edge_iterator edge_iterator;
-  typedef list_graph::each_node_iterator each_node_iterator;
-  typedef list_graph::each_edge_iterator each_edge_iterator;
-  typedef list_graph::out_edge_iterator out_edge_iterator;
-  typedef list_graph::in_edge_iterator in_edge_iterator;
-  typedef list_graph::sym_edge_iterator sym_edge_iterator;
-  list_graph G;
-  std::vector<node_iterator> vector_of_node_iterators;
-  for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  typedef ListGraph::SymEdgeIt SymEdgeIt;
+  ListGraph G;
+  std::vector<NodeIt> vector_of_NodeIts;
+  for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
   for(int i=0; i!=8; ++i)
-    for(int j=0; j!=8; ++j) {
-      if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
-    }  
+    for(int j=0; j!=8; ++j) 
+      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
 
   std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
-  std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
-
-  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+  std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
+
+  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     std::cout << "node " << G.id(i) << std::endl;
-    std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; 
-    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { 
+    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
+    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
     }
@@ -39 +37 @@
 
     std::cout<< " ";
-    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { 
-      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 
-    std::cout<<std::endl;
-
-    std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
-    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { 
+    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
+      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
+    std::cout<<std::endl;
+
+    std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
+    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
       std::cout << j << " "; } 
     std::cout << std::endl;
 
     std::cout<< " ";
-    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { 
-      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 
-    std::cout<<std::endl;
-
-    std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
-    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { 
+    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
+      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
+    std::cout<<std::endl;
+
+    std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
+    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
       std::cout << j << " "; } 
     std::cout<<std::endl;
 
     std::cout<< " ";
-    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { 
-      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 
+    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
+      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
     std::cout<<std::endl;
   }
 
   std::cout << "all edges: ";
-  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
+  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     std::cout << i << " ";
   }
@@ -71 +69 @@
 
   std::cout << "node property array test" << std::endl;
-  node_property_vector<list_graph, int> my_property_vector(G);
-  each_node_iterator v;
-  G.get_first(v);
-  my_property_vector.put(v, 42);
-  my_property_vector.put(++G.first_node(), 314);
-  my_property_vector.put(++++G.first_node(), 1956);
-  my_property_vector.put(vector_of_node_iterators[3], 1989);
-  my_property_vector.put(vector_of_node_iterators[4], 2003);
-  my_property_vector.put(vector_of_node_iterators[7], 1978);
+  ListGraph::NodeMap<int> my_property_vector(G);
+  EachNodeIt v;
+  G.getFirst(v);
+  my_property_vector.set(v, 42);
+  my_property_vector.set(++G.first<EachNodeIt>(), 314);
+  my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
+  my_property_vector.set(vector_of_NodeIts[3], 1989);
+  my_property_vector.set(vector_of_NodeIts[4], 2003);
+  my_property_vector.set(vector_of_NodeIts[7], 1978);
   std::cout << "some node property values..." << std::endl;
-  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     std::cout << my_property_vector.get(i) << std::endl;
   }
   int _i=1;
   int _ii=1;
-  edge_property_vector<list_graph, int> my_edge_property(G);
-  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
-    my_edge_property.put(i, _i);
+  ListGraph::EdgeMap<int> my_edge_property(G);
+  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
+    my_edge_property.set(i, _i);
     _i*=_ii; ++_ii;
   }
 
   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
-  for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
+  for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
   }
   std::cout << std::endl;
 
-  //std::cout << "the same for inedges of the nodes..." << std::endl;
-  //k=0;
-  //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
-  //  for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
-  //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
-  //  }
-  //  std::cout << std::endl;
-  //}
-
   std::cout << "bfs from the first node" << std::endl;
-  bfs<list_graph> bfs_test(G, G.first_node());
+  bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
   bfs_test.run();
   std::cout << "reached: ";
-  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     std::cout << bfs_test.reached.get(i) << " ";
   }
   std::cout<<std::endl;
   std::cout << "dist: ";
-  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     std::cout << bfs_test.dist.get(i) << " ";
   }
@@ -123 +112 @@
 
   std::cout << "augmenting path flow algorithm test..." << std::endl;
-  list_graph flow_test;
-
-  node_iterator s=flow_test.add_node();
-  node_iterator v1=flow_test.add_node();
-  node_iterator v2=flow_test.add_node();
-  node_iterator v3=flow_test.add_node();
-  node_iterator v4=flow_test.add_node();
-  node_iterator t=flow_test.add_node();
+  ListGraph flowG;
+
+  NodeIt s=flowG.addNode();
+  NodeIt v1=flowG.addNode();
+  NodeIt v2=flowG.addNode();
+  NodeIt v3=flowG.addNode();
+  NodeIt v4=flowG.addNode();
+  NodeIt t=flowG.addNode();
   
-  node_property_vector<list_graph, std::string> node_name(flow_test);
-  node_name.put(s, "s");
-  node_name.put(v1, "v1");
-  node_name.put(v2, "v2");
-  node_name.put(v3, "v3");
-  node_name.put(v4, "v4");
-  node_name.put(t, "t");
-
-  edge_iterator s_v1=flow_test.add_edge(s, v1);
-  edge_iterator s_v2=flow_test.add_edge(s, v2);
-  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
-  edge_iterator v2_v1=flow_test.add_edge(v2, v1);
-  edge_iterator v1_v3=flow_test.add_edge(v1, v3);
-  edge_iterator v3_v2=flow_test.add_edge(v3, v2);
-  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
-  edge_iterator v4_v3=flow_test.add_edge(v4, v3);
-  edge_iterator v3_t=flow_test.add_edge(v3, t);
-  edge_iterator v4_t=flow_test.add_edge(v4, t);
-
-  edge_property_vector<list_graph, int> cap(flow_test);
-
-  cap.put(s_v1, 16);
-  cap.put(s_v2, 13);
-  cap.put(v1_v2, 10);
-  cap.put(v2_v1, 4);
-  cap.put(v1_v3, 12);
-  cap.put(v3_v2, 9);
-  cap.put(v2_v4, 14);
-  cap.put(v4_v3, 7);
-  cap.put(v3_t, 20);
-  cap.put(v4_t, 4);
-
-  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
+  ListGraph::NodeMap<std::string> node_name(flowG);
+  node_name.set(s, "s");
+  node_name.set(v1, "v1");
+  node_name.set(v2, "v2");
+  node_name.set(v3, "v3");
+  node_name.set(v4, "v4");
+  node_name.set(t, "t");
+
+  EdgeIt s_v1=flowG.addEdge(s, v1);
+  EdgeIt s_v2=flowG.addEdge(s, v2);
+  EdgeIt v1_v2=flowG.addEdge(v1, v2);
+  EdgeIt v2_v1=flowG.addEdge(v2, v1);
+  EdgeIt v1_v3=flowG.addEdge(v1, v3);
+  EdgeIt v3_v2=flowG.addEdge(v3, v2);
+  EdgeIt v2_v4=flowG.addEdge(v2, v4);
+  EdgeIt v4_v3=flowG.addEdge(v4, v3);
+  EdgeIt v3_t=flowG.addEdge(v3, t);
+  EdgeIt v4_t=flowG.addEdge(v4, t);
+
+  ListGraph::EdgeMap<int> cap(flowG);
+
+  cap.set(s_v1, 16);
+  cap.set(s_v2, 13);
+  cap.set(v1_v2, 10);
+  cap.set(v2_v1, 4);
+  cap.set(v1_v3, 12);
+  cap.set(v3_v2, 9);
+  cap.set(v2_v4, 14);
+  cap.set(v4_v3, 7);
+  cap.set(v3_t, 20);
+  cap.set(v4_t, 4);
+
+  std::cout << "on directed graph graph" << std::endl; //<< flowG;
   std::cout << "names and capacity values" << std::endl; 
-  for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 
+  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
     std::cout << node_name.get(i) << ": ";
     std::cout << "out edges: ";
-    for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) 
-      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
+    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << "in edges: ";
-    for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) 
-      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
+    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << std::endl;
   }
 
+  //flowG.setTail(v3_t, v2);
+  //flowG.setHead(v3_t, s);
+
+  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+    std::cout << node_name.get(i) << ": ";
+    std::cout << "out edges: ";
+    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+    std::cout << "in edges: ";
+    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+    std::cout << std::endl;
+  }
   
-  //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 
-  //  std::cout << i << " ";
-  //}
+
+  /*
+  while (flowG.first<EachEdgeIt>().valid()) {
+    flowG.deleteEdge(flowG.first<EachEdgeIt>());
+    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+      std::cout << node_name.get(i) << ": ";
+      std::cout << "out edges: ";
+      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+      std::cout << "in edges: ";
+      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+      std::cout << std::endl;
+    }
+  }
   
-  max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
+  while (flowG.first<EachNodeIt>().valid()) {
+    flowG.deleteNode(flowG.first<EachNodeIt>());
+    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+      std::cout << node_name.get(i) << ": ";
+      std::cout << "out edges: ";
+      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+      std::cout << "in edges: ";
+      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
+      std::cout << std::endl;
+    }
+  }
+  */
+
+  //ListGraph::EdgeMap<int> flow(flowG, 0);
+  //ResGraph<ListGraph, int> res_graph(flowG, cap, flow); 
+  max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap);
   max_flow_test.run();