File ListGraph.h

↰ Parent directory (ADS/graph)

The GRAPH with lists of adjacency of section 9.4 [see File Graph.h]: for each node the LIST of its adjacent nodes and of the weights of the edges, Theta( n + m ) space, adj( u ) in Theta( |adj( u )| ), hasEdge( u , v ) in O( |adj( u )| ), all the edges in Theta( n + m ), deleteNode() in O( n + m ).

Definition (ADS/graph/ListGraph.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 lists hold only nodes of the graph, without loops nor repetitions, m() edges in all, and that an unoriented edge is in the lists of both its ends with the same weight. The insertions and the deletions of edges check it on the lists of the two ends, in O( d log d ) for d adjacent nodes, deleteNode() on the whole graph. The operations are defined in ListGraph.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes