quantrs2_tytan/problem_decomposition/
types.rs

1//! Data structures and types for problem decomposition
2
3use crate::sampler::SampleResult;
4use scirs2_core::ndarray::Array2;
5use std::collections::{HashMap, HashSet};
6
7/// Graph representation for partitioning
8#[derive(Debug, Clone)]
9pub struct Graph {
10    pub num_nodes: usize,
11    pub edges: Vec<Edge>,
12    pub node_weights: Vec<f64>,
13}
14
15/// Graph edge
16#[derive(Debug, Clone)]
17pub struct Edge {
18    pub from: usize,
19    pub to: usize,
20    pub weight: f64,
21}
22
23/// Partitioning algorithms
24#[derive(Debug, Clone)]
25pub enum PartitioningAlgorithm {
26    /// Kernighan-Lin algorithm
27    KernighanLin,
28    /// Fiduccia-Mattheyses algorithm
29    FiducciaMattheyses,
30    /// Spectral partitioning
31    Spectral,
32    /// METIS-style multilevel
33    Multilevel,
34    /// Community detection
35    CommunityDetection,
36    /// Min-cut max-flow
37    MinCutMaxFlow,
38}
39
40/// Result of partitioning
41#[derive(Debug, Clone)]
42pub struct Partitioning {
43    pub partition_assignment: Vec<usize>,
44    pub subproblems: Vec<Subproblem>,
45    pub coupling_terms: Vec<CouplingTerm>,
46    pub metrics: PartitionMetrics,
47}
48
49/// Individual subproblem
50#[derive(Debug, Clone)]
51pub struct Subproblem {
52    pub id: usize,
53    pub variables: Vec<String>,
54    pub qubo: Array2<f64>,
55    pub var_map: HashMap<String, usize>,
56}
57
58/// Coupling between subproblems
59#[derive(Debug, Clone)]
60pub struct CouplingTerm {
61    pub var1: String,
62    pub var2: String,
63    pub subproblem1: usize,
64    pub subproblem2: usize,
65    pub weight: f64,
66}
67
68/// Partition quality metrics
69#[derive(Debug, Clone)]
70pub struct PartitionMetrics {
71    pub edge_cut: f64,
72    pub balance: f64,
73    pub modularity: f64,
74    pub conductance: f64,
75}
76
77/// Hierarchical solving strategies
78#[derive(Debug, Clone)]
79pub enum HierarchicalStrategy {
80    /// Coarsen then solve
81    CoarsenSolve,
82    /// Multi-grid approach
83    MultiGrid,
84    /// V-cycle
85    VCycle,
86}
87
88/// Coarsening strategies
89#[derive(Debug, Clone)]
90pub enum CoarseningStrategy {
91    /// Cluster strongly connected variables
92    VariableClustering,
93    /// Edge collapsing
94    EdgeCollapsing,
95    /// Algebraic multigrid
96    AlgebraicMultigrid,
97}
98
99/// Hierarchy of problems
100#[derive(Debug, Clone)]
101pub struct Hierarchy {
102    pub levels: Vec<HierarchyLevel>,
103    pub projections: Vec<Projection>,
104}
105
106/// Single level in hierarchy
107#[derive(Debug, Clone)]
108pub struct HierarchyLevel {
109    pub level: usize,
110    pub qubo: Array2<f64>,
111    pub var_map: HashMap<String, usize>,
112    pub size: usize,
113}
114
115/// Projection between levels
116#[derive(Debug, Clone)]
117pub struct Projection {
118    pub fine_to_coarse: Vec<usize>,
119    pub coarse_to_fine: Vec<Vec<usize>>,
120}
121
122/// Domain decomposition strategies
123#[derive(Debug, Clone)]
124pub enum DecompositionStrategy {
125    /// Schwarz alternating method
126    Schwarz,
127    /// Block Jacobi
128    BlockJacobi,
129    /// Additive Schwarz
130    AdditiveSchwarz,
131    /// Multiplicative Schwarz
132    MultiplicativeSchwarz,
133}
134
135/// Coordination strategies for parallel solving
136#[derive(Debug, Clone)]
137pub enum CoordinationStrategy {
138    /// Alternating Direction Method of Multipliers
139    ADMM { rho: f64 },
140    /// Consensus approach
141    Consensus,
142    /// Lagrangian relaxation
143    LagrangianRelaxation,
144    /// Price coordination
145    PriceCoordination,
146}
147
148/// Domain for decomposition
149#[derive(Debug, Clone)]
150pub struct Domain {
151    pub id: usize,
152    pub variables: Vec<String>,
153    pub qubo: Array2<f64>,
154    pub var_map: HashMap<String, usize>,
155    pub boundary_vars: Vec<usize>,
156    pub internal_vars: Vec<usize>,
157}
158
159/// Coordination state for parallel solving
160#[derive(Debug, Clone)]
161pub struct CoordinationState {
162    pub iteration: usize,
163    pub lagrange_multipliers: Option<HashMap<(usize, usize), f64>>,
164    pub consensus_variables: Option<HashMap<usize, bool>>,
165    pub convergence_tolerance: f64,
166    pub max_iterations: usize,
167}
168
169/// Solution for a subdomain
170#[derive(Debug, Clone)]
171pub struct SubdomainSolution {
172    pub domain_id: usize,
173    pub results: SampleResult,
174}
175
176/// CSP decomposition strategies
177#[derive(Debug, Clone)]
178pub enum CSPDecompositionStrategy {
179    /// Tree decomposition
180    TreeDecomposition,
181    /// Constraint clustering
182    ConstraintClustering,
183    /// Cycle cutset
184    CycleCutset,
185    /// Bucket elimination
186    BucketElimination,
187}
188
189/// Variable ordering heuristics
190#[derive(Debug, Clone)]
191pub enum VariableOrderingHeuristic {
192    /// Minimum width ordering
193    MinWidth,
194    /// Maximum cardinality
195    MaxCardinality,
196    /// Fill-in heuristic
197    MinFillIn,
198    /// Weighted min-fill
199    WeightedMinFill,
200}
201
202/// Constraint propagation levels
203#[derive(Debug, Clone)]
204pub enum PropagationLevel {
205    /// No propagation
206    None,
207    /// Arc consistency
208    ArcConsistency,
209    /// Path consistency
210    PathConsistency,
211    /// Full consistency
212    FullConsistency,
213}
214
215/// CSP Problem representation
216#[derive(Debug, Clone)]
217pub struct CSPProblem {
218    pub variables: HashMap<String, DomainCsp>,
219    pub constraints: Vec<CSPConstraint>,
220    pub constraint_graph: ConstraintGraph,
221}
222
223/// CSP variable domain
224#[derive(Debug, Clone)]
225pub struct DomainCsp {
226    pub values: Vec<i32>,
227}
228
229/// CSP constraint
230#[derive(Debug, Clone)]
231pub struct CSPConstraint {
232    pub id: usize,
233    pub scope: Vec<String>,
234    pub constraint_type: ConstraintType,
235    pub tuples: Option<Vec<Vec<i32>>>,
236}
237
238/// Constraint types
239#[derive(Debug, Clone)]
240pub enum ConstraintType {
241    /// All variables must be different
242    AllDifferent,
243    /// Linear constraint
244    Linear { coefficients: Vec<f64>, rhs: f64 },
245    /// Table constraint
246    Table,
247    /// Global constraint
248    Global { name: String },
249}
250
251/// Constraint graph for CSP
252#[derive(Debug, Clone)]
253pub struct ConstraintGraph {
254    /// Adjacency list representation
255    pub adjacency: HashMap<String, HashSet<String>>,
256    /// Constraint hypergraph
257    pub hyperedges: Vec<HashSet<String>>,
258}
259
260/// CSP decomposition result
261#[derive(Debug, Clone)]
262pub struct CSPDecomposition {
263    pub clusters: Vec<CSPCluster>,
264    pub cluster_tree: ClusterTree,
265    pub separator_sets: Vec<HashSet<String>>,
266    pub width: usize,
267}
268
269/// CSP cluster
270#[derive(Debug, Clone)]
271pub struct CSPCluster {
272    pub id: usize,
273    pub variables: HashSet<String>,
274    pub constraints: Vec<usize>,
275    pub subproblem: Option<CSPSubproblem>,
276}
277
278/// CSP subproblem
279#[derive(Debug, Clone)]
280pub struct CSPSubproblem {
281    pub variables: HashMap<String, DomainCsp>,
282    pub constraints: Vec<CSPConstraint>,
283}
284
285/// Cluster tree for CSP
286#[derive(Debug, Clone)]
287pub struct ClusterTree {
288    pub nodes: Vec<TreeNode>,
289    pub edges: Vec<(usize, usize)>,
290    pub root: usize,
291}
292
293/// Tree node in cluster tree
294#[derive(Debug, Clone)]
295pub struct TreeNode {
296    pub id: usize,
297    pub cluster_id: usize,
298    pub separator: HashSet<String>,
299    pub children: Vec<usize>,
300    pub parent: Option<usize>,
301}
302
303/// Tree decomposition result
304#[derive(Debug, Clone)]
305pub struct TreeDecomposition {
306    pub bags: Vec<HashSet<String>>,
307    pub tree_edges: Vec<(usize, usize)>,
308    pub width: usize,
309}
310
311/// Decomposition metrics
312#[derive(Debug, Clone)]
313pub struct DecompositionMetrics {
314    pub width: usize,
315    pub num_clusters: usize,
316    pub balance_factor: f64,
317    pub separator_size: f64,
318    pub decomposition_time: std::time::Duration,
319}
320
321/// Solution integration strategies
322#[derive(Debug, Clone)]
323pub enum IntegrationStrategy {
324    /// Weighted voting
325    WeightedVoting,
326    /// Consensus building
327    Consensus,
328    /// Best solution selection
329    BestSelection,
330    /// Majority voting
331    MajorityVoting,
332}
333
334/// Integrated solution result
335#[derive(Debug, Clone)]
336pub struct IntegratedSolution {
337    pub assignment: HashMap<String, bool>,
338    pub energy: f64,
339    pub confidence: f64,
340    pub component_solutions: Vec<ComponentSolution>,
341}
342
343/// Component solution from subproblem
344#[derive(Debug, Clone)]
345pub struct ComponentSolution {
346    pub subproblem_id: usize,
347    pub assignment: HashMap<String, bool>,
348    pub energy: f64,
349    pub weight: f64,
350}
351
352/// Decomposition configuration
353#[derive(Debug, Clone)]
354pub struct DecompositionConfig {
355    pub max_subproblem_size: usize,
356    pub min_subproblem_size: usize,
357    pub overlap_factor: f64,
358    pub balance_tolerance: f64,
359    pub quality_threshold: f64,
360}
361
362/// Parallel execution configuration
363#[derive(Debug, Clone)]
364pub struct ParallelConfig {
365    pub num_threads: usize,
366    pub thread_pool_size: usize,
367    pub load_balancing: bool,
368    pub dynamic_scheduling: bool,
369}
quantrs2_tytan/problem_decomposition/types.rs

quantrs2_tytan/problem_decomposition/
types.rs
