RandomGraphFactory.hpp

Go to the documentation of this file.

 
// Copyright (c) 2017 Czech Technical University in Prague | Faculty of Information Technology. All rights reserved.
 
#pragma once
 
#include <alib/pair>
#include <alib/vector>
#include <alib/tuple>
#include <random>
 
namespace graph {
 
namespace generate {
 
class RandomGraphFactory {
// ---------------------------------------------------------------------------------------------------------------------
 public:
  template<typename TGraph>
  static
  ext::tuple<TGraph, typename TGraph::node_type, typename TGraph::node_type>
  randomGraph(unsigned long max_nodes, unsigned long branching_factor);
 
// ---------------------------------------------------------------------------------------------------------------------
 
  template<typename TGraph>
  static
  ext::tuple<TGraph, typename TGraph::node_type, typename TGraph::node_type>
  randomWeightedGraph(unsigned long max_nodes,
                      unsigned long branching_factor,
                      long max_weight);
 
// ---------------------------------------------------------------------------------------------------------------------
 
};
 
// =====================================================================================================================
 
template<typename TGraph>
ext::tuple<TGraph, typename TGraph::node_type, typename TGraph::node_type>
RandomGraphFactory::randomGraph(unsigned long max_nodes,
                                unsigned long branching_factor) {
  using node_type = typename TGraph::node_type;
 
  // Seed with a real random value, if available
  std::random_device r;
  std::default_random_engine e1(r());
 
  // Create distribution
  std::uniform_int_distribution<unsigned long> number_of_nodes(1, max_nodes); // Generate number of nodes
  std::uniform_int_distribution<unsigned long>
      number_of_edges(1, branching_factor); // Generate number of edges for each node
 
  unsigned long node_cnt = number_of_nodes(e1);
 
  std::uniform_int_distribution<node_type> node_id(0, node_cnt * 10); // Generate indexes of nodes
  std::uniform_int_distribution<long> random_node(0, node_cnt - 1); // Generate random index in vector of nodes
 
  TGraph graph;
 
  // Add nodes
  ext::vector<node_type> nodes;
 
  // Generate start and goal node
  node_type start(node_id(e1));
  node_type goal(node_id(e1));
  nodes.push_back(start);
  graph.addNode(start);
  nodes.push_back(goal);
  graph.addNode(goal);
 
  // Generate nodes
  for (unsigned long i = 0; i < node_cnt; ++i) {
    node_type node(node_id(e1));
    graph.addNode(node);
    nodes.push_back(node);
  }
 
  // Generate edges
  for (const auto &v : nodes) {
    unsigned long cnt = number_of_edges(e1); // Generate number of edges for current v
    for (unsigned long i = 0; i < cnt; ++i) {
      long w = random_node(e1); // Get target v
      graph.addEdge(v, nodes.at(w));
    }
  }
 
  return ext::make_tuple(graph, start, goal);
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TGraph>
ext::tuple<TGraph, typename TGraph::node_type, typename TGraph::node_type>
RandomGraphFactory::randomWeightedGraph(
    unsigned long max_nodes,
    unsigned long branching_factor,
    long max_weight) {
  using node_type = typename TGraph::node_type;
  using weight_type = typename TGraph::edge_type::weight_type;
 
  // Seed with a real random value, if available
  std::random_device r;
  std::default_random_engine e1(r());
 
  // Create distribution
  std::uniform_int_distribution<unsigned long> number_of_nodes(1, max_nodes); // Generate number of nodes
  std::uniform_int_distribution<unsigned long>
      number_of_edges(1, branching_factor); // Generate number of edges for each node
  std::uniform_real_distribution<weight_type> edge_weight(1, max_weight); // Generate edge weight
 
  unsigned long node_cnt = number_of_nodes(e1);
 
  std::uniform_int_distribution<node_type> node_id(0, node_cnt * 10); // Generate indexes of nodes
  std::uniform_int_distribution<long> random_node(0, node_cnt - 1); // Generate random index in vector of nodes
 
  TGraph graph;
 
  // Add nodes
  ext::vector<node_type> nodes;
 
  // Generate start and goal node
  node_type start(node_id(e1));
  node_type goal(node_id(e1));
  nodes.push_back(start);
  graph.addNode(start);
  nodes.push_back(goal);
  graph.addNode(goal);
 
  // Generate nodes
  for (unsigned long i = 0; i < node_cnt; ++i) {
    node_type node(node_id(e1));
    graph.addNode(node);
    nodes.push_back(node);
  }
 
  // Generate edges
  for (const auto &v : nodes) {
    unsigned long cnt = number_of_edges(e1); // Generate number of edges for current v
    for (unsigned long i = 0; i < cnt; ++i) {
      long w = random_node(e1); // Get target v
      graph.addEdge(v, nodes.at(w), edge_weight(e1));
    }
  }
 
  return ext::make_tuple(graph, start, goal);
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace generate
 
} // namespace graph