Namespace graph¶

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

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

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(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

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