problemreductions/models/graph/
minimum_feedback_arc_set.rs

1//! Minimum Feedback Arc Set problem implementation.
2//!
3//! The Feedback Arc Set problem asks for a minimum-weight subset of arcs
4//! whose removal makes a directed graph acyclic (a DAG).
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::DirectedGraph;
8use crate::traits::Problem;
9use crate::types::{Min, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumFeedbackArcSet",
16        display_name: "Minimum Feedback Arc Set",
17        aliases: &["FAS"],
18        dimensions: &[
19            VariantDimension::new("weight", "i64", &["i64"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find minimum weight feedback arc set in a directed graph",
24        fields: MinimumFeedbackArcSetCreateSpec::FIELDS,
25    }
26}
27
28/// The Minimum Feedback Arc Set problem.
29///
30/// Given a directed graph G = (V, A) and weights w_a for each arc,
31/// find a subset A' ⊆ A such that:
32/// - Removing A' from G yields a directed acyclic graph (DAG)
33/// - The total weight Σ_{a ∈ A'} w_a is minimized
34///
35/// # Variables
36///
37/// One binary variable per arc: x_a = 1 means arc a is in the feedback arc set (removed).
38/// The configuration space has dimension m = |A|.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::MinimumFeedbackArcSet;
44/// use problemreductions::topology::DirectedGraph;
45/// use problemreductions::{Problem, BruteForce};
46///
47/// // Directed cycle: 0->1->2->0
48/// let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
49/// let problem = MinimumFeedbackArcSet::new(graph, vec![1i64; 3]);
50///
51/// // Solve with brute force
52/// let solver = BruteForce::new();
53/// let solution = solver.solve(&problem).unwrap().unwrap();
54///
55/// // Minimum FAS has size 1 (remove any single arc to break the cycle)
56/// assert_eq!(solution.iter().filter(|&&selected| selected).count(), 1);
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(try_from = "MinimumFeedbackArcSetData<W>")]
60#[serde(bound(deserialize = "W: Clone + Default + Deserialize<'de>"))]
61pub struct MinimumFeedbackArcSet<W> {
62    /// The directed graph.
63    graph: DirectedGraph,
64    /// Weights for each arc.
65    weights: Vec<W>,
66}
67
68#[derive(Deserialize)]
69struct MinimumFeedbackArcSetData<W> {
70    graph: DirectedGraph,
71    weights: Vec<W>,
72}
73
74impl<W> TryFrom<MinimumFeedbackArcSetData<W>> for MinimumFeedbackArcSet<W>
75where
76    W: Clone + Default,
77{
78    type Error = crate::registry::ConstructionError;
79
80    fn try_from(data: MinimumFeedbackArcSetData<W>) -> Result<Self, Self::Error> {
81        Self::try_new(data.graph, data.weights)
82    }
83}
84
85#[derive(Debug, Deserialize, crate::CreateSpec)]
86struct MinimumFeedbackArcSetCreateSpec {
87    /// The directed graph.
88    graph: DirectedGraph,
89    /// Arc weights; defaults to one per arc.
90    weights: Option<Vec<i64>>,
91}
92impl TryFrom<MinimumFeedbackArcSetCreateSpec> for MinimumFeedbackArcSet<i64> {
93    type Error = crate::registry::ConstructionError;
94    fn try_from(spec: MinimumFeedbackArcSetCreateSpec) -> Result<Self, Self::Error> {
95        let count = spec.graph.num_arcs();
96        let weights = spec.weights.unwrap_or_else(|| vec![1; count]);
97        Self::try_new(spec.graph, weights)
98    }
99}
100
101impl<W: Clone + Default> MinimumFeedbackArcSet<W> {
102    /// Create a Minimum Feedback Arc Set problem from a directed graph with given weights.
103    pub fn new(graph: DirectedGraph, weights: Vec<W>) -> Self {
104        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
105    }
106
107    fn try_new(
108        graph: DirectedGraph,
109        weights: Vec<W>,
110    ) -> Result<Self, crate::registry::ConstructionError> {
111        Self::check_weights(&graph, &weights)?;
112        Ok(Self { graph, weights })
113    }
114
115    /// Get a reference to the underlying directed graph.
116    pub fn graph(&self) -> &DirectedGraph {
117        &self.graph
118    }
119
120    /// Get a reference to the weights slice.
121    pub fn weights(&self) -> &[W] {
122        &self.weights
123    }
124
125    /// Set arc weights.
126    pub fn set_weights(&mut self, weights: Vec<W>) {
127        Self::check_weights(&self.graph, &weights).unwrap_or_else(|error| panic!("{error}"));
128        self.weights = weights;
129    }
130
131    fn check_weights(
132        graph: &DirectedGraph,
133        weights: &[W],
134    ) -> Result<(), crate::registry::ConstructionError> {
135        if weights.len() != graph.num_arcs() {
136            return Err(crate::registry::ConstructionError::length_mismatch(
137                "weights",
138                weights.len(),
139                graph.num_arcs(),
140            ));
141        }
142        Ok(())
143    }
144
145    /// Check if a configuration is a valid feedback arc set.
146    ///
147    /// A configuration is valid if removing the selected arcs makes the graph acyclic.
148    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
149        is_valid_fas(&self.graph, config)
150    }
151}
152
153impl<W: WeightElement> MinimumFeedbackArcSet<W> {
154    /// Check if the problem has non-unit weights.
155    pub fn is_weighted(&self) -> bool {
156        !W::IS_UNIT
157    }
158
159    /// Get the number of vertices in the directed graph.
160    pub fn num_vertices(&self) -> usize {
161        self.graph.num_vertices()
162    }
163
164    /// Get the number of arcs in the directed graph.
165    pub fn num_arcs(&self) -> usize {
166        self.graph.num_arcs()
167    }
168}
169
170impl<W> Problem for MinimumFeedbackArcSet<W>
171where
172    W: WeightElement + crate::variant::VariantParam,
173{
174    const NAME: &'static str = "MinimumFeedbackArcSet";
175    type Solution = Vec<bool>;
176    type Value = Min<W::Sum>;
177
178    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
179
180    fn variant() -> Vec<(&'static str, &'static str)> {
181        crate::variant_params![W]
182    }
183
184    fn evaluate(
185        &self,
186        config: &Self::Solution,
187    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
188        if config.len() != self.graph.num_arcs() {
189            return Err(crate::traits::EvaluationError::InvalidConfiguration(
190                "arc-selection length does not match the graph".into(),
191            ));
192        }
193        Ok({
194            if !is_valid_fas(&self.graph, config) {
195                return Ok(Min(None));
196            }
197            let mut total = W::Sum::zero();
198            for (i, &selected) in config.iter().enumerate() {
199                if selected {
200                    total = W::checked_add_to_sum(
201                        total,
202                        self.weights[i].to_sum(),
203                        "summing selected feedback-arc weights",
204                    )?;
205                }
206            }
207            Min(Some(total))
208        })
209    }
210}
211
212impl<W> crate::solvers::BruteForceProblem for MinimumFeedbackArcSet<W>
213where
214    W: WeightElement + crate::variant::VariantParam,
215{
216    fn dimensions(&self) -> Vec<usize> {
217        vec![2; self.graph.num_arcs()]
218    }
219}
220
221/// Check if a configuration forms a valid feedback arc set.
222///
223/// config[i] = 1 means arc i is selected for removal.
224/// The remaining arcs must form a DAG.
225fn is_valid_fas(graph: &DirectedGraph, config: &[bool]) -> bool {
226    let num_arcs = graph.num_arcs();
227    if config.len() != num_arcs {
228        return false;
229    }
230    // kept_arcs[i] = true means arc i is NOT removed (kept in the graph)
231    let kept_arcs: Vec<bool> = config.iter().map(|&removed| !removed).collect();
232    graph.is_acyclic_subgraph(&kept_arcs)
233}
234
235crate::declare_variants! {
236    default MinimumFeedbackArcSet<i64> => "2^num_vertices" create MinimumFeedbackArcSetCreateSpec,
237}
238
239crate::register_brute_force! {
240    MinimumFeedbackArcSet<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
241}
242
243#[cfg(feature = "example-db")]
244pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
245    use crate::topology::DirectedGraph;
246    // 3-node cycle, unit weights; remove one arc to break cycle, cost = 1
247    vec![crate::example_db::specs::ModelExampleSpec {
248        id: "minimum_feedback_arc_set",
249        instance: Box::new(MinimumFeedbackArcSet::new(
250            DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
251            vec![1i64, 1, 1],
252        )),
253        optimal_config: serde_json::json!(vec![false, false, true]),
254        optimal_value: serde_json::json!(1),
255    }]
256}
257
258#[cfg(test)]
259#[path = "../../unit_tests/models/graph/minimum_feedback_arc_set.rs"]
260mod tests;
problemreductions/models/graph/minimum_feedback_arc_set.rs

problemreductions/models/graph/
minimum_feedback_arc_set.rs
