File graph.hpp

namespace graph

class graphcomponents

#include <graph.hpp>

Represents a graph as a series of connected components.

The input graph may consist of many components, they will be separated in the construction.

Public Functions

template <class rng_t>
graph::componentscomponents(const input_graph &g, rng_t &rng, const vector<int> &reserve)

const vector<int> &graph::componentsnodes(int c) const

Get the set of nodes in a component.

int graph::componentssize() const

Get the number of connected components in the graph.

int graph::componentsnum_reserved(int c) const

returns the number of reserved nodes in a component

int graph::componentssize(int c) const

Get the size (in nodes) of a component.

input_graph &graph::componentscomponent_graph(int c)

Get a mutable reference to the graph object of a component.

template <typename T>
bool graph::componentsinto_component(const int c, T &nodes_in, vector<int> &nodes_out) const

translate nodes from the input graph, to their labels in component c

template <typename T>
void graph::componentsfrom_component(const int c, T &nodes_in, vector<int> &nodes_out)

translate nodes from labels in component c, back to their original input labels

Private Functions

int graph::components__init_find(int x)

void graph::components__init_union(int x, int y)

Private Members

vector<int> graph::componentsindex

vector<int> graph::componentslabel

vector<int> graph::components_num_reserved

vector<vector<int>> graph::componentscomponent

vector<input_graph> graph::componentscomponent_g

class graphinput_graph

#include <graph.hpp>

Represents an undirected graph as a list of edges.

Provides methods to extract those edges into neighbor lists (with options to relabel and produce directed graphs).

As an input to the library this may be a disconnected graph, but when returned from components it is a connected sub graph.

Public Functions

graph::input_graphinput_graph()

Constructs an empty graph.

graph::input_graphinput_graph(int n_v, const vector<int> &aside, const vector<int> &bside)

Constructs a graph from the provided edges.

The ends of edge ii are aside[ii] and bside[ii].

Parameters

• n_v: Number of nodes in the graph.
• aside: List of nodes describing edges.
• bside: List of nodes describing edges.

void graph::input_graphclear()

Remove all edges and nodes from a graph.

int graph::input_grapha(const int i) const

Return the nodes on either end of edge i

int graph::input_graphb(const int i) const

Return the nodes on either end of edge i

int graph::input_graphnum_nodes() const

Return the size of the graph in nodes.

int graph::input_graphnum_edges() const

Return the size of the graph in edges.

void graph::input_graphpush_back(int ai, int bi)

Add an edge to the graph.

void graph::input_graphget_neighbors_sources(vector<vector<int>> &nbrs, const vector<int> &sources) const

produce the node->nodelist mapping for our graph, where certain nodes are marked as sources (no incoming edges)

void graph::input_graphget_neighbors_sinks(vector<vector<int>> &nbrs, const vector<int> &sinks) const

produce the node->nodelist mapping for our graph, where certain nodes are marked as sinks (no outgoing edges)

void graph::input_graphget_neighbors_sinks_relabel(vector<vector<int>> &nbrs, const vector<int> &sinks, const vector<int> &relabel) const

produce the node->nodelist mapping for our graph, where certain nodes are marked as sinks (no outgoing edges), relabeling all nodes along the way

void graph::input_graphget_neighbors_relabel(vector<vector<int>> &nbrs, const vector<int> &relabel) const

produce the node->nodelist mapping for our graph, relabeling all nodes along the way

void graph::input_graphget_neighbors(vector<vector<int>> &nbrs) const

produce the node->nodelist mapping for our graph

Private Functions

void graph::input_graph_to_vectorhoods(vector<set<int>> &_nbrs, vector<vector<int>> &nbrs) const

this method converts a vector of sets into a vector of sets, ensuring that element i is not contained in nbrs[i].

this method is called by methods which produce neighbor sets (killing parallel/overrepresented edges), in order to kill self-loops and also store each neighborhood in a contiguous memory segment.

Private Members

vector<int> graph::input_graphedges_aside

vector<int> graph::input_graphedges_bside

int graph::input_graph_num_nodes