File PointerGraph.h

↰ Parent directory (ADS/graph)

An oriented graph with pointers, beyond the book: each node is an object with its label, a flag for the visits, the number of edges that touch it and the list of its edges, each a pointer to the other end and a weight.

Definition (ADS/graph/PointerGraph.h)

Detailed Description

A node is reached by its address, which stays valid until it is deleted, and found by label in O( n ). deleteNode() deletes only an isolated node, forceDeleteNode() first deletes the edges that enter or leave it, in O( n + m ); dfs() and bfs() mark the nodes with the flags, cleared at the start of each visit. The graphs of chapter 9 number their nodes from 0 [see File ListGraph.h]; this one has neither numbers nor a bound.

The contracts [see File Contract.h]: the operations need nodes of this graph, not nil (whether a node belongs to the graph costs O( n ), and is checked at the level of the audits); the invariant is that the degree of each node counts the edges that leave it and those that enter it, and that the edges lead to nodes of the graph. The operations are defined in PointerGraph.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes