Template Class ListGraph

Inheritance Relationships

Base Type

Class Documentation

template<class W = std::monostate, class T = std::monostate>
class ListGraph : public ADS::GraphNodes<std::monostate>

a graph with lists of adjacency

Public Types

using Weight = W

the type of the weights

using Label = T

the type of the labels

Public Functions

explicit ListGraph(int n = 0, bool directed = true)

Graph(): the graph of the nodes 0 , … , n - 1, with no edge.

Pre:

n >= 0

int insertNode(const T &t = T())

a new node, with no edge, and its name

void insertEdge(int u, int v, const W &w = W())

the edge ( u , v ), or [ u , v ], of weight w; only the weight changes if it is there

Pre:

u and v are distinct nodes

Post:

hasEdge( u , v )

void deleteEdge(int u, int v)

removes the edge ( u , v ), or [ u , v ], if it is there

Pre:

u and v are distinct nodes

Post:

! hasEdge( u , v )

void deleteNode(int u)

removes the node u and its edges, O( n + m ) time

Pre:

u is a node

Post:

! hasNode( u )

bool hasEdge(int u, int v) const
std::optional<W> weight(int u, int v) const

the weight of ( u , v ), nothing if there is no such edge

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

the set of the nodes adjacent to u, in the order of insertion

Pre:

u is a node

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

f( v ) on the nodes adjacent to u

Pre:

u is a node

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

f( v , w ) on the nodes adjacent to u and the weights of the edges

Pre:

u is a node

inline auto neighbors(int u) const

the nodes adjacent to u, in the order of its list, bidirectional

Pre:

u is a node