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.