converge_optimization/graph/
mod.rs

1//! Graph algorithms
2//!
3//! This module provides graph algorithms for optimization:
4//!
5//! - [`dijkstra`] - Shortest path algorithms
6//! - [`flow`] - Max flow and min cost flow
7//! - [`matching`] - Graph matching algorithms
8//!
9//! ## Graph Representation
10//!
11//! We use [`petgraph`] for the underlying graph structure, with
12//! wrapper types for optimization-specific operations.
13//!
14//! ## Example: Max Flow
15//!
16//! ```rust
17//! use converge_optimization::graph::flow::{FlowNetwork, max_flow};
18//!
19//! let mut net = FlowNetwork::new(4);
20//! net.add_edge_with_capacity(0, 1, 10);
21//! net.add_edge_with_capacity(0, 2, 10);
22//! net.add_edge_with_capacity(1, 3, 10);
23//! net.add_edge_with_capacity(2, 3, 10);
24//!
25//! let result = max_flow(&net, 0, 3).unwrap();
26//! assert_eq!(result.max_flow, 20);
27//! ```
28
29pub mod dijkstra;
30pub mod flow;
31pub mod matching;
32
33// Re-export main types
34pub use flow::{
35    FlowNetwork, MaxFlowResult, MinCostFlowProblem, MinCostFlowResult, max_flow, min_cost_flow,
36};
37
38use petgraph::graph::{DiGraph, EdgeIndex, NodeIndex};
39use serde::{Deserialize, Serialize};
40
41/// Node identifier
42pub type NodeId = NodeIndex;
43
44/// Edge identifier
45pub type EdgeId = EdgeIndex;
46
47/// A directed graph with node and edge weights
48pub type Graph<N, E> = DiGraph<N, E>;
49
50/// Edge with capacity and cost for flow problems
51#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
52pub struct FlowEdge {
53    /// Maximum flow capacity
54    pub capacity: i64,
55    /// Cost per unit flow
56    pub cost: i64,
57    /// Current flow (for solutions)
58    pub flow: i64,
59}
60
61impl FlowEdge {
62    /// Create a new flow edge
63    pub fn new(capacity: i64, cost: i64) -> Self {
64        Self {
65            capacity,
66            cost,
67            flow: 0,
68        }
69    }
70
71    /// Create an edge with only capacity (zero cost)
72    pub fn with_capacity(capacity: i64) -> Self {
73        Self::new(capacity, 0)
74    }
75
76    /// Remaining capacity
77    pub fn residual(&self) -> i64 {
78        self.capacity - self.flow
79    }
80}
81
82/// Path in a graph
83#[derive(Debug, Clone)]
84pub struct Path {
85    /// Nodes in the path (as indices)
86    pub nodes: Vec<NodeId>,
87    /// Total cost/distance of the path
88    pub cost: i64,
89}
90
91impl Path {
92    /// Create an empty path
93    pub fn empty() -> Self {
94        Self {
95            nodes: Vec::new(),
96            cost: 0,
97        }
98    }
99
100    /// Check if path is empty
101    pub fn is_empty(&self) -> bool {
102        self.nodes.is_empty()
103    }
104
105    /// Number of nodes in path
106    pub fn len(&self) -> usize {
107        self.nodes.len()
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn test_flow_edge() {
117        let mut edge = FlowEdge::new(10, 5);
118        assert_eq!(edge.residual(), 10);
119        edge.flow = 3;
120        assert_eq!(edge.residual(), 7);
121    }
122}
converge_optimization/graph/mod.rs

converge_optimization/graph/
mod.rs
