Template Class MatrixGraph

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

Class Documentation

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

a graph with an adjacency matrix

Public Types

using Weight = W

the type of the weights

using Label = T

the type of the labels

Public Functions

explicit MatrixGraph(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, a new row and a new column, O( n ) time

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

u and v are distinct nodes

Post:

hasEdge( u , v )

void deleteEdge(int u, int v)
Pre:

u and v are distinct nodes

Post:

! hasEdge( u , v )

void deleteNode(int u)

removes the node u and its edges, Theta( n ) time

Pre:

u is a node

Post:

! hasNode( u )

bool hasEdge(int u, int v) const

O( 1 ) time.

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

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

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

the set of the nodes adjacent to u, in increasing order, Theta( n ) time

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
Pre:

u is a node

inline auto neighbors(int u) const

the nodes adjacent to u in increasing order, bidirectional

Pre:

u is a node

struct Present

the columns of the edges in a row, for SlotIterator

Public Static Functions

static inline std::size_t size(const auto &r)
static inline bool occupied(const auto &r, std::size_t i)
static inline int read(const auto&, std::size_t i)