Changeset 49:f00a4f7e2149 in lemon0.x for src
 Timestamp:
 01/30/04 15:55:10 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@64
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci_graph_demo.cc
r19 r49 3 3 #include <string> 4 4 5 #include <marci_list_graph.hh> 6 #include <marci_property_vector.hh> 7 #include <marci_bfs.hh> 8 #include <marci_max_flow.hh> 5 #include <list_graph.hh> 6 #include <bfs_iterator.hh> 7 #include <edmonds_karp.hh> 9 8 10 9 using namespace marci; … … 12 11 int main (int, char*[]) 13 12 { 14 typedef list_graph::node_iterator node_iterator;15 typedef list_graph::edge_iterator edge_iterator;16 typedef list_graph::each_node_iterator each_node_iterator;17 typedef list_graph::each_edge_iterator each_edge_iterator;18 typedef list_graph::out_edge_iterator out_edge_iterator;19 typedef list_graph::in_edge_iterator in_edge_iterator;20 typedef list_graph::sym_edge_iterator sym_edge_iterator;21 list_graph G;22 std::vector< node_iterator> vector_of_node_iterators;23 for(int i=0; i!=8; ++i) vector_of_ node_iterators.push_back(G.add_node());13 typedef ListGraph::NodeIt NodeIt; 14 typedef ListGraph::EdgeIt EdgeIt; 15 typedef ListGraph::EachNodeIt EachNodeIt; 16 typedef ListGraph::EachEdgeIt EachEdgeIt; 17 typedef ListGraph::OutEdgeIt OutEdgeIt; 18 typedef ListGraph::InEdgeIt InEdgeIt; 19 typedef ListGraph::SymEdgeIt SymEdgeIt; 20 ListGraph G; 21 std::vector<NodeIt> vector_of_NodeIts; 22 for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode()); 24 23 for(int i=0; i!=8; ++i) 25 for(int j=0; j!=8; ++j) { 26 if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]); 27 } 24 for(int j=0; j!=8; ++j) 25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]); 28 26 29 27 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; 30 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;31 32 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {28 std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl; 29 30 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 33 31 std::cout << "node " << G.id(i) << std::endl; 34 std::cout << " outdegree ( out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";35 for( out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 36 34 std::cout << "(" << G.id(G.tail(j)) << "" << G.id(j) << ">" << G.id(G.head(j)) << ") "; 37 35 } … … 39 37 40 38 std::cout<< " "; 41 for( out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {42 std::cout << G.a _node(j) << ">" << G.b_node(j) << " "; }43 std::cout<<std::endl; 44 45 std::cout << " indegree: ( in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";46 for( in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 40 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 41 std::cout<<std::endl; 42 43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " "; 44 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 47 45 std::cout << j << " "; } 48 46 std::cout << std::endl; 49 47 50 48 std::cout<< " "; 51 for( in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {52 std::cout << G.a _node(j) << ">" << G.b_node(j) << " "; }53 std::cout<<std::endl; 54 55 std::cout << " degree: ( sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";56 for( sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {49 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 50 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 51 std::cout<<std::endl; 52 53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " "; 54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 57 55 std::cout << j << " "; } 58 56 std::cout<<std::endl; 59 57 60 58 std::cout<< " "; 61 for( sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {62 std::cout << G.a _node(j) << ">" << G.b_node(j) << " "; }59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 60 std::cout << G.aNode(j) << ">" << G.bNode(j) << " "; } 63 61 std::cout<<std::endl; 64 62 } 65 63 66 64 std::cout << "all edges: "; 67 for( each_edge_iterator i=G.first_edge(); i.valid(); ++i) {65 for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) { 68 66 std::cout << i << " "; 69 67 } … … 71 69 72 70 std::cout << "node property array test" << std::endl; 73 node_property_vector<list_graph,int> my_property_vector(G);74 each_node_iteratorv;75 G.get _first(v);76 my_property_vector. put(v, 42);77 my_property_vector. put(++G.first_node(), 314);78 my_property_vector. put(++++G.first_node(), 1956);79 my_property_vector. put(vector_of_node_iterators[3], 1989);80 my_property_vector. put(vector_of_node_iterators[4], 2003);81 my_property_vector. put(vector_of_node_iterators[7], 1978);71 ListGraph::NodeMap<int> my_property_vector(G); 72 EachNodeIt v; 73 G.getFirst(v); 74 my_property_vector.set(v, 42); 75 my_property_vector.set(++G.first<EachNodeIt>(), 314); 76 my_property_vector.set(++++G.first<EachNodeIt>(), 1956); 77 my_property_vector.set(vector_of_NodeIts[3], 1989); 78 my_property_vector.set(vector_of_NodeIts[4], 2003); 79 my_property_vector.set(vector_of_NodeIts[7], 1978); 82 80 std::cout << "some node property values..." << std::endl; 83 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {81 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 84 82 std::cout << my_property_vector.get(i) << std::endl; 85 83 } 86 84 int _i=1; 87 85 int _ii=1; 88 edge_property_vector<list_graph,int> my_edge_property(G);89 for( each_edge_iterator i=G.first_edge(); i.valid(); ++i) {90 my_edge_property. put(i, _i);86 ListGraph::EdgeMap<int> my_edge_property(G); 87 for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) { 88 my_edge_property.set(i, _i); 91 89 _i*=_ii; ++_ii; 92 90 } 93 91 94 92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; 95 for( each_edge_iterator j=G.first_edge(); j.valid(); ++j) {93 for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) { 96 94 std::cout << my_property_vector.get(G.tail(j)) << "" << my_edge_property.get(j) << ">" << my_property_vector.get(G.head(j)) << " "; 97 95 } 98 96 std::cout << std::endl; 99 97 100 //std::cout << "the same for inedges of the nodes..." << std::endl;101 //k=0;102 //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {103 // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {104 // std::cout << my_property_vector.get(G.tail(j)) << ">" << my_property_vector.get(G.head(j)) << " ";105 // }106 // std::cout << std::endl;107 //}108 109 98 std::cout << "bfs from the first node" << std::endl; 110 bfs< list_graph> bfs_test(G, G.first_node());99 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>()); 111 100 bfs_test.run(); 112 101 std::cout << "reached: "; 113 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {102 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 114 103 std::cout << bfs_test.reached.get(i) << " "; 115 104 } 116 105 std::cout<<std::endl; 117 106 std::cout << "dist: "; 118 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {107 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 119 108 std::cout << bfs_test.dist.get(i) << " "; 120 109 } … … 123 112 124 113 std::cout << "augmenting path flow algorithm test..." << std::endl; 125 list_graph flow_test;126 127 node_iterator s=flow_test.add_node();128 node_iterator v1=flow_test.add_node();129 node_iterator v2=flow_test.add_node();130 node_iterator v3=flow_test.add_node();131 node_iterator v4=flow_test.add_node();132 node_iterator t=flow_test.add_node();114 ListGraph flowG; 115 116 NodeIt s=flowG.addNode(); 117 NodeIt v1=flowG.addNode(); 118 NodeIt v2=flowG.addNode(); 119 NodeIt v3=flowG.addNode(); 120 NodeIt v4=flowG.addNode(); 121 NodeIt t=flowG.addNode(); 133 122 134 node_property_vector<list_graph, std::string> node_name(flow_test);135 node_name. put(s, "s");136 node_name. put(v1, "v1");137 node_name. put(v2, "v2");138 node_name. put(v3, "v3");139 node_name. put(v4, "v4");140 node_name. put(t, "t");141 142 edge_iterator s_v1=flow_test.add_edge(s, v1);143 edge_iterator s_v2=flow_test.add_edge(s, v2);144 edge_iterator v1_v2=flow_test.add_edge(v1, v2);145 edge_iterator v2_v1=flow_test.add_edge(v2, v1);146 edge_iterator v1_v3=flow_test.add_edge(v1, v3);147 edge_iterator v3_v2=flow_test.add_edge(v3, v2);148 edge_iterator v2_v4=flow_test.add_edge(v2, v4);149 edge_iterator v4_v3=flow_test.add_edge(v4, v3);150 edge_iterator v3_t=flow_test.add_edge(v3, t);151 edge_iterator v4_t=flow_test.add_edge(v4, t);152 153 edge_property_vector<list_graph, int> cap(flow_test);154 155 cap. put(s_v1, 16);156 cap. put(s_v2, 13);157 cap. put(v1_v2, 10);158 cap. put(v2_v1, 4);159 cap. put(v1_v3, 12);160 cap. put(v3_v2, 9);161 cap. put(v2_v4, 14);162 cap. put(v4_v3, 7);163 cap. put(v3_t, 20);164 cap. put(v4_t, 4);165 166 std::cout << "on directed graph graph" << std::endl; //<< flow _test;123 ListGraph::NodeMap<std::string> node_name(flowG); 124 node_name.set(s, "s"); 125 node_name.set(v1, "v1"); 126 node_name.set(v2, "v2"); 127 node_name.set(v3, "v3"); 128 node_name.set(v4, "v4"); 129 node_name.set(t, "t"); 130 131 EdgeIt s_v1=flowG.addEdge(s, v1); 132 EdgeIt s_v2=flowG.addEdge(s, v2); 133 EdgeIt v1_v2=flowG.addEdge(v1, v2); 134 EdgeIt v2_v1=flowG.addEdge(v2, v1); 135 EdgeIt v1_v3=flowG.addEdge(v1, v3); 136 EdgeIt v3_v2=flowG.addEdge(v3, v2); 137 EdgeIt v2_v4=flowG.addEdge(v2, v4); 138 EdgeIt v4_v3=flowG.addEdge(v4, v3); 139 EdgeIt v3_t=flowG.addEdge(v3, t); 140 EdgeIt v4_t=flowG.addEdge(v4, t); 141 142 ListGraph::EdgeMap<int> cap(flowG); 143 144 cap.set(s_v1, 16); 145 cap.set(s_v2, 13); 146 cap.set(v1_v2, 10); 147 cap.set(v2_v1, 4); 148 cap.set(v1_v3, 12); 149 cap.set(v3_v2, 9); 150 cap.set(v2_v4, 14); 151 cap.set(v4_v3, 7); 152 cap.set(v3_t, 20); 153 cap.set(v4_t, 4); 154 155 std::cout << "on directed graph graph" << std::endl; //<< flowG; 167 156 std::cout << "names and capacity values" << std::endl; 168 for( each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {157 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 169 158 std::cout << node_name.get(i) << ": "; 170 159 std::cout << "out edges: "; 171 for( out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)172 std::cout << node_name.get(flow _test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 161 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 173 162 std::cout << "in edges: "; 174 for( in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)175 std::cout << node_name.get(flow _test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 164 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 176 165 std::cout << std::endl; 177 166 } 178 167 168 //flowG.setTail(v3_t, v2); 169 //flowG.setHead(v3_t, s); 170 171 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 172 std::cout << node_name.get(i) << ": "; 173 std::cout << "out edges: "; 174 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 175 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 176 std::cout << "in edges: "; 177 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 178 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 179 std::cout << std::endl; 180 } 179 181 180 //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 181 // std::cout << i << " "; 182 //} 182 183 /* 184 while (flowG.first<EachEdgeIt>().valid()) { 185 flowG.deleteEdge(flowG.first<EachEdgeIt>()); 186 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 187 std::cout << node_name.get(i) << ": "; 188 std::cout << "out edges: "; 189 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 190 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 191 std::cout << "in edges: "; 192 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 193 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 194 std::cout << std::endl; 195 } 196 } 183 197 184 max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap); 198 while (flowG.first<EachNodeIt>().valid()) { 199 flowG.deleteNode(flowG.first<EachNodeIt>()); 200 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 201 std::cout << node_name.get(i) << ": "; 202 std::cout << "out edges: "; 203 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 204 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 205 std::cout << "in edges: "; 206 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 207 std::cout << node_name.get(flowG.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flowG.head(j)) << " "; 208 std::cout << std::endl; 209 } 210 } 211 */ 212 213 //ListGraph::EdgeMap<int> flow(flowG, 0); 214 //ResGraph<ListGraph, int> res_graph(flowG, cap, flow); 215 max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap); 185 216 max_flow_test.run(); 186 217
Note: See TracChangeset
for help on using the changeset viewer.