monist_core/
eval.rs

1use crate::graph::{Edge, GraphArena, ScopedVar};
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4pub enum EvalResult {
5    Success(Vec<(ScopedVar, i32)>),
6    NegativeCycle,
7}
8
9pub fn evaluate_clause(edges: &[Edge]) -> EvalResult {
10    let mut vertices = Vec::new();
11    for edge in edges {
12        if !vertices.contains(&edge.source) {
13            vertices.push(edge.source.clone());
14        }
15        if !vertices.contains(&edge.target) {
16            vertices.push(edge.target.clone());
17        }
18    }
19
20    let v_count = vertices.len();
21    if v_count == 0 {
22        return EvalResult::Success(Vec::new());
23    }
24
25    let mut dist = vec![0; v_count];
26    let get_idx = |v: &ScopedVar| vertices.iter().position(|x| x == v).unwrap();
27
28    let indexed_edges: Vec<(usize, usize, i32)> = edges
29        .iter()
30        .map(|e| (get_idx(&e.source), get_idx(&e.target), e.weight))
31        .collect();
32
33    for _ in 0..(v_count - 1) {
34        let mut updated = false;
35        for &(u, v, weight) in &indexed_edges {
36            if dist[u] + weight < dist[v] {
37                dist[v] = dist[u] + weight;
38                updated = true;
39            }
40        }
41        if !updated {
42            break;
43        }
44    }
45
46    for &(u, v, weight) in &indexed_edges {
47        if dist[u] + weight < dist[v] {
48            return EvalResult::NegativeCycle;
49        }
50    }
51
52    let final_dist = vertices.into_iter().zip(dist.into_iter()).collect();
53    EvalResult::Success(final_dist)
54}
55
56#[derive(Debug, Clone)]
57pub struct ExecutionLimits {
58    pub max_k_iterations: usize,
59    pub mcm: f64,
60}
61
62impl ExecutionLimits {
63    pub fn compute_for_graph(graph: &GraphArena) -> Option<Self> {
64        let n = graph.vars.len();
65        if n == 0 {
66            return None;
67        }
68
69        // Karp's Minimum Cycle Mean (MCM) Algorithm
70        // DP array: dp[k][v] = min weight of path of length k to v
71        let mut dp = vec![vec![i32::MAX / 2; n]; n + 1];
72        for v in 0..n {
73            dp[0][v] = 0;
74        }
75
76        for k in 1..=n {
77            for &(u, v, w, _) in &graph.edges {
78                if dp[k - 1][u] + w < dp[k][v] {
79                    dp[k][v] = dp[k - 1][u] + w;
80                }
81            }
82        }
83
84        let mut mcm: f64 = f64::INFINITY;
85        let mut has_cycle = false;
86
87        for v in 0..n {
88            if dp[n][v] >= i32::MAX / 4 {
89                continue;
90            }
91            let mut min_val: f64 = f64::NEG_INFINITY;
92            for k in 0..n {
93                if dp[k][v] >= i32::MAX / 4 {
94                    continue;
95                }
96                let val = (dp[n][v] - dp[k][v]) as f64 / (n - k) as f64;
97                if val > min_val {
98                    min_val = val;
99                }
100            }
101            if min_val < mcm {
102                mcm = min_val;
103                has_cycle = true;
104            }
105        }
106
107        if !has_cycle {
108            mcm = 0.0;
109        }
110
111        // K-Iteration based on Pigeonhole Principle
112        let max_iterations = if mcm < 0.0 {
113            // Negative cycle indicates Extensionality Collision, halt early.
114            0
115        } else {
116            // Safe geometric limits
117            n * 2
118        };
119
120        Some(ExecutionLimits {
121            max_k_iterations: max_iterations,
122            mcm,
123        })
124    }
125}
monist_core/eval.rs

monist_core/
eval.rs
