21958406699

Committed 12 Feb 2026 05:00PM UTC coverage: 61.964% (+1.1%) from 60.815%

Build # 21958406699

Build Type

push

github

Committed by

chrjabs

Commit Message

refactor: migrate `rustsat-tools` parsers to `winnow`

closes #564

Run Details

241 of 301 new or added lines in 6 files covered. (80.07%)

1102 existing lines in 16 files now uncovered.

14178 of 22881 relevant lines covered (61.96%)

140791.04 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

28.99

/src/instances/multiopt.rs

//! # Multi-Objective Optimization Instance Representations

use std::{collections::BTreeSet, io, path::Path};

use crate::{
    types::{Assignment, Lit, TernaryVal, Var, WClsIter, WLitIter},
    RequiresSoftLits,
};

use super::{
    fio::{self, dimacs::McnfLine},
    BasicVarManager, Cnf, ManageVars, Objective, ReindexVars, SatInstance, WriteDimacsError,
    WriteOpbError,
};

/// Type representing a multi-objective optimization instance.
/// The constraints are represented as a [`SatInstance`] struct.
#[derive(Clone, Debug, PartialEq, Eq, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct MultiOptInstance<VM: ManageVars = BasicVarManager> {
    pub(super) constrs: SatInstance<VM>,
    pub(super) objs: Vec<Objective>,
}

impl<VM: ManageVars> MultiOptInstance<VM> {
    /// Creates a new optimization instance with a specific var manager
    pub fn new_with_manager(n_objs: usize, var_manager: VM) -> Self {
        MultiOptInstance {
            constrs: SatInstance::new_with_manager(var_manager),
            objs: {
                let mut tmp = Vec::with_capacity(n_objs);
                tmp.resize(n_objs, Objective::new());
                tmp
            },
        }
    }

    /// Creates a new optimization instance from constraints and objectives
    pub fn compose(mut constraints: SatInstance<VM>, objectives: Vec<Objective>) -> Self {
        for o in &objectives {
            if let Some(mv) = o.max_var() {
                constraints.var_manager_mut().increase_next_free(mv + 1);
            }
        }
        MultiOptInstance {
            constrs: constraints,
            objs: objectives,
        }
    }

    /// Decomposes the optimization instance to a [`SatInstance`] and [`Objective`]s
    pub fn decompose(mut self) -> (SatInstance<VM>, Vec<Objective>) {
        let omv = self.objs.iter().fold(Var::new(0), |v, o| {
            if let Some(mv) = o.max_var() {
                return std::cmp::max(v, mv);
            }
            v
        });
        self.constrs.var_manager.increase_next_free(omv + 1);
        (self.constrs, self.objs)
    }

    /// Returns the number of objectives in the instance
    pub fn n_objectives(&self) -> usize {
        self.objs.len()
    }

    /// Gets a mutable reference to the hard constraints for modifying them
    pub fn constraints_mut(&mut self) -> &mut SatInstance<VM> {
        &mut self.constrs
    }

    /// Gets a reference to the hard constraints
    pub fn constraints_ref(&self) -> &SatInstance<VM> {
        &self.constrs
    }

    /// Reserves a new variable in the internal variable manager. This is a
    /// shortcut for `inst.get_constraints().var_manager().new_var()`.
    pub fn new_var(&mut self) -> Var {
        self.constraints_mut().var_manager_mut().new_var()
    }

    /// Reserves a new variable in the internal variable manager. This is a
    /// shortcut for `inst.get_constraints().var_manager().new_lit()`.
    pub fn new_lit(&mut self) -> Lit {
        self.constraints_mut().var_manager_mut().new_lit()
    }

    /// Gets the used variable with the highest index. This is a shortcut
    /// for `inst.get_constraints().var_manager().max_var()`.
    pub fn max_var(&self) -> Option<Var> {
        self.constraints_ref().var_manager_ref().max_var()
    }

    /// Gets a mutable reference to the objective with index `obj_idx` for modifying it.
    /// Make sure `obj_idx` does not exceed the number of objectives in the instance.
    ///
    /// # Panics
    ///
    /// If `obj_idx` exceeds the number of objectives in the instance.
    pub fn objective_mut(&mut self, obj_idx: usize) -> &mut Objective {
        assert!(obj_idx < self.objs.len());
        &mut self.objs[obj_idx]
    }

    /// Gets a reference to the objective with index `obj_idx`.
    /// Make sure `obj_idx` does not exceed the number of objectives in the instance.
    ///
    /// # Panics
    ///
    /// If `obj_idx` exceeds the number of objectives in the instance.
    pub fn objective_ref(&self, obj_idx: usize) -> &Objective {
        assert!(obj_idx < self.objs.len());
        &self.objs[obj_idx]
    }

    /// Returns an iterator over references to the objectives
    pub fn iter_obj(&self) -> impl Iterator<Item = &Objective> {
        self.objs.iter()
    }

    /// Returns an iterator over mutable references to the objectives
    pub fn iter_obj_mut(&mut self) -> impl Iterator<Item = &mut Objective> {
        self.objs.iter_mut()
    }

    /// Converts the instance to a set of hard and soft clauses
    ///
    /// # Panic
    ///
    /// This might panic if the conversion to [`Cnf`] runs out of memory.
    pub fn into_hard_cls_soft_cls(self) -> (Cnf, Vec<(impl WClsIter, isize)>, VM) {
        let (cnf, mut vm) = self.constrs.into_cnf();
        let omv = self.objs.iter().fold(Var::new(0), |v, o| {
            if let Some(mv) = o.max_var() {
                return std::cmp::max(v, mv);
            }
            v
        });
        vm.increase_next_free(omv + 1);
        let soft_cls = self
            .objs
            .into_iter()
            .map(Objective::into_soft_cls)
            .collect();
        (cnf, soft_cls, vm)
    }

    /// Converts the instance to a set of hard clauses and soft literals
    ///
    /// # Panic
    ///
    /// This might panic if the conversion to [`Cnf`] runs out of memory.
    pub fn into_hard_cls_soft_lits(self) -> (Cnf, Vec<(impl WLitIter, isize)>, VM) {
        let (mut cnf, mut vm) = self.constrs.into_cnf();
        let omv = self.objs.iter().fold(Var::new(0), |v, o| {
            if let Some(mv) = o.max_var() {
                return std::cmp::max(v, mv);
            }
            v
        });
        vm.increase_next_free(omv);
        let soft_lits = self
            .objs
            .into_iter()
            .map(|o| {
                let (hards, softs) = o.into_soft_lits(&mut vm);
                cnf.extend(hards);
                softs
            })
            .collect();
        (cnf, soft_lits, vm)
    }

    /// Converts the included variable manager to a different type
    pub fn change_var_manager<VM2, VMC>(self, vm_converter: VMC) -> (MultiOptInstance<VM2>, VM)
    where
        VM2: ManageVars + Default,
        VMC: Fn(&VM) -> VM2,
    {
        let (constrs, vm) = self.constrs.change_var_manager(vm_converter);
        (
            MultiOptInstance {
                constrs,
                objs: self.objs,
            },
            vm,
        )
    }

    /// Re-indexes all variables in the instance with a re-indexing variable manager
    pub fn reindex<R: ReindexVars>(self, mut reindexer: R) -> MultiOptInstance<R> {
        let objs = self
            .objs
            .into_iter()
            .map(|o| o.reindex(&mut reindexer))
            .collect();
        let constrs = self.constrs.reindex(reindexer);
        MultiOptInstance { constrs, objs }
    }

    fn extend_var_set(&self, varset: &mut BTreeSet<Var>) {
        self.constrs.extend_var_set(varset);
        for o in &self.objs {
            o.var_set(varset);
        }
    }

    /// Gets the set of variables in the instance
    pub fn var_set(&self) -> BTreeSet<Var> {
        let mut varset = BTreeSet::new();
        self.extend_var_set(&mut varset);
        varset
    }

    /// Re-index all variables in the instance in order
    ///
    /// If the re-indexing variable manager produces new free variables in order, this results in
    /// the variable _order_ being preserved with gaps in the variable space being closed
    #[must_use]
    pub fn reindex_ordered<R: ReindexVars>(self, mut reindexer: R) -> MultiOptInstance<R> {
        let mut varset = BTreeSet::new();
        self.extend_var_set(&mut varset);
        // reindex variables in order to ensure ordered re-indexing
        for var in varset {
            reindexer.reindex(var);
        }
        self.reindex(reindexer)
    }

    #[cfg(feature = "rand")]
    /// Randomly shuffles the order of constraints and the objective
    #[must_use]
    pub fn shuffle(mut self) -> Self {
        self.constrs = self.constrs.shuffle();
        self.objs = self.objs.into_iter().map(Objective::shuffle).collect();
        self
    }

    /// Writes the instance to a DIMACS MCNF file at a path
    ///
    /// This requires that the instance is clausal, i.e., does not contain any non-converted
    /// cardinality of pseudo-boolean constraints. If necessary, the instance can be converted by
    /// [`SatInstance::convert_to_cnf`] or [`SatInstance::convert_to_cnf_with_encoders`] first.
    ///
    /// # Errors
    ///
    /// If the instance is not clausal or writing fails
    pub fn write_dimacs_path<P: AsRef<Path>>(&self, path: P) -> Result<(), WriteDimacsError> {
        let mut writer = fio::open_compressed_uncompressed_write(path)?;
        self.write_dimacs(&mut writer)
    }

    /// Write to DIMACS MCNF
    ///
    /// This requires that the instance is clausal, i.e., does not contain any non-converted
    /// cardinality of pseudo-boolean constraints. If necessary, the instance can be converted by
    /// [`SatInstance::convert_to_cnf`] or [`SatInstance::convert_to_cnf_with_encoders`] first.
    ///
    /// # Performance
    ///
    /// For performance, consider using a [`std::io::BufWriter`] instance.
    ///
    /// # Errors
    ///
    /// If the instance is not clausal or writing fails
    pub fn write_dimacs<W: io::Write>(&self, writer: W) -> Result<(), WriteDimacsError> {
        if self.constrs.n_cards() > 0 || self.constrs.n_pbs() > 0 {
            return Err(WriteDimacsError::RequiresClausal);
        }
        let n_vars = self.constrs.n_vars();
        let iter = self.objs.iter().map(|o| {
            let offset = o.offset();
            (o.iter_soft_cls(), offset)
        });
        Ok(fio::dimacs::write_mcnf_annotated(
            writer,
            &self.constrs.cnf,
            iter,
            Some(n_vars),
        )?)
    }

    /// Writes the instance to an OPB file at a path
    ///
    /// This requires that the objective does not contain soft clauses. If it does, use
    /// [`Objective::convert_to_soft_lits`] first.
    ///
    /// # Errors
    ///
    /// If the objective contains soft clauses or writing fails
    pub fn write_opb_path<P: AsRef<Path>>(
        &self,
        path: P,
        opts: fio::opb::Options,
    ) -> Result<(), WriteOpbError> {
        let mut writer = fio::open_compressed_uncompressed_write(path)?;
        self.write_opb(&mut writer, opts)
    }

    /// Writes the instance to an OPB file
    ///
    /// This requires that the objective does not contain soft clauses. If it does, use
    /// [`Objective::convert_to_soft_lits`] first.
    ///
    /// # Performance
    ///
    /// For performance, consider using a [`std::io::BufWriter`] instance(crate).
    ///
    /// # Errors
    ///
    /// If the objective contains soft clauses or writing fails
    pub fn write_opb<W: io::Write>(
        &self,
        writer: W,
        opts: fio::opb::Options,
    ) -> Result<(), WriteOpbError> {
        let objs: Result<Vec<_>, RequiresSoftLits> = self
            .objs
            .iter()
            .map(|o| {
                let offset = o.offset();
                Ok((o.iter_soft_lits()?, offset))
            })
            .collect();
        let objs = objs?;
        Ok(fio::opb::write_multi_opt::<W, VM, _, _>(
            writer,
            &self.constrs,
            objs.into_iter(),
            opts,
        )?)
    }

    /// Calculates the objective values of an assignment. Returns [`None`] if the
    /// assignment is not a solution.
    pub fn cost(&self, assign: &Assignment) -> Option<Vec<isize>> {
        if self.constrs.evaluate(assign) != TernaryVal::True {
            return None;
        }
        Some(self.objs.iter().map(|o| o.evaluate(assign)).collect())
    }
}

impl<VM: ManageVars + Default> MultiOptInstance<VM> {
    /// Creates a new optimization instance
    #[must_use]
    pub fn new(n_objs: usize) -> Self {
        MultiOptInstance {
            constrs: SatInstance::new(),
            objs: {
                let mut tmp = Vec::with_capacity(n_objs);
                tmp.resize(n_objs, Objective::new());
                tmp
            },
        }
    }

    /// Parse a DIMACS instance from a reader object.
    ///
    /// # File Format
    ///
    /// The file format expected by this reader is an extension of the [new
    /// DIMACS WCNF
    /// format](https://maxsat-evaluations.github.io/2022/rules.html#input) to
    /// multiple objectives, which we call DIMACS MCNF. An example of this file
    /// format is the following:
    ///
    /// ```text
    /// c <comment>
    /// h 1 2 3 0
    /// o1 5 1 0
    /// o2 7 2 3 0
    /// ```
    ///
    /// Comments start with `c`, as in other DIMACS formats. Hard clauses start
    /// with an `h`, as in WCNF files. Soft clauses are of the following form
    /// `o<obj idx> <weight> <lit 1> ... <lit n> 0`. The first token must be a
    /// positive number preceded by an `o`, indicating what objective this soft
    /// clause belongs to. After that, the format is identical to a soft clause
    /// in a WCNF file.
    ///
    /// # Errors
    ///
    /// [`io::Error`] or if parsing fails.
    pub fn from_dimacs<R: io::BufRead>(reader: R) -> Result<Self, fio::Error> {
        let mut constrs = SatInstance::<VM>::default();
        let mut objs = vec![];
        for data in fio::dimacs::Parser::<fio::dimacs::Mcnf, _>::new(reader) {
            match data? {
                fio::dimacs::McnfData::HardClause(clause) => constrs.add_clause(clause),
                fio::dimacs::McnfData::SoftClause {
                    obj_idx,
                    weight,
                    clause,
                } => {
                    if obj_idx > objs.len() {
                        objs.resize(obj_idx, Objective::new());
                    }
                    objs[obj_idx - 1].increase_soft_clause(weight, clause);
                }
                fio::dimacs::McnfData::Comment(_) => (),
            }
        }
        Ok(Self::compose(constrs, objs))
    }

    /// Parses a DIMACS instance from a file path. For more details see
    /// [`OptInstance::from_dimacs`](super::OptInstance::from_dimacs).
    ///
    /// # Errors
    ///
    /// [`io::Error`] or if parsing fails.
    pub fn from_dimacs_path<P: AsRef<Path>>(path: P) -> Result<Self, fio::Error> {
        let mut reader = fio::open_compressed_uncompressed_read(path)?;
        Self::from_dimacs(&mut reader)
    }

    /// Parses an OPB instance from a reader object.
    ///
    /// # File Format
    ///
    /// The file format expected by this parser is the OPB format for
    /// pseudo-boolean optimization instances with multiple objectives defined.
    /// For details on the file format see
    /// [here](https://www.cril.univ-artois.fr/PB12/format.pdf).
    ///
    /// # Errors
    ///
    /// [`io::Error`] or if parsing fails.
    pub fn from_opb<R: io::BufRead>(
        reader: R,
        opts: fio::opb::Options,
    ) -> Result<Self, fio::Error> {
        fio::opb::Parser::new(reader, opts).collect()
    }

    /// Parses an OPB instance from a file path. For more details see
    /// [`MultiOptInstance::from_opb`]. With feature `compression` supports
    /// bzip2 and gzip compression, detected by the file extension.
    ///
    /// # Errors
    ///
    /// [`io::Error`] or if parsing fails.
    pub fn from_opb_path<P: AsRef<Path>>(
        path: P,
        opts: fio::opb::Options,
    ) -> Result<Self, fio::Error> {
        let mut reader = fio::open_compressed_uncompressed_read(path)?;
        Self::from_opb(&mut reader, opts)
    }
}

impl<VM: ManageVars + Default> FromIterator<McnfLine> for MultiOptInstance<VM> {
    fn from_iter<T: IntoIterator<Item = McnfLine>>(iter: T) -> Self {
        let mut inst = Self::default();
        for line in iter {
            match line {
                McnfLine::Comment(_) => (),
                McnfLine::Hard(cl) => inst.constraints_mut().add_clause(cl),
                McnfLine::Soft(cl, w, oidx) => {
                    if oidx >= inst.objs.len() {
                        inst.objs.resize(oidx + 1, Objective::default());
                    }
                    for l in &cl {
                        inst.constraints_mut().var_manager_mut().mark_used(l.var());
                    }
                    inst.objective_mut(oidx).add_soft_clause(w, cl);
                }
            }
        }
        inst
    }
}

impl<VM: ManageVars + Default> FromIterator<fio::opb::Data> for MultiOptInstance<VM> {
    fn from_iter<T: IntoIterator<Item = fio::opb::Data>>(iter: T) -> Self {
        let mut inst = Self::default();
        for data in iter {
            match data {
                fio::opb::Data::Cmt(_) => {}
                fio::opb::Data::Constr(constr) => inst.constraints_mut().add_pb_constr(constr),
                fio::opb::Data::Obj(fio::opb::Objective { terms, offset }) => {
                    for (_, lit) in &terms {
                        inst.constraints_mut()
                            .var_manager_mut()
                            .mark_used(lit.var());
                    }
                    let mut obj: crate::instances::Objective =
                        terms.into_iter().map(|(coeff, lit)| (lit, coeff)).collect();
                    obj.increase_offset(offset);
                    inst.objs.push(obj);
                }
            }
        }
        inst
    }
}

1	//! # Multi-Objective Optimization Instance Representations
2
3	use std::{collections::BTreeSet, io, path::Path};
4
5	use crate::{
6	types::{Assignment, Lit, TernaryVal, Var, WClsIter, WLitIter},
7	RequiresSoftLits,
8	};
9
10	use super::{
11	fio::{self, dimacs::McnfLine},
12	BasicVarManager, Cnf, ManageVars, Objective, ReindexVars, SatInstance, WriteDimacsError,
13	WriteOpbError,
14	};
15
16	/// Type representing a multi-objective optimization instance.
17	/// The constraints are represented as a [`SatInstance`] struct.
18	#[derive(Clone, Debug, PartialEq, Eq, Default)]
19	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
20	pub struct MultiOptInstance<VM: ManageVars = BasicVarManager> {
21	pub(super) constrs: SatInstance<VM>,
22	pub(super) objs: Vec<Objective>,
23	}
24
25	impl<VM: ManageVars> MultiOptInstance<VM> {
26	/// Creates a new optimization instance with a specific var manager
27	pub fn new_with_manager(n_objs: usize, var_manager: VM) -> Self {	×
28	MultiOptInstance {	×
29	constrs: SatInstance::new_with_manager(var_manager),	×
30	objs: {	×
31	let mut tmp = Vec::with_capacity(n_objs);	×
32	tmp.resize(n_objs, Objective::new());	×
33	tmp	×
34	},	×
35	}	×
UNCOV 36	}	×
37
38	/// Creates a new optimization instance from constraints and objectives
39	pub fn compose(mut constraints: SatInstance<VM>, objectives: Vec<Objective>) -> Self {	6✔
40	for o in &objectives {	18✔
41	if let Some(mv) = o.max_var() {	12✔
42	constraints.var_manager_mut().increase_next_free(mv + 1);	12✔
43	}	12✔
44	}
45	MultiOptInstance {	6✔
46	constrs: constraints,	6✔
47	objs: objectives,	6✔
48	}	6✔
49	}	6✔
50
51	/// Decomposes the optimization instance to a [`SatInstance`] and [`Objective`]s
52	pub fn decompose(mut self) -> (SatInstance<VM>, Vec<Objective>) {	×
53	let omv = self.objs.iter().fold(Var::new(0), \|v, o\| {	×
54	if let Some(mv) = o.max_var() {	×
55	return std::cmp::max(v, mv);	×
56	}	×
57	v	×
58	});	×
59	self.constrs.var_manager.increase_next_free(omv + 1);	×
60	(self.constrs, self.objs)	×
UNCOV 61	}	×
62
63	/// Returns the number of objectives in the instance
64	pub fn n_objectives(&self) -> usize {	×
65	self.objs.len()	×
UNCOV 66	}	×
67
68	/// Gets a mutable reference to the hard constraints for modifying them
69	pub fn constraints_mut(&mut self) -> &mut SatInstance<VM> {	10✔
70	&mut self.constrs	10✔
71	}	10✔
72
73	/// Gets a reference to the hard constraints
74	pub fn constraints_ref(&self) -> &SatInstance<VM> {	×
75	&self.constrs	×
UNCOV 76	}	×
77
78	/// Reserves a new variable in the internal variable manager. This is a
79	/// shortcut for `inst.get_constraints().var_manager().new_var()`.
80	pub fn new_var(&mut self) -> Var {	×
81	self.constraints_mut().var_manager_mut().new_var()	×
UNCOV 82	}	×
83
84	/// Reserves a new variable in the internal variable manager. This is a
85	/// shortcut for `inst.get_constraints().var_manager().new_lit()`.
86	pub fn new_lit(&mut self) -> Lit {	×
87	self.constraints_mut().var_manager_mut().new_lit()	×
UNCOV 88	}	×
89
90	/// Gets the used variable with the highest index. This is a shortcut
91	/// for `inst.get_constraints().var_manager().max_var()`.
92	pub fn max_var(&self) -> Option<Var> {	×
93	self.constraints_ref().var_manager_ref().max_var()	×
UNCOV 94	}	×
95
96	/// Gets a mutable reference to the objective with index `obj_idx` for modifying it.
97	/// Make sure `obj_idx` does not exceed the number of objectives in the instance.
98	///
99	/// # Panics
100	///
101	/// If `obj_idx` exceeds the number of objectives in the instance.
102	pub fn objective_mut(&mut self, obj_idx: usize) -> &mut Objective {	×
103	assert!(obj_idx < self.objs.len());	×
104	&mut self.objs[obj_idx]	×
UNCOV 105	}	×
106
107	/// Gets a reference to the objective with index `obj_idx`.
108	/// Make sure `obj_idx` does not exceed the number of objectives in the instance.
109	///
110	/// # Panics
111	///
112	/// If `obj_idx` exceeds the number of objectives in the instance.
113	pub fn objective_ref(&self, obj_idx: usize) -> &Objective {	×
114	assert!(obj_idx < self.objs.len());	×
115	&self.objs[obj_idx]	×
UNCOV 116	}	×
117
118	/// Returns an iterator over references to the objectives
119	pub fn iter_obj(&self) -> impl Iterator<Item = &Objective> {	×
120	self.objs.iter()	×
UNCOV 121	}	×
122
123	/// Returns an iterator over mutable references to the objectives
124	pub fn iter_obj_mut(&mut self) -> impl Iterator<Item = &mut Objective> {	×
125	self.objs.iter_mut()	×
UNCOV 126	}	×
127
128	/// Converts the instance to a set of hard and soft clauses
129	///
130	/// # Panic
131	///
132	/// This might panic if the conversion to [`Cnf`] runs out of memory.
133	pub fn into_hard_cls_soft_cls(self) -> (Cnf, Vec<(impl WClsIter, isize)>, VM) {	×
134	let (cnf, mut vm) = self.constrs.into_cnf();	×
135	let omv = self.objs.iter().fold(Var::new(0), \|v, o\| {	×
136	if let Some(mv) = o.max_var() {	×
137	return std::cmp::max(v, mv);	×
138	}	×
139	v	×
140	});	×
141	vm.increase_next_free(omv + 1);	×
142	let soft_cls = self	×
143	.objs	×
144	.into_iter()	×
145	.map(Objective::into_soft_cls)	×
146	.collect();	×
147	(cnf, soft_cls, vm)	×
UNCOV 148	}	×
149
150	/// Converts the instance to a set of hard clauses and soft literals
151	///
152	/// # Panic
153	///
154	/// This might panic if the conversion to [`Cnf`] runs out of memory.
155	pub fn into_hard_cls_soft_lits(self) -> (Cnf, Vec<(impl WLitIter, isize)>, VM) {	×
156	let (mut cnf, mut vm) = self.constrs.into_cnf();	×
157	let omv = self.objs.iter().fold(Var::new(0), \|v, o\| {	×
158	if let Some(mv) = o.max_var() {	×
159	return std::cmp::max(v, mv);	×
160	}	×
161	v	×
162	});	×
163	vm.increase_next_free(omv);	×
164	let soft_lits = self	×
165	.objs	×
166	.into_iter()	×
167	.map(\|o\| {	×
168	let (hards, softs) = o.into_soft_lits(&mut vm);	×
169	cnf.extend(hards);	×
170	softs	×
171	})	×
172	.collect();	×
173	(cnf, soft_lits, vm)	×
UNCOV 174	}	×
175
176	/// Converts the included variable manager to a different type
177	pub fn change_var_manager<VM2, VMC>(self, vm_converter: VMC) -> (MultiOptInstance<VM2>, VM)	×
178	where	×
179	VM2: ManageVars + Default,	×
UNCOV 180	VMC: Fn(&VM) -> VM2,	×
181	{
182	let (constrs, vm) = self.constrs.change_var_manager(vm_converter);	×
183	(	×
184	MultiOptInstance {	×
185	constrs,	×
186	objs: self.objs,	×
187	},	×
188	vm,	×
189	)	×
UNCOV 190	}	×
191
192	/// Re-indexes all variables in the instance with a re-indexing variable manager
193	pub fn reindex<R: ReindexVars>(self, mut reindexer: R) -> MultiOptInstance<R> {	×
194	let objs = self	×
195	.objs	×
196	.into_iter()	×
197	.map(\|o\| o.reindex(&mut reindexer))	×
198	.collect();	×
199	let constrs = self.constrs.reindex(reindexer);	×
200	MultiOptInstance { constrs, objs }	×
UNCOV 201	}	×
202
203	fn extend_var_set(&self, varset: &mut BTreeSet<Var>) {	×
204	self.constrs.extend_var_set(varset);	×
205	for o in &self.objs {	×
206	o.var_set(varset);	×
207	}	×
UNCOV 208	}	×
209
210	/// Gets the set of variables in the instance
211	pub fn var_set(&self) -> BTreeSet<Var> {	×
212	let mut varset = BTreeSet::new();	×
213	self.extend_var_set(&mut varset);	×
214	varset	×
UNCOV 215	}	×
216
217	/// Re-index all variables in the instance in order
218	///
219	/// If the re-indexing variable manager produces new free variables in order, this results in
220	/// the variable _order_ being preserved with gaps in the variable space being closed
221	#[must_use]
222	pub fn reindex_ordered<R: ReindexVars>(self, mut reindexer: R) -> MultiOptInstance<R> {	×
223	let mut varset = BTreeSet::new();	×
UNCOV 224	self.extend_var_set(&mut varset);	×
225	// reindex variables in order to ensure ordered re-indexing
226	for var in varset {	×
227	reindexer.reindex(var);	×
228	}	×
229	self.reindex(reindexer)	×
UNCOV 230	}	×
231
232	#[cfg(feature = "rand")]
233	/// Randomly shuffles the order of constraints and the objective
234	#[must_use]
235	pub fn shuffle(mut self) -> Self {	×
236	self.constrs = self.constrs.shuffle();	×
237	self.objs = self.objs.into_iter().map(Objective::shuffle).collect();	×
238	self	×
UNCOV 239	}	×
240
241	/// Writes the instance to a DIMACS MCNF file at a path
242	///
243	/// This requires that the instance is clausal, i.e., does not contain any non-converted
244	/// cardinality of pseudo-boolean constraints. If necessary, the instance can be converted by
245	/// [`SatInstance::convert_to_cnf`] or [`SatInstance::convert_to_cnf_with_encoders`] first.
246	///
247	/// # Errors
248	///
249	/// If the instance is not clausal or writing fails
250	pub fn write_dimacs_path<P: AsRef<Path>>(&self, path: P) -> Result<(), WriteDimacsError> {	×
251	let mut writer = fio::open_compressed_uncompressed_write(path)?;	×
252	self.write_dimacs(&mut writer)	×
253	}	×
254
255	/// Write to DIMACS MCNF
256	///
257	/// This requires that the instance is clausal, i.e., does not contain any non-converted
258	/// cardinality of pseudo-boolean constraints. If necessary, the instance can be converted by
259	/// [`SatInstance::convert_to_cnf`] or [`SatInstance::convert_to_cnf_with_encoders`] first.
260	///
261	/// # Performance
262	///
263	/// For performance, consider using a [`std::io::BufWriter`] instance.
264	///
265	/// # Errors
266	///
267	/// If the instance is not clausal or writing fails
UNCOV 268	pub fn write_dimacs<W: io::Write>(&self, writer: W) -> Result<(), WriteDimacsError> {	×
269	if self.constrs.n_cards() > 0 \|\| self.constrs.n_pbs() > 0 {	×
270	return Err(WriteDimacsError::RequiresClausal);	×
271	}	×
272	let n_vars = self.constrs.n_vars();	×
273	let iter = self.objs.iter().map(\|o\| {	×
274	let offset = o.offset();	×
275	(o.iter_soft_cls(), offset)	×
276	});	×
277	Ok(fio::dimacs::write_mcnf_annotated(	×
278	writer,	×
279	&self.constrs.cnf,	×
280	iter,	×
281	Some(n_vars),	×
282	)?)	×
283	}	×
284
285	/// Writes the instance to an OPB file at a path
286	///
287	/// This requires that the objective does not contain soft clauses. If it does, use
288	/// [`Objective::convert_to_soft_lits`] first.
289	///
290	/// # Errors
291	///
292	/// If the objective contains soft clauses or writing fails
UNCOV 293	pub fn write_opb_path<P: AsRef<Path>>(	×
UNCOV 294	&self,	×
295	path: P,	×
296	opts: fio::opb::Options,	×
297	) -> Result<(), WriteOpbError> {	×
298	let mut writer = fio::open_compressed_uncompressed_write(path)?;	×
299	self.write_opb(&mut writer, opts)	×
300	}	×
301
302	/// Writes the instance to an OPB file
303	///
304	/// This requires that the objective does not contain soft clauses. If it does, use
305	/// [`Objective::convert_to_soft_lits`] first.
306	///
307	/// # Performance
308	///
309	/// For performance, consider using a [`std::io::BufWriter`] instance(crate).
310	///
311	/// # Errors
312	///
313	/// If the objective contains soft clauses or writing fails
314	pub fn write_opb<W: io::Write>(	1✔
315	&self,	1✔
316	writer: W,	1✔
317	opts: fio::opb::Options,	1✔
318	) -> Result<(), WriteOpbError> {	1✔
319	let objs: Result<Vec<_>, RequiresSoftLits> = self	1✔
320	.objs	1✔
321	.iter()	1✔
322	.map(\|o\| {	2✔
323	let offset = o.offset();	2✔
324	Ok((o.iter_soft_lits()?, offset))	2✔
325	})	2✔
326	.collect();	1✔
327	let objs = objs?;	1✔
328	Ok(fio::opb::write_multi_opt::<W, VM, _, _>(	1✔
329	writer,	1✔
330	&self.constrs,	1✔
331	objs.into_iter(),	1✔
332	opts,	1✔
333	)?)	×
334	}	1✔
335
336	/// Calculates the objective values of an assignment. Returns [`None`] if the
337	/// assignment is not a solution.
UNCOV 338	pub fn cost(&self, assign: &Assignment) -> Option<Vec<isize>> {	×
UNCOV 339	if self.constrs.evaluate(assign) != TernaryVal::True {	×
UNCOV 340	return None;	×
341	}	×
342	Some(self.objs.iter().map(\|o\| o.evaluate(assign)).collect())	×
343	}	×
344	}
345
346	impl<VM: ManageVars + Default> MultiOptInstance<VM> {
347	/// Creates a new optimization instance
348	#[must_use]
UNCOV 349	pub fn new(n_objs: usize) -> Self {	×
UNCOV 350	MultiOptInstance {	×
UNCOV 351	constrs: SatInstance::new(),	×
352	objs: {	×
353	let mut tmp = Vec::with_capacity(n_objs);	×
354	tmp.resize(n_objs, Objective::new());	×
355	tmp	×
356	},	×
357	}	×
358	}	×
359
360	/// Parse a DIMACS instance from a reader object.
361	///
362	/// # File Format
363	///
364	/// The file format expected by this reader is an extension of the [new
365	/// DIMACS WCNF
366	/// format](https://maxsat-evaluations.github.io/2022/rules.html#input) to
367	/// multiple objectives, which we call DIMACS MCNF. An example of this file
368	/// format is the following:
369	///
370	/// ```text
371	/// c <comment>
372	/// h 1 2 3 0
373	/// o1 5 1 0
374	/// o2 7 2 3 0
375	/// ```
376	///
377	/// Comments start with `c`, as in other DIMACS formats. Hard clauses start
378	/// with an `h`, as in WCNF files. Soft clauses are of the following form
379	/// `o<obj idx> <weight> <lit 1> ... <lit n> 0`. The first token must be a
380	/// positive number preceded by an `o`, indicating what objective this soft
381	/// clause belongs to. After that, the format is identical to a soft clause
382	/// in a WCNF file.
383	///
384	/// # Errors
385	///
386	/// [`io::Error`] or if parsing fails.
387	pub fn from_dimacs<R: io::BufRead>(reader: R) -> Result<Self, fio::Error> {	3✔
388	let mut constrs = SatInstance::<VM>::default();	3✔
389	let mut objs = vec![];	3✔
390	for data in fio::dimacs::Parser::<fio::dimacs::Mcnf, _>::new(reader) {	19✔
391	match data? {	19✔
392	fio::dimacs::McnfData::HardClause(clause) => constrs.add_clause(clause),	3✔
393	fio::dimacs::McnfData::SoftClause {
394	obj_idx,	8✔
395	weight,	8✔
396	clause,	8✔
397	} => {
398	if obj_idx > objs.len() {	8✔
399	objs.resize(obj_idx, Objective::new());	4✔
400	}	4✔
401	objs[obj_idx - 1].increase_soft_clause(weight, clause);	8✔
402	}
403	fio::dimacs::McnfData::Comment(_) => (),	8✔
404	}
405	}
406	Ok(Self::compose(constrs, objs))	3✔
407	}	3✔
408
409	/// Parses a DIMACS instance from a file path. For more details see
410	/// [`OptInstance::from_dimacs`](super::OptInstance::from_dimacs).
411	///
412	/// # Errors
413	///
414	/// [`io::Error`] or if parsing fails.
UNCOV 415	pub fn from_dimacs_path<P: AsRef<Path>>(path: P) -> Result<Self, fio::Error> {	×
UNCOV 416	let mut reader = fio::open_compressed_uncompressed_read(path)?;	×
UNCOV 417	Self::from_dimacs(&mut reader)	×
UNCOV 418	}	×
419
420	/// Parses an OPB instance from a reader object.
421	///
422	/// # File Format
423	///
424	/// The file format expected by this parser is the OPB format for
425	/// pseudo-boolean optimization instances with multiple objectives defined.
426	/// For details on the file format see
427	/// [here](https://www.cril.univ-artois.fr/PB12/format.pdf).
428	///
429	/// # Errors
430	///
431	/// [`io::Error`] or if parsing fails.
432	pub fn from_opb<R: io::BufRead>(	2✔
433	reader: R,	2✔
434	opts: fio::opb::Options,	2✔
435	) -> Result<Self, fio::Error> {	2✔
436	fio::opb::Parser::new(reader, opts).collect()	2✔
437	}	2✔
438
439	/// Parses an OPB instance from a file path. For more details see
440	/// [`MultiOptInstance::from_opb`]. With feature `compression` supports
441	/// bzip2 and gzip compression, detected by the file extension.
442	///
443	/// # Errors
444	///
445	/// [`io::Error`] or if parsing fails.
446	pub fn from_opb_path<P: AsRef<Path>>(	1✔
447	path: P,	1✔
448	opts: fio::opb::Options,	1✔
449	) -> Result<Self, fio::Error> {	1✔
450	let mut reader = fio::open_compressed_uncompressed_read(path)?;	1✔
451	Self::from_opb(&mut reader, opts)	1✔
452	}	1✔
453	}
454
455	impl<VM: ManageVars + Default> FromIterator<McnfLine> for MultiOptInstance<VM> {
UNCOV 456	fn from_iter<T: IntoIterator<Item = McnfLine>>(iter: T) -> Self {	×
UNCOV 457	let mut inst = Self::default();	×
UNCOV 458	for line in iter {	×
UNCOV 459	match line {	×
UNCOV 460	McnfLine::Comment(_) => (),	×
UNCOV 461	McnfLine::Hard(cl) => inst.constraints_mut().add_clause(cl),	×
UNCOV 462	McnfLine::Soft(cl, w, oidx) => {	×
UNCOV 463	if oidx >= inst.objs.len() {	×
UNCOV 464	inst.objs.resize(oidx + 1, Objective::default());	×
UNCOV 465	}	×
UNCOV 466	for l in &cl {	×
UNCOV 467	inst.constraints_mut().var_manager_mut().mark_used(l.var());	×
UNCOV 468	}	×
UNCOV 469	inst.objective_mut(oidx).add_soft_clause(w, cl);	×
470	}
471	}
472	}
UNCOV 473	inst	×
UNCOV 474	}	×
475	}
476
477	impl<VM: ManageVars + Default> FromIterator<fio::opb::Data> for MultiOptInstance<VM> {
478	fn from_iter<T: IntoIterator<Item = fio::opb::Data>>(iter: T) -> Self {	2✔
479	let mut inst = Self::default();	2✔
480	for data in iter {	19✔
481	match data {	17✔
482	fio::opb::Data::Cmt(_) => {}	9✔
483	fio::opb::Data::Constr(constr) => inst.constraints_mut().add_pb_constr(constr),	4✔
484	fio::opb::Data::Obj(fio::opb::Objective { terms, offset }) => {	4✔
485	for (_, lit) in &terms {	10✔
486	inst.constraints_mut()	6✔
487	.var_manager_mut()	6✔
488	.mark_used(lit.var());	6✔
489	}	6✔
490	let mut obj: crate::instances::Objective =	4✔
491	terms.into_iter().map(\|(coeff, lit)\| (lit, coeff)).collect();	6✔
492	obj.increase_offset(offset);	4✔
493	inst.objs.push(obj);	4✔
494	}
495	}
496	}
497	inst	2✔
498	}	2✔
499	}

chrjabs / rustsat / 21958406699

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous