File Graph.h

↰ Parent directory (ADS/graph)

The GRAPH of chapter 9 and its realizations.

Definition (ADS/graph/Graph.h)

Detailed Description

A graph G = ( V , E ) has n nodes, named by integers, and m edges, ordered pairs ( u , v ) if it is oriented and unordered pairs [ u , v ] otherwise; an unoriented graph is the oriented one with both ( u , v ) and ( v , u ) (section 9.2), and so adj( u ) gives v for each edge [ u , v ]. The edges may have a weight of type W and the nodes a label of type T, both std::monostate if absent; there are no loops ( u , u ), so :math:` 0 leq m leq n ( n - 1 ) `.

The nodes of a graph are the integers in [ 0 , bound() ): insertNode() gives the next one and deleteNode() leaves its name unused, so that the vectors indexed by the nodes of the visits have bound() places, and n() = |V()| is the G.n of the book. The concept Graph asks for V(), adj( u ), which gives the adjacent nodes in a vector, as the SET of the book, and forEachAdj( u , f ), which calls f on them without building it.

incidence() gives the n x m matrix B of incidence nodes-edges (section 9.3): :math:` b_{uk} = -1 ` if the edge k leaves u and +1 if it enters it, for an oriented graph, and 1 if the edge k touches u, for an unoriented one.

adjFromIncidence() reads the adjacent nodes of u back from the matrix: in the row u, each column k of an edge leaving u (or touching it, if the graph is unoriented) leads to the other row with a nonzero entry.

The contracts [see File Contract.h]: a graph has n >= 0 nodes, the operations on a node need one of the graph, and an edge needs two distinct nodes of the graph (no loops); the invariant of the nodes is that n() counts the names in use. The realizations relax some preconditions of the specification, which asks for an edge not there in insertEdge(), for one there in deleteEdge() and for an isolated node in deleteNode(): instead, insertEdge() of an edge already there replaces its weight, deleteEdge() of one not there does nothing, and deleteNode() also deletes the edges of the node (PointerGraph [see File PointerGraph.h] keeps the strict deleteNode()). The operations are defined in Graph.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 9.1-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

Functions