API Reference

dmy_sssp!(graph::DMYGraph, source::Int) -> Vector{Float64}

Main entry point for the DMY shortest-path algorithm. Computes single-source shortest paths from the given source vertex.

Arguments

• graph: The directed graph with non-negative edge weights
• source: Source vertex index (1-based)

Returns

• Vector of shortest distances from source to all vertices

Algorithm Overview

The DMY algorithm uses recursive layering with frontier sparsification:

1. Initialize distance and parent arrays
2. Call recursive_layer! with full vertex set
3. Return computed distances

Time complexity: O(m log^(2/3) n) for sparse graphs Space complexity: O(n) for distance and parent arrays

dmy_sssp_with_parents!(graph::DMYGraph, source::Int) -> Tuple{Vector{Float64}, Vector{Int}}

DMY algorithm that returns both distances and parent pointers for path reconstruction.

Returns

• Tuple of (distances, parents) where parents[v] gives the predecessor of v in shortest path tree

dmy_sssp_bounded!(graph::DMYGraph, source::Int, max_distance::Float64) -> Vector{Float64}

DMY algorithm with distance bound - only computes paths up to max_distance. Can be more efficient when only short paths are needed.

Arguments

• graph: The directed graph
• source: Source vertex
• max_distance: Maximum distance to compute (paths longer than this are ignored)

Returns

• Distance array with INF for vertices beyond max_distance

DMYGraph

Efficient graph representation for the DMY algorithm using adjacency lists. Stores vertices, edges, and weights with validation for non-negative weights.

Edge

Represents a directed edge in the graph with source, target vertices and weight index.

Block

Represents a partitioned block of vertices for recursive processing.

recursive_layer!(graph::DMYGraph, dist::Vector{Float64}, parent::Vector{Int},
                U::Vector{Int}, S::OrderedSet{Int}, B::Float64) -> Nothing

Recursive layer processing function that implements the core DMY algorithm logic. Processes vertex subset U with current frontier S and upper bound B.

Arguments

• graph: The graph to process
• dist: Distance array (modified in-place)
• parent: Parent array for path reconstruction (modified in-place)
• U: Vertex subset to process
• S: Current frontier set
• B: Upper bound for distance updates

The function implements the recursive layering strategy with:

1. Base case handling for small vertex sets
2. Pivot threshold calculation k = ⌈|U|^(1/3)⌉
3. Frontier size checking and algorithm path selection
4. Pivot selection for frontier sparsification when needed
5. Vertex partitioning and recursive calls

bmssp!(graph::DMYGraph, dist::Vector{Float64}, parent::Vector{Int},
       frontier::AbstractSet{Int}, bound::Float64, k::Int) -> OrderedSet{Int}

Perform bounded multi-source shortest path relaxation for k rounds. Updates the distance and parent arrays in-place and returns the final frontier.

Arguments

• graph: The graph to process
• dist: Distance array (modified in-place)
• parent: Parent array for path reconstruction (modified in-place)
• frontier: Set of active vertices for relaxation
• bound: Upper bound for distance updates
• k: Maximum number of relaxation rounds

Returns

• Final frontier set after k rounds or early termination

bmssp_single_round!(graph::DMYGraph, dist::Vector{Float64}, parent::Vector{Int},
                    frontier::AbstractSet{Int}, bound::Float64) -> Tuple{OrderedSet{Int}, Bool}

Perform a single round of BMSSP relaxation. Returns the new frontier and whether any updates occurred.

select_pivots(U_tilde::Vector{Int}, S::AbstractSet{Int}, k::Int, dist::Vector{Float64}) -> Vector{Int}

Select pivot vertices from U_tilde to sparsify the frontier. Uses distance-based clustering to choose representative vertices.

Arguments

• U_tilde: Filtered vertex set (vertices not in S with finite distance < bound)
• S: Current frontier set
• k: Pivot threshold (typically ⌈|U|^(1/3)⌉)
• dist: Current distance array

Returns

• Vector of selected pivot vertices with |P| ≤ |U_tilde| / k

partition_blocks(U::Vector{Int}, dist::Vector{Float64}, t::Int, B::Float64=INF) -> Vector{Block}

Partition vertex set U into 2^t nearly equal blocks based on distance values. Each block gets a frontier seed and upper bound for recursive processing.

Arguments

• U: Vertex set to partition
• dist: Distance array
• t: Partition parameter (typically ⌈log^(1/3) n⌉)
• B: Overall bound for distances (default: INF)

Returns

• Vector of Block objects with vertices, frontier, and upper bound

partition_blocks_adaptive(U::Vector{Int}, dist::Vector{Float64}, t::Int, 
                         graph::DMYGraph, B::Float64=INF) -> Vector{Block}

Adaptive block partitioning that considers graph structure and distance distribution. Creates more balanced blocks based on both distance and connectivity.

validate_bmssp_input(graph::DMYGraph, dist::Vector{Float64}, parent::Vector{Int},
                    frontier::AbstractSet{Int}, bound::Float64, k::Int) -> Bool

Validate inputs for BMSSP function. Throws ArgumentError if invalid.

validate_dmy_input(graph::DMYGraph, source::Int) -> Bool

Validate inputs for DMY algorithm. Throws appropriate errors if invalid.

bmssp_with_statistics!(graph::DMYGraph, dist::Vector{Float64}, parent::Vector{Int},
                      frontier::AbstractSet{Int}, bound::Float64, k::Int) -> Dict{String, Any}

Perform BMSSP with detailed statistics collection. Returns statistics about the relaxation process.

dmy_algorithm_statistics(graph::DMYGraph, source::Int) -> Dict{String, Any}

Run DMY algorithm with detailed statistics collection. Useful for algorithm analysis and performance tuning.

count_relaxations(graph::DMYGraph, frontier::AbstractSet{Int}, bound::Float64, 
                 dist::Vector{Float64}) -> Int

Count the number of edge relaxations that would be performed in the next round. Useful for algorithm analysis and debugging.

Compute the full Pareto front for multi-objective shortest paths. Returns all non-dominated paths from source to target.

Find the "knee point" in the Pareto front - the solution with best trade-off. Uses the maximum distance from the utopia-nadir line.

Compute objective values for a path given parent array. Optionally accepts a vector of edge indices (per vertex) that identifies which multi-objective edge was used to reach each vertex.

Weighted sum approach: Combine objectives with weights. Simple but may miss some Pareto-optimal solutions.

Epsilon-constraint approach: Optimize one objective while constraining others. Good for finding specific trade-off solutions.

Lexicographic approach: Optimize objectives in priority order. Good when objectives have clear priority ranking.

A Pareto-optimal solution with multiple objective values

Multi-objective graph structure

Edge with multiple objective weights (e.g., distance, cost, risk, time)

OptimizationProblem(::Symbol, data, source)

Container for problem instances that can be transformed into a graph using the OptimShortestPaths casting helpers. data is the argument tuple that will be splatted into the corresponding constructor (e.g. create_drug_target_network).

Main OptimShortestPaths interface: optimize by casting to shortest path.

Cast an optimization problem to a graph representation. This is the core innovation of OptimShortestPaths: transforming optimization into shortest paths.

Transform optimization objectives into edge weights.

PharmaNetwork

Abstract base type for pharmaceutical network representations.

DrugTargetNetwork <: PharmaNetwork

Represents drug-target interaction networks for pharmaceutical applications.

MetabolicPathway <: PharmaNetwork

Represents metabolic pathway networks with metabolites and enzymatic reactions.

TreatmentProtocol <: PharmaNetwork

Represents treatment protocol networks with treatment steps and transition costs.

create_drug_target_network(drugs::Vector{String}, targets::Vector{String}, 
                          interactions::Matrix{Float64}) -> DrugTargetNetwork

Create a drug-target interaction network from drug names, target names, and interaction matrix. The interaction matrix contains binding affinities or interaction strengths.

Arguments

• drugs: Vector of drug names
• targets: Vector of target protein names
• interactions: Matrix where interactions[i,j] is the binding affinity between drug i and target j Use 0.0 for no interaction, positive values for binding affinities

Returns

• DrugTargetNetwork with underlying graph representation

Network Structure

• Vertices represent both drugs and targets
• Edges represent drug-target interactions
• Edge weights are -log(binding_affinity) to convert to distance metric

create_metabolic_pathway(metabolites::Vector{String}, reactions::Vector{String}, 
                       reaction_costs::Vector{Float64}, 
                       reaction_network::Vector{Tuple{String, String, String}}) -> MetabolicPathway

Create a metabolic pathway network from metabolites, reactions, and their connections.

Arguments

• metabolites: Vector of metabolite names
• reactions: Vector of reaction names
• reaction_costs: Vector of costs for each reaction (energy, time, etc.)
• reaction_network: Vector of (substrate, reaction, product) tuples defining the pathway

Returns

• MetabolicPathway with underlying graph representation

create_treatment_protocol(treatments::Vector{String}, costs::Vector{Float64}, 
                        efficacy_weights::Vector{Float64}, 
                        transitions::Vector{Tuple{String, String, Float64}}) -> TreatmentProtocol

Create a treatment protocol network for healthcare optimization.

Arguments

• treatments: Vector of treatment step names
• costs: Vector of costs for each treatment
• efficacy_weights: Vector of efficacy weights for each treatment
• transitions: Vector of (fromtreatment, totreatment, transition_cost) tuples

Returns

• TreatmentProtocol with underlying graph representation

find_drug_target_paths(network::DrugTargetNetwork, drug_name::String, 
                      target_name::String) -> Tuple{Float64, Vector{String}}

Find the shortest path from a drug to a target in the network. Returns the path distance and the sequence of drugs/targets in the path.

analyze_drug_connectivity(network::DrugTargetNetwork, drug_name::String) -> Dict{String, Any}

Analyze the connectivity of a specific drug in the network. Returns statistics about reachable targets and path lengths.

find_metabolic_pathway(pathway::MetabolicPathway, start_metabolite::String, 
                      end_metabolite::String) -> Tuple{Float64, Vector{String}}

Find the shortest metabolic pathway between two metabolites. Returns the total cost and sequence of metabolites in the pathway.

optimize_treatment_sequence(protocol::TreatmentProtocol, start_treatment::String, 
                           end_treatment::String) -> Tuple{Float64, Vector{String}}

Find the optimal treatment sequence from start to end treatment. Returns the total cost and sequence of treatments.

find_shortest_path(graph::DMYGraph, source::Int, target::Int)

Find the shortest path and distance between two vertices.

Returns

• Tuple of (distance, path) where path is vector of vertex indices

Example

distance, path = find_shortest_path(graph, start, goal)
if distance < INF
    println("Path found: ", join(path, " -> "))
end

reconstruct_path(parent::Vector{Int}, source::Int, target::Int) -> Vector{Int}

Reconstruct the shortest path from source to target using parent pointers. Returns empty vector if no path exists.

Arguments

• parent: Parent array from DMY algorithm
• source: Source vertex
• target: Target vertex

Returns

• Vector of vertices representing the path from source to target

shortest_path_tree(parent::Vector{Int}, source::Int) -> Dict{Int, Vector{Int}}

Construct the complete shortest path tree from the parent array. Returns a dictionary mapping each reachable vertex to its path from source.

path_length(path::Vector{Int}, graph::DMYGraph) -> Float64

Calculate the total length of a path in the graph. Returns INF if path is invalid or contains non-existent edges.

analyze_connectivity(graph::DMYGraph, source::Int)

Analyze connectivity metrics from a source vertex.

Returns

Dictionary containing:

• reachable_count: Number of reachable vertices
• unreachable_count: Number of unreachable vertices
• avg_distance: Average distance to reachable vertices
• max_distance: Maximum finite distance
• connectivity_ratio: Fraction of vertices that are reachable

Example

metrics = analyze_connectivity(graph, hub_vertex)
println("Hub connectivity: ", metrics["connectivity_ratio"] * 100, "%")

find_reachable_vertices(graph::DMYGraph, source::Int, max_distance::Float64 = INF)

Find all vertices reachable from source within a maximum distance.

Arguments

• graph: The graph to analyze
• source: Source vertex
• max_distance: Maximum distance threshold (default: INF for all reachable)

Returns

• Vector of vertex indices that are reachable within max_distance

Example

# Find all vertices within distance 10 from source
nearby = find_reachable_vertices(graph, source, 10.0)

graph_reachability(graph::DMYGraph, source::Int) -> Set{Int}

Find all vertices reachable from the source vertex. Uses simple BFS traversal.

is_connected(graph::DMYGraph, source::Int, target::Int) -> Bool

Check if there is a direct edge from source to target vertex.

calculate_distance_ratio(graph::DMYGraph, source::Int, target1::Int, target2::Int)

Calculate the ratio of distances from source to two different targets. This is a generic function useful for selectivity, preference, or comparison metrics.

Arguments

• graph: The graph to analyze
• source: Source vertex
• target1: First target vertex (numerator in ratio)
• target2: Second target vertex (denominator in ratio)

Returns

• Ratio of distance to target1 / distance to target2
• Returns 0.0 if either distance is 0 or unreachable
• Returns Inf if target2 is unreachable but target1 is reachable

Example

# For drug selectivity: higher ratio means more selective for target2
ratio = calculate_distance_ratio(graph, drug_vertex, cox1_vertex, cox2_vertex)

calculate_path_preference(graph::DMYGraph, source::Int, preferred::Int, alternative::Int)

Calculate preference score for reaching one target over another from a source. Higher values indicate stronger preference for the preferred target.

Arguments

• graph: The graph to analyze
• source: Source vertex
• preferred: Preferred target vertex
• alternative: Alternative target vertex

Returns

• Preference score (higher is better for preferred target)
• Uses inverse distance ratio so lower distance = higher preference

Example

# Check if pathway A is preferred over pathway B
preference = calculate_path_preference(graph, start, pathwayA, pathwayB)
if preference > 1.5
    println("Strong preference for pathway A")
end

compare_sources(graph::DMYGraph, sources::Vector{Int}, target::Int)

Compare distances from multiple sources to a single target.

Arguments

• graph: The graph to analyze
• sources: Vector of source vertices to compare
• target: Target vertex

Returns

Dictionary mapping source vertex to distance to target

Example

# Compare which warehouse is closest to customer
warehouses = [1, 2, 3]
customer = 10
distances = compare_sources(graph, warehouses, customer)
best_warehouse = argmin(distances)

vertex_count(graph::DMYGraph) -> Int

Return the number of vertices in the graph.

edge_count(graph::DMYGraph) -> Int

Return the number of edges in the graph.

out_degree(graph::DMYGraph, vertex::Int) -> Int

Return the out-degree of the specified vertex.

outgoing_edges(graph::DMYGraph, vertex::Int) -> Vector{Int}

Return the indices of all outgoing edges from the specified vertex.

graph_density(graph::DMYGraph) -> Float64

Calculate the density of the graph (ratio of actual edges to possible edges).

graph_statistics(graph::DMYGraph) -> Dict{String, Any}

Return comprehensive statistics about the graph structure.

has_self_loops(graph::DMYGraph) -> Bool

Check if the graph contains any self-loops (edges from a vertex to itself).

get_vertices_by_out_degree(graph::DMYGraph) -> Vector{Tuple{Int,Int}}

Return vertices sorted by their out-degree in descending order. Returns vector of (vertex, out_degree) tuples.

get_edge(graph::DMYGraph, edge_index::Int) -> Edge

Return the edge at the specified index.

get_edge_weight(graph::DMYGraph, edge_index::Int) -> Float64

Return the weight of the edge at the specified index.

get_edge_weight_between(graph::DMYGraph, source::Int, target::Int) -> Union{Float64, Nothing}

Get the weight of the edge from source to target, or return nothing if no edge exists. If multiple edges exist, returns the weight of the first one found.

find_edge(graph::DMYGraph, source::Int, target::Int) -> Union{Int, Nothing}

Find the index of the edge from source to target, or return nothing if not found. If multiple edges exist, returns the first one found.

iterate_edges(graph::DMYGraph, vertex::Int)

Iterator for outgoing edges from a vertex. Returns (edge, weight) pairs.

get_all_targets(graph::DMYGraph, source::Int) -> Vector{Int}

Get all target vertices reachable directly from the source vertex.

create_simple_graph(n_vertices::Int, edge_list::Vector{Tuple{Int,Int,Float64}}) -> DMYGraph

Create a DMYGraph from a simple edge list representation. Each tuple contains (source, target, weight).

validate_graph(graph::DMYGraph) -> Bool

Validate the structure and properties of a DMYGraph. Returns true if valid, throws ArgumentError if invalid.

validate_vertex(graph::DMYGraph, vertex::Int) -> Bool

Validate that a vertex index is within the valid range for the graph.

verify_shortest_path(graph::DMYGraph, dist::Vector{Float64}, source::Int, target::Int) -> Bool

Verify that the computed distance is indeed the shortest path length. Useful for debugging and validation.

format_distance_results(dist::Vector{Float64}, source::Int) -> String

Format distance results for human-readable output.

compare_with_dijkstra(graph::DMYGraph, source::Int) -> Dict{String, Any}

Compare DMY algorithm results with Dijkstra's algorithm for validation. Returns comparison statistics and identifies any discrepancies.

simple_dijkstra(graph::DMYGraph, source::Int) -> Vector{Float64}

Simple Dijkstra's algorithm implementation for comparison and validation. Not optimized for performance - used only for correctness checking.

calculate_pivot_threshold(U_size::Int) -> Int

Calculate the pivot threshold k = ⌈|U|^(1/3)⌉ for a given vertex set size. This is the theoretical optimum from the DMY paper.

calculate_partition_parameter(n::Int) -> Int

Calculate the partition parameter t = ⌈log^(1/3) n⌉ for a given graph size. This determines the number of blocks (2^t) in recursive partitioning.

pivot_selection_statistics(U_tilde::Vector{Int}, S::AbstractSet{Int}, k::Int,
                          pivots::Vector{Int}, dist::Vector{Float64}) -> Dict{String, Any}

Collect statistics about the pivot selection process.

validate_pivot_selection(pivots::Vector{Int}, U_tilde::Vector{Int}, k::Int) -> Bool

Validate that pivot selection satisfies the algorithm constraints. Checks that |P| ≤ |Utilde| / k and all pivots are from Utilde.