graph_utils.hpp

This file provides a number of tools for manipulating graphs.

Note

Status: BETA

Functions

Graph shuffle_graph(const Graph &in_graph, Random &random)

Take an existing graph, and build a new one that is isomorphic to it, but with randomized vertex IDs.

Graph build_graph_ring(size_t v_count, Random &random)

Construct a graph where all vertics are degree two and form a single ring.

Graph build_graph_tree(size_t v_count, Random &random)

Construct a random tree graph (new vertices are repeatedly attached to a random position in a tree as it is constructed.)

Graph build_graph_random(size_t v_count, size_t e_count, Random &random, bool connected = true)

Construct a random, graph with the specified number of vertices and edges. If connected is set, start by building a tree. Then connect random (unconnected) pairs of vertices until the proper number of edges are included.

Graph build_graph_grid(size_t width, size_t height, Random &random, double prob_use = 1.0)

Construct a graph with width x height vertices setup into a grid structure.

Graph build_graph_clique_set(size_t clique_size, size_t clique_count, Random &random, double extra_prob = 0.5)

Build a set of cliques (such that one member of each can be part of an independent set) and then links them together

Graph build_graph_dag(size_t v_count, size_t e_count, Random &random, bool connected = true)

Construct a random, graph with the specified number of vertices and edges. If connected is set, start by building a tree. Then connect random (unconnected) pairs of vertices until the proper number of edges are included.

WeightedGraph build_weighted_graph_tree(size_t v_count, size_t min_weight, size_t max_weight, Random &random)

Construct a random WEIGHTED tree graph (new vertices are repeatedly attached to a random position in a tree as it is constructed.)

WeightedGraph build_weighted_graph_random(size_t v_count, size_t e_count, size_t min_weight, size_t max_weight, Random &random, bool connected = true)

Construct a random, WEIGHTED graph with the specified number of vertices, edges, and range of edge weights. If connected is set, start by building a tree. Then connect random (unconnected) pairs of vertices until the proper number of edges are included.

Graph load_graph_sym(std::istream &is, bool sub1 = false)

Helper function for loading symmetric graphs from an input stream. sub1 indicates that verticies are numbered 1 to N instead of 0 to N-1.

Graph load_graph_sym(std::string filename, bool sub1 = false)

Load a graph with a specified filename.

Graph load_graph_table(std::istream &is)

Load a graph from a connection matrix. Format: Number of vertices followed by v^2 0’s or 1’s Example: “3 0 1 0 1 0 0 0 0 1”

Graph load_graph_table(std::string filename)

Load a graph from a connection matrix in a file by the specified name.