File MatrixGraph.h

↰ Parent directory (ADS/graph)

The GRAPH with an adjacency matrix of section 9.3 [see File Graph.h]: the weight of ( u , v ), or nothing, the infinity of the book, in place ( u , v ); Theta( n^2 ) space, hasEdge() in O( 1 ), adj( u ) in Theta( n ), insertNode() and deleteNode() in Theta( n ).

Definition (ADS/graph/MatrixGraph.h)

Detailed Description

The contracts [see File Contract.h]: insertEdge() and deleteEdge() need two distinct nodes, deleteNode(), adj(), forEachAdj() and forEachEdge() a node; the invariant is that the matrix is n x n with no entry on the diagonal nor in the rows and columns of the names not in use, m() entries in all, and symmetric for an unoriented graph. The operations check it on the rows and the columns they touch, in O( n ). The operations are defined in MatrixGraph.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 9.3, https://algoritmicamente.it/materiali/libro/capitoli/cap09.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes