Graph

Definition

Lightweight directed graph implementation for cycle detection in macro expansion This module provides a compact, allocation-efficient directed graph (digraph) specifically designed for detecting circular dependencies during macro expansion in the fpx preprocessor.

Features:

• Fixed-size adjacency list using a dense 2D integer array (fast access, no pointers)
• Dynamic edge insertion with automatic per-vertex size tracking
• Depth-first search (DFS) based) cycle detection starting from any vertex
• Automatic cleanup via finalizer
• No dynamic memory fragmentation – ideal for frequent creation/destruction during preprocessing

Used internally by fpx_macro to prevent infinite recursion when a macro expands (directly or indirectly) to itself (e.g., #define A B, #define B A).

Examples

1. Detect circular macro dependency:

   type(digraph) :: g
   logical       :: cycle
    
   g = digraph(3)            ! 3 macros indexed 1..3
   call g%add_edge(1, 2)     ! macro1 depends on macro2
   call g%add_edge(2, 3)     ! macro2 depends on macro3
   call g%add_edge(3, 1)     ! macro3 depends on macro1 → cycle!
    
   cycle = g%is_circular(1)  ! returns .true.
   print *, 'Circular macro chain detected:', cycle
   ...

2. Safe expansion (used inside fpx_macro):

   type(digraph) :: expansion_graph
   expansion_graph = digraph(size(macros))
   call expansion_graph%add_edge(current_macro_idx, referenced_macro_idx)
   if (expansion_graph%is_circular(referenced_macro_idx)) then
      ! Skip expansion to prevent infinite loop
   end if
   ...

Data Types
interface	digraph
	Directed graph with fixed vertex count and efficient cycle detection Stores edges in a dense adjacency matrix slice per vertex. Only the actually used portion of each row is tracked via list_sizes. More...

Methods

dfs_recursive()

recursive logical function dfs_recursive ( class(digraph), intent(in) this, integer, intent(in) vertex, logical, dimension(:), intent(inout) visited, logical, dimension(:), intent(inout) recursion_stack )

private

Internal recursive DFS worker for cycle detection.

Definition at line 168 of file graph.f90.