Changeset 558:4cbfb435ec2b in lemon0.x
 Timestamp:
 05/06/04 19:22:11 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@731
 Location:
 src/work
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/graph_gen.h
r534 r558 1 1 // * c++ * 2 //randomGraph(i,j) gives a random graph on i nodes and j edges.3 2 #include <vector> 4 3 #include <cstdlib> 5 6 //#include <list_graph.h>7 //#include <time_measure.h>8 //#include <for_each_macros.h>9 //#include <bfs_iterator.h>10 //#include <bipartite_graph_wrapper.h>11 //#include <maps.h>12 //#include <max_flow.h>13 4 14 5 namespace hugo { … … 39 30 40 31 32 /// Generates a random graph with n nodes and m edges. 33 /// Before generating the random graph, \c g.clear() is called. 41 34 template<typename Graph> 42 void randomGraph (Graph& g, int n, int m) { 43 typedef typename Graph::Node Node; 35 void randomGraph(Graph& g, int n, int m) { 44 36 g.clear(); 45 std::vector< Node> nodes;37 std::vector<typename Graph::Node> nodes; 46 38 for (int i=0; i<n; ++i) 47 39 nodes.push_back(g.addNode()); … … 50 42 } 51 43 52 } 44 /// Generates a random bipartite graph with a and b nodes 45 /// in the color classes and m edges. 46 /// According to the bipartite graph concept, the resulting 47 /// graph is directed from the first class to the second one. 48 /// Before generating the random graph, \c g.clear() is called. 49 template<typename Graph> 50 void randomBipartiteGraph(Graph& g, int a, int b, int m) { 51 g.clear(); 52 std::vector<typename Graph::Node> s_nodes; 53 std::vector<typename Graph::Node> t_nodes; 54 for (int i=0; i<a; ++i) 55 ///\bug g.addNode(g.S_CLASS) would be better. 56 s_nodes.push_back(g.addNode(false)); 57 for (int i=0; i<b; ++i) 58 ///\bug g.addNode(g.T_CLASS) would be better. 59 t_nodes.push_back(g.addNode(true)); 60 for (int i=0; i<m; ++i) 61 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); 62 } 63 64 } //namespace hugo 
src/work/marci/bipartite_graph_wrapper.h
r557 r558 248 248 249 249 void clear() { 250 FOR_EACH_LOC(typename Parent::EdgeIt, e, G) erase(e);251 FOR_EACH_LOC(typename Parent::NodeIt, n, G) erase(n);250 FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e); 251 FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n); 252 252 } 253 253 }; 
src/work/marci/bipartite_matching_try_3.cc
r555 r558 3 3 #include <fstream> 4 4 #include <vector> 5 #include <cstdlib>6 5 7 6 #include <list_graph.h> … … 14 13 #include <hugo/maps.h> 15 14 #include <max_flow.h> 15 #include <graph_gen.h> 16 16 17 17 using namespace hugo; … … 80 80 }; 81 81 82 /**83 * Inicializalja a veletlenszamgeneratort.84 * Figyelem, ez nem jo igazi random szamokhoz,85 * erre ne bizzad a titkaidat!86 */87 void random_init()88 {89 unsigned int seed = getpid();90 seed = seed << 15;91 seed ^= time(0);92 93 srand(seed);94 }95 96 /**97 * Egy veletlen intet ad vissza 0 es m1 kozott.98 */99 int random(int m)100 {101 return int( double(m) * rand() / (RAND_MAX + 1.0) );102 }103 82 104 83 int main() { … … 113 92 114 93 Graph g; 115 116 std::vector<Graph::Node> s_nodes;117 std::vector<Graph::Node> t_nodes;118 94 119 95 int a; … … 128 104 129 105 std::cout << "Generatig a random bipartite graph..." << std::endl; 130 for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));131 for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));132 133 106 random_init(); 134 for(int i=0; i<m; ++i) { 135 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); 136 } 107 randomBipartiteGraph(g, a, b, m); 137 108 138 109 // std::cout << "Edges of the bipartite graph:" << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.