File graph.hpp

template<>
class graph::unaryint<std::vector<int>>
#include <graph.hpp>

Public Functions

inline unaryint(const std::vector<int> m)
inline int operator()(int i) const

Private Members

const std::vector<int> b
namespace graph
class components
#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<typename T>
inline components(const input_graph &g, const unaryint<T> &reserve)
inline components(const input_graph &g)
inline components(const input_graph &g, const std::vector<int> reserve)
inline const std::vector<int> &nodes(int c) const

Get the set of nodes in a component.

inline size_t size() const

Get the number of connected components in the graph.

inline size_t num_reserved(int c) const

returns the number of reserved nodes in a component

inline size_t size(int c) const

Get the size (in nodes) of a component.

inline const input_graph &component_graph(int c) const

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

inline std::vector<std::vector<int>> component_neighbors(int c) const

Construct a neighborhood list for component c, with reserved nodes as sources.

template<typename T>
inline bool into_component(const int c, T &nodes_in, std::vector<int> &nodes_out) const

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

template<typename T>
inline void from_component(const int c, T &nodes_in, std::vector<int> &nodes_out) const

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

Private Functions

inline int __init_find(int x)
inline void __init_union(int x, int y)

Private Members

std::vector<int> index
std::vector<int> label
std::vector<int> _num_reserved
std::vector<std::vector<int>> component
std::vector<input_graph> component_g
class input_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

inline input_graph()

Constructs an empty graph.

inline input_graph(int n_v, const std::vector<int> &aside, const std::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.

inline void clear()

Remove all edges and nodes from a graph.

inline int a(const int i) const

Return the nodes on either end of edge i

inline int b(const int i) const

Return the nodes on either end of edge i

inline size_t num_nodes() const

Return the size of the graph in nodes.

inline size_t num_edges() const

Return the size of the graph in edges.

inline void push_back(int ai, int bi)

Add an edge to the graph.

template<typename T1, typename ...Args>
inline std::vector<std::vector<int>> get_neighbors_sources(const T1 &sources, Args... args) const

produce a std::vector<std::vector<int>> of neigborhoods, with certain nodes marked as sources (inbound edges are omitted) sources is either a std::vector<int> (where non-sources x have sources[x] = 0), or another type for which we have a unaryint specialization optional arguments: relabel, mask (any type with a unaryint specialization) relabel is applied to the nodes as they are placed into the neighborhood list (and not used for checking sources / mask) mask is used to filter down to the induced graph on nodes x with mask[x] = 1

template<typename T2, typename ...Args>
inline std::vector<std::vector<int>> get_neighbors_sinks(const T2 &sinks, Args... args) const

produce a std::vector<std::vector<int>> of neigborhoods, with certain nodes marked as sinks (outbound edges are omitted) sinks is either a std::vector<int> (where non-sinks x have sinks[x] = 0), or another type for which we have a unaryint specialization optional arguments: relabel, mask (any type with a unaryint specialization) relabel is applied to the nodes as they are placed into the neighborhood list (and not used for checking sinks / mask) mask is used to filter down to the induced graph on nodes x with mask[x] = 1

template<typename ...Args>
inline std::vector<std::vector<int>> get_neighbors(Args... args) const

produce a std::vector<std::vector<int>> of neigborhoods optional arguments: relabel, mask (any type with a unaryint specialization) relabel is applied to the nodes as they are placed into the neighborhood list (and not used for checking mask) mask is used to filter down to the induced graph on nodes x with mask[x] = 1

Private Functions

inline std::vector<std::vector<int>> _to_vectorhoods(std::vector<std::set<int>> &_nbrs) const

this method converts a std::vector of sets into a std::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.

template<typename T1, typename T2, typename T3, typename T4>
inline std::vector<std::vector<int>> __get_neighbors(const unaryint<T1> &sources, const unaryint<T2> &sinks, const unaryint<T3> &relabel, const unaryint<T4> &mask) const

produce the node->nodelist mapping for our graph, where certain nodes are marked as sources (no incoming edges), relabeling all nodes along the way, and filtering according to a mask.

note that the mask itself is assumed to be a union of components only one side of each edge is checked

template<typename T1, typename T2, typename T3 = void*, typename T4 = bool>
inline std::vector<std::vector<int>> _get_neighbors(const T1 &sources, const T2 &sinks, const T3 &relabel = nullptr, const T4 &mask = true) const

smash the types through unaryint

Private Members

std::vector<int> edges_aside
std::vector<int> edges_bside
size_t _num_nodes
template<typename T>
class unaryint
#include <graph.hpp>
template<>
class unaryint<bool>
#include <graph.hpp>

Public Functions

inline unaryint(const bool x)
inline int operator()(int) const

Private Members

const bool b
template<>
class unaryint<int>
#include <graph.hpp>

Public Functions

inline unaryint(int m)
inline int operator()(int i) const

Private Members

const int b
template<> vector< int > >
#include <graph.hpp>

Public Functions

inline unaryint(const std::vector<int> m)
inline int operator()(int i) const

Private Members

const std::vector<int> b
template<>
class unaryint<void*>
#include <graph.hpp>

this one is a little weird construct a unaryint(nullptr) and get back the identity function f(x) -> x

Public Functions

inline unaryint(void*const&)
inline int operator()(int i) const