pic_graph Module

Shortest-path and traversal algorithms on a weighted directed graph stored as a csr_t from pic_csr.

A graph on n vertices is a square n by n csr_t: row u holds one entry per outgoing edge of u, the column index is the head vertex and the value is the edge weight. Vertices are numbered 1:n. An undirected graph is the symmetric case, stored with both directions.

### Reproducibility guarantee

This is the property that makes the module worth having. pic_heap guarantees that entries with equal keys pop in FIFO order, so equal-distance vertices settle in a deterministic order rather than in whatever order a heap happens to rebalance into. On top of that, dijkstra relaxes each vertex’s outgoing edges in ascending column order (CSR rows are sorted), and accepts a relaxation only on a strict improvement. Together those make the entire output a pure function of the input: not only dist, which is forced by the mathematics, but also prev and therefore the reconstructed path when several shortest paths tie. The same graph gives the same tie-broken path on every compiler and every run. test_pic_graph pins this with a graph that has two equal-cost shortest paths and asserts which one wins.

Concretely, when two shortest paths to a vertex tie, the predecessor that is discovered first in settle order wins, and settle order among equal distances is the order in which those vertices were pushed.

### Sentinels

  • GRAPH_INFINITY (huge(1.0_dp)) is the distance of a vertex not reachable from the source.
  • GRAPH_NO_PREDECESSOR (0) is the prev entry of the source and of every unreachable vertex; 0 is not a valid vertex index.
  • GRAPH_UNREACHABLE (-1) is the bfs hop count of an unreachable vertex.

### Negative weights are rejected

Dijkstra and A* are simply invalid on negative edge weights. Rather than quietly returning wrong distances, dijkstra, a_star and path_cost report ERROR_VALIDATION when any stored weight is negative. Use a Bellman-Ford style algorithm for graphs with negative edges.

### The priority queue and its key

heap_t is keyed by integer(int64) while distances here are real(dp), so distances are mapped to keys by distance_key, an order-preserving and injective encoding of non-negative doubles into integer(int64) (see its own documentation). Because it is injective, two vertices tie in the heap exactly when their distances are equal as reals, which is what makes the FIFO tie-break above meaningful.

The queue is used with the lazy deletion pattern: an improved distance is pushed as a new entry rather than decreasing an existing key, and stale pops are skipped by testing whether the vertex has already settled. heap_t deliberately offers no decrease_key, and this is its intended usage.

### Usage

 type(csr_t) :: g
 type(error_t) :: err
 real(dp), allocatable :: dist(:)
 integer(default_int), allocatable :: prev(:)

 call dijkstra(g, 1_default_int, dist, prev, err)

Uses

  • module~~pic_graph~~UsesGraph module~pic_graph pic_graph module~pic_csr pic_csr module~pic_graph->module~pic_csr module~pic_error pic_error module~pic_graph->module~pic_error module~pic_heap pic_heap module~pic_graph->module~pic_heap module~pic_types pic_types module~pic_graph->module~pic_types module~pic_csr->module~pic_error module~pic_csr->module~pic_types module~pic_error->module~pic_types module~pic_global_definitions pic_global_definitions module~pic_error->module~pic_global_definitions module~pic_heap->module~pic_error module~pic_heap->module~pic_types iso_c_binding iso_c_binding module~pic_types->iso_c_binding iso_fortran_env iso_fortran_env module~pic_types->iso_fortran_env module~pic_global_definitions->module~pic_types

Variables

Type Visibility Attributes Name Initial
real(kind=dp), public, parameter :: GRAPH_INFINITY = huge(1.0_dp)

Distance reported for a vertex unreachable from the source
integer(kind=default_int), public, parameter :: GRAPH_NO_PREDECESSOR = 0

prev entry meaning “no predecessor”; 0 is never a valid vertex
integer(kind=default_int), public, parameter :: GRAPH_UNREACHABLE = -1

bfs hop count of a vertex unreachable from the source
integer(kind=int64), private, parameter :: EXPONENT_BIAS = int(maxexponent(1.0_dp), int64)-2_int64

Bias turning exponent(x) into the stored exponent field, 1022 for binary64
integer(kind=default_int), private, parameter :: MANTISSA_BITS = digits(1.0_dp)-1

Explicit-mantissa bit count of real(dp), 52 for IEEE binary64
integer(kind=int64), private, parameter :: MANTISSA_SCALE = 2_int64**MANTISSA_BITS

2**MANTISSA_BITS, the weight of one unit in the exponent field

Functions

private function check_graph(graph, source, err) result(ok)

Validate the structural preconditions shared by every algorithm here.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Adjacency matrix to check
integer(kind=default_int), intent(in) :: source

Vertex index that must lie in 1:n
type(error_t), intent(out), optional :: err

Return Value logical

.true. when the graph and vertex are usable

private function check_weights(graph, err) result(ok)

Reject negative edge weights, on which Dijkstra and A* are invalid.

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Adjacency matrix whose stored values are the edge weights
type(error_t), intent(out), optional :: err

Return Value logical

.true. when every stored weight is non-negative

private pure function distance_key(x) result(key)

Map a non-negative real(dp) onto an integer(int64) heap key, preserving order exactly.

Read more…

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(in) :: x

Distance to encode; must be non-negative and finite

Return Value integer(kind=int64)

Order-preserving encoding of x


Subroutines

public subroutine a_star(graph, source, target, heuristic, path, err)

A* search for one shortest path from source to target.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square weighted adjacency matrix of the graph
integer(kind=default_int), intent(in) :: source

Start vertex, in 1:n
integer(kind=default_int), intent(in) :: target

Goal vertex, in 1:n
real(kind=dp), intent(in) :: heuristic(:)

Admissible lower bound on the distance from each vertex to target
integer(kind=default_int), intent(out), allocatable :: path(:)

Vertices from source to target, or zero-size if unreachable
type(error_t), intent(out), optional :: err

public subroutine bfs(graph, source, level, prev, err)

Breadth-first search, ignoring edge weights.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square adjacency matrix of the graph; values are ignored
integer(kind=default_int), intent(in) :: source

Source vertex, in 1:n
integer(kind=default_int), intent(out), allocatable :: level(:)

Hop count to each vertex
integer(kind=default_int), intent(out), allocatable :: prev(:)

Predecessor of each vertex on its shortest hop path
type(error_t), intent(out), optional :: err

public subroutine connected_components(graph, component, n_components, err)

Label the weakly connected components of the graph.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square adjacency matrix of the graph; values are ignored
integer(kind=default_int), intent(out), allocatable :: component(:)

Component label of each vertex
integer(kind=default_int), intent(out) :: n_components

Number of weakly connected components found
type(error_t), intent(out), optional :: err

public subroutine dijkstra(graph, source, dist, prev, err)

Single-source shortest paths with non-negative edge weights.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square weighted adjacency matrix of the graph
integer(kind=default_int), intent(in) :: source

Source vertex, in 1:n
real(kind=dp), intent(out), allocatable :: dist(:)

Shortest distance to each vertex
integer(kind=default_int), intent(out), allocatable :: prev(:)

Predecessor of each vertex on its shortest path
type(error_t), intent(out), optional :: err

public subroutine path_cost(graph, path, cost, err)

Total weight of walking path through graph.

Read more…

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square weighted adjacency matrix of the graph
integer(kind=default_int), intent(in) :: path(:)

Vertices to walk, in order
real(kind=dp), intent(out) :: cost

Sum of the weights of the traversed edges
type(error_t), intent(out), optional :: err

private pure subroutine enqueue_neighbours(adjacency, u, label, component, queue, tail)

Label and enqueue every still-unlabelled neighbour of u.

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: adjacency

Adjacency to read row u from
integer(kind=default_int), intent(in) :: u

Vertex whose neighbours are being visited
integer(kind=default_int), intent(in) :: label

Component label to assign
integer(kind=default_int), intent(inout) :: component(:)

Component labels, 0 where still unlabelled
integer(kind=default_int), intent(inout) :: queue(:)

Visit queue
integer(kind=default_int), intent(inout) :: tail

Index of the last used slot of queue

private pure subroutine fail(err, message)

Set err to ERROR_VALIDATION with message, when err is present.

Arguments

Type IntentOptional Attributes Name
type(error_t), intent(out), optional :: err
character(len=*), intent(in) :: message

Human-readable description of the violation

private pure subroutine trace_back(prev, source, target, path)

Walk prev from target back to source and return it forwards.

Arguments

Type IntentOptional Attributes Name
integer(kind=default_int), intent(in) :: prev(:)

Predecessor array, with GRAPH_NO_PREDECESSOR at the source
integer(kind=default_int), intent(in) :: source

First vertex of the path
integer(kind=default_int), intent(in) :: target

Last vertex of the path
integer(kind=default_int), intent(out), allocatable :: path(:)

source first, target last