Directed graph utilities used for macro dependency analysis.
This module provides a lightweight directed graph implementation used internally by the fpx preprocessor to detect cyclic dependencies during macro expansion.
Unlike general-purpose graph libraries, this implementation is optimized for the small graphs typically encountered during preprocessing:
- Vertices are represented by 1-based integer identifiers.
- Edges are stored in a dense adjacency structure for fast traversal.
- Cycle detection uses depth-first search (DFS) with a recursion stack.
- Invalid vertices are ignored gracefully.
- Memory management is automatic through a finalizer.
The primary use case is preventing infinite recursion caused by macros expanding, directly or indirectly, to themselves:
#define A B
#define B C
#define C A
Before expanding a macro, fpx records dependencies in a graph and checks whether introducing a new dependency would create a cycle.
Examples
- Detecting a circular dependency:
type(digraph) :: g
logical :: cycle
g = digraph(3)
call g%add_edge(1, 2)
call g%add_edge(2, 3)
call g%add_edge(3, 1)
cycle = g%is_circular(1)
print *, cycle
- Detecting an acyclic dependency chain:
type(digraph) :: g
g = digraph(4)
call g%add_edge(1, 2)
call g%add_edge(2, 3)
call g%add_edge(3, 4)
print *, g%is_circular(1)
- Internal usage during macro expansion:
call graph%add_edge(current_macro, referenced_macro)
if (graph%is_circular(referenced_macro)) then
end if