Class graph::input_graph

class graph::input_graph

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