COIN-OR::LEMON - Graph Library

Changeset 558:4cbfb435ec2b in lemon-0.x for src/work


Ignore:
Timestamp:
05/06/04 19:22:11 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@731
Message:

random graph, random bipartite graph in jacint/graph_gen.h

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/graph_gen.h

    r534 r558  
    11// -*- c++ -*-
    2 //randomGraph(i,j) gives a random graph on i nodes and j edges.
    32#include <vector>
    43#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>
    134
    145namespace hugo {
     
    3930
    4031
     32  /// Generates a random graph with n nodes and m edges.
     33  /// Before generating the random graph, \c g.clear() is called.
    4134  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) {
    4436    g.clear();
    45     std::vector<Node> nodes;
     37    std::vector<typename Graph::Node> nodes;
    4638    for (int i=0; i<n; ++i)
    4739      nodes.push_back(g.addNode());
     
    5042  }
    5143
    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  
    248248   
    249249    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);
    252252    }
    253253  };
  • src/work/marci/bipartite_matching_try_3.cc

    r555 r558  
    33#include <fstream>
    44#include <vector>
    5 #include <cstdlib>
    65
    76#include <list_graph.h>
     
    1413#include <hugo/maps.h>
    1514#include <max_flow.h>
     15#include <graph_gen.h>
    1616
    1717using namespace hugo;
     
    8080};
    8181
    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 int-et ad vissza 0 es m-1 kozott.
    98  */
    99 int random(int m)
    100 {
    101   return int( double(m) * rand() / (RAND_MAX + 1.0) );
    102 }
    10382
    10483int main() {
     
    11392
    11493  Graph g;
    115 
    116   std::vector<Graph::Node> s_nodes;
    117   std::vector<Graph::Node> t_nodes;
    11894
    11995  int a;
     
    128104 
    129105  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 
    133106  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);
    137108
    138109//   std::cout << "Edges of the bipartite graph:" << std::endl;
Note: See TracChangeset for help on using the changeset viewer.