API Reference

OptimShortestPaths.jl - Optimization via Shortest Paths

A unified framework for solving multi-objective optimization problems by transforming them into graph shortest-path problems. OptimShortestPaths leverages the efficient DMY (Duan-Mao-Yin) algorithm while extending it with Pareto optimization and domain-specific applications.

Key Innovation: OptimShortestPaths casts complex optimization problems as shortest-path problems, enabling efficient solution of pharmaceutical, metabolic, and healthcare optimization challenges.

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

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

Advanced pivot selection that considers graph structure in addition to distances. Uses a combination of distance-based clustering and vertex degree information.

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 using a geometric trade-off heuristic.

For two objectives, this uses the point with maximum perpendicular distance from the chord joining the extreme Pareto solutions after objective normalization. For higher dimensions, it falls back to the distance from the normalized utopia-nadir diagonal. Pass objective_sense when the front mixes minimization and maximization.

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.

Check if solution a dominates solution b (all objectives <= and at least one <)

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.

analyze_treatment_accessibility(protocol::TreatmentProtocol, treatment_name::String) -> Dict{String, Any}

Analyze reachability and cost statistics starting from a treatment step. Returns summary metrics over all treatment vertices reachable from the named step.

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.