File graph.hpp¶
-
template<>
classgraph
::
unaryint
<std::vector<int>> - #include <graph.hpp>
Private Members
-
const std::vector<int>
b
¶
-
const std::vector<int>
-
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
>components
(const input_graph &g, const unaryint<T> &reserve)¶
-
components
(const input_graph &g)¶
-
components
(const input_graph &g, const std::vector<int> reserve)¶
-
const std::vector<int> &
nodes
(int c) const Get the set of nodes in a component.
-
size_t
size
() const Get the number of connected components in the graph.
-
size_t
num_reserved
(int c) const returns the number of reserved nodes in a component
-
size_t
size
(int c) const Get the size (in nodes) of a component.
-
const input_graph &
component_graph
(int c) const Get a const reference to the graph object of a component.
-
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
>
boolinto_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
>
voidfrom_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
-
template<typename
-
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
-
input_graph
() Constructs an empty graph.
-
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.
-
void
clear
() Remove all edges and nodes from a graph.
-
int
a
(const int i) const Return the nodes on either end of edge
i
-
int
b
(const int i) const Return the nodes on either end of edge
i
-
size_t
num_nodes
() const Return the size of the graph in nodes.
-
size_t
num_edges
() const Return the size of the graph in edges.
-
void
push_back
(int ai, int bi) Add an edge to the graph.
-
template<typename
T1
, typename ...Args
>
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
>
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
>
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
-
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
, typenameT2
, typenameT3
, typenameT4
>
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
T
>
classunaryint
- #include <graph.hpp>
-
template<>
classunaryint
<bool> - #include <graph.hpp>
Private Members
-
const bool
b
¶
-
const bool
-
template<>
classunaryint
<int> - #include <graph.hpp>
Private Members
-
const int
b
¶
-
const int
-
template<> vector< int > >
- #include <graph.hpp>
Private Members
-
const std::vector<int>
b
¶
-
const std::vector<int>
-
template<>
classunaryint
<void*> - #include <graph.hpp>
this one is a little weird construct a unaryint(nullptr) and get back the identity function f(x) -> x
-
class