Template Class StaticGraph

• Defined in File StaticGraph.h

Class Documentation

template<class W = std::monostate>
class StaticGraph

a static graph in compressed sparse rows, the arcs of each node sorted by head, each next to its weight

Public Types

using Weight = W

the type of the weights

using Arc = std::conditional_t<weighted, WeightedArc<W>, int>

an arc: its head, and its weight if the graph is weighted

Public Functions

inline StaticGraph(void)

the graph with no node

StaticGraph(int n, const std::vector<std::tuple<int, int, W>> &E, bool directed = true)

the graph of the nodes 0 , … , n - 1 and of the given edges; an unoriented edge [ u , v ] is given once

Pre:

n >= 0, each edge joins two distinct nodes, fewer than 2^31 arcs

StaticGraph(int n, const std::vector<std::pair<int, int>> &E, bool directed = true)

the unweighted graph of the nodes 0 , … , n - 1 and of the edges E

Pre:

n >= 0, each edge joins two distinct nodes, fewer than 2^31 arcs

template<Graph G>
explicit StaticGraph(const G &g)

the copy of any graph, the names that are not nodes of g becoming isolated nodes

inline bool directed(void) const

inline int n(void) const

inline int m(void) const

the number of edges, an unoriented one counted once

inline int arcs(void) const

the number of arcs, 2 m() if the graph is unoriented

inline int bound(void) const

inline bool hasNode(int u) const

int degree(int u) const

Pre:

u is a node

std::vector<int> V(void) const

std::vector<int> adj(int u) const

Pre:

u is a node

template<class F>
void forEachAdj(int u, F &&f) const

Pre:

u is a node

template<class F>
void forEachEdge(int u, F &&f) const

f( v , w ) on each arc ( u , v ) of weight w

Pre:

u is a node

std::span<const Arc> out(int u) const

the arcs out of u, contiguous

Pre:

u is a node

inline const int *offsets(void) const

the offsets of the rows: the arcs of u are those in the places [ offsets()[ u ] , offsets()[ u + 1 ] ) of arcData()

inline const Arc *arcData(void) const

all the arcs, row by row

StaticGraph transpose(void) const

the graph with each arc reversed (the same graph if unoriented)

StaticGraph relabel(const std::vector<int> &p) const

the same graph with the node u renamed p[ u ]

Pre:

p is a permutation of the nodes

inline auto nodes(void) const

the nodes, 0 , … , n - 1, random access

Public Static Functions

static inline int head(const Arc &a)

the head of an arc

Public Static Attributes

static constexpr bool weighted = !std::is_same_v<W, std::monostate>

whether the arcs have a weight