Random Graph Utilities

Defined in: <boost/graph/random.hpp>

Routines to create random graphs, select random vertices and edges, and randomize properties.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <iostream>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS,
    no_property, property<edge_weight_t, double>>;

int main() {
    Graph g;
    mt19937 gen(42);

    bool allow_parallel = true;
    bool allow_self_loops = false;
    generate_random_graph(g, 5, 8, gen, allow_parallel, allow_self_loops);
    std::cout << num_vertices(g) << " vertices, " << num_edges(g) << " edges\n";

    // Assign random weights to all edges
    randomize_property<edge_weight_t>(g, gen);

    std::cout << "random vertex: " << random_vertex(g, gen) << "\n";

    auto e = random_edge(g, gen);
    std::cout << "random edge: " << source(e, g) << " -> " << target(e, g) << "\n";

    if (out_degree(vertex(0, g), g) > 0) {
        auto oe = random_out_edge(g, vertex(0, g), gen);
        std::cout << "random out-edge of 0: "
                  << source(oe, g) << " -> " << target(oe, g) << "\n";

        auto we = weighted_random_out_edge(g, vertex(0, g), get(edge_weight, g), gen);
        std::cout << "weighted random out-edge of 0: "
                  << source(we, g) << " -> " << target(we, g) << "\n";
    }
}

5 vertices, 8 edges
random vertex: 1
random edge: 0 -> 2
random out-edge of 0: 0 -> 2
weighted random out-edge of 0: 0 -> 2

generate_random_graph

template <typename MutableGraph, typename RandNumGen>
void generate_random_graph(MutableGraph& g, vertices_size_type V, vertices_size_type E, RandNumGen& gen, bool allow_parallel = true, bool self_edges = false);

Adds V vertices and E random edges to g. If allow_parallel is false, duplicate edges are rejected. If self_edges is false, no edge will connect a vertex to itself.

Precondition: num_vertices(g) == 0
Complexity: O(V * E)

Overload that outputs created vertices and edges through iterators:

template <typename MutableGraph, typename RandNumGen, typename VertexOutputIterator, typename EdgeOutputIterator>
void generate_random_graph(MutableGraph& g, vertices_size_type V, vertices_size_type E, RandNumGen& gen, VertexOutputIterator vertex_out, EdgeOutputIterator edge_out, bool self_edges = false);

random_vertex

template <typename Graph, typename RandomNumGen>
vertex_descriptor random_vertex(Graph& g, RandomNumGen& gen);

Returns a uniformly random vertex from g.

Precondition: num_vertices(g) > 0
Complexity: O(num_vertices(g))

random_edge

template <typename Graph, typename RandomNumGen>
edge_descriptor random_edge(Graph& g, RandomNumGen& gen);

Returns a uniformly random edge from g.

Precondition: num_edges(g) > 0
Complexity: O(num_edges(g))

random_out_edge

template <typename Graph, typename RandomNumGen>
edge_descriptor random_out_edge(Graph& g, vertex_descriptor src, RandomNumGen& gen);

Returns a uniformly random out-edge of vertex src.

Precondition: out_degree(src, g) > 0
Complexity: O(out_degree(src, g))

weighted_random_out_edge

template <typename Graph, typename WeightMap, typename RandomNumGen>
edge_descriptor weighted_random_out_edge(Graph& g, vertex_descriptor src, WeightMap weight, RandomNumGen& gen);

Returns a random out-edge of vertex src, where each edge is selected with probability proportional to its weight. WeightMap must be a Readable Property Map with key type edge_descriptor.

Precondition: out_degree(src, g) > 0 and total weight > 0
Complexity: O(out_degree(src, g))

randomize_property

template <typename Property, typename G, typename RandomGenerator>
void randomize_property(G& g, RandomGenerator& rg);

Assigns a random value to Property on every vertex or every edge, depending on whether Property has vertex_property_tag or edge_property_tag kind.

Complexity: O(V) or O(E) depending on property kind.

Edit this Page