geometric_traits/traits/algorithms/
clique_ranking.rs

1//! Composable clique ranking for MCES result selection.
2//!
3//! When the MCES pipeline finds multiple maximum cliques of the same size,
4//! a ranking system selects the best one. This module provides:
5//!
6//! - [`CliqueInfo`] — trait for accessing precomputed clique data.
7//! - [`EagerCliqueInfo`] — concrete implementation that eagerly computes
8//!   matched edges, vertex matches, and fragment structure.
9//! - [`CliqueRanker`] — trait for comparing two cliques; composable via
10//!   [`then`](CliqueRankerExt::then) into zero-cost [`ChainedRanker`] chains.
11//! - [`FragmentCountRanker`] — ranks by number of connected fragments (fewer =
12//!   better).
13//!
14//! The ranking chain is fully monomorphized at compile time — no dynamic
15//! dispatch, no vtable overhead.
16//!
17//! # Example
18//!
19//! ```
20//! use core::cmp::Ordering;
21//!
22//! use geometric_traits::prelude::*;
23//!
24//! // Custom ranker: prefer more vertex matches.
25//! struct MoreVerticesRanker;
26//!
27//! impl<I: CliqueInfo> CliqueRanker<I> for MoreVerticesRanker {
28//!     fn compare(&self, a: &I, b: &I) -> Ordering {
29//!         // More vertices = better → reverse order
30//!         b.vertex_matches().len().cmp(&a.vertex_matches().len())
31//!     }
32//! }
33//!
34//! // Chain: fewer fragments first, then more vertices.
35//! let _ranker = FragmentCountRanker.then(MoreVerticesRanker);
36//! ```
37
38use alloc::{
39    collections::{BTreeMap, BTreeSet, VecDeque},
40    vec::Vec,
41};
42use core::cmp::Ordering;
43
44use super::vertex_match_inference::infer_vertex_matches;
45
46/// A matched edge pair: `((src1, dst1), (src2, dst2))` from two graphs.
47pub type MatchedEdgePair<N> = ((N, N), (N, N));
48
49/// Trait for accessing precomputed clique data used by rankers.
50///
51/// Implementors provide matched edges, vertex matches, and fragment
52/// structure. All data is expected to be precomputed at construction.
53pub trait CliqueInfo {
54    /// Node ID type (same for both graphs).
55    type NodeId: Eq + Copy + Ord + core::fmt::Debug;
56
57    /// The clique vertex indices (into the modular product).
58    fn clique(&self) -> &[usize];
59
60    /// Matched edge pairs: `((src1, dst1), (src2, dst2))` from the
61    /// original graphs.
62    fn matched_edges(&self) -> &[MatchedEdgePair<Self::NodeId>];
63
64    /// Matched vertex pairs `(v1, v2)` inferred from edge matches.
65    fn vertex_matches(&self) -> &[(Self::NodeId, Self::NodeId)];
66
67    /// Number of connected components (fragments) in the matched edge
68    /// subgraph.
69    fn fragment_count(&self) -> usize;
70
71    /// Number of matched edges in the largest connected fragment.
72    fn largest_fragment_edge_count(&self) -> usize;
73
74    /// Number of matched vertices in the largest connected fragment.
75    fn largest_fragment_atom_count(&self) -> usize;
76
77    /// Legacy alias for the edge-based largest fragment size.
78    #[inline]
79    fn largest_fragment_size(&self) -> usize {
80        self.largest_fragment_edge_count()
81    }
82}
83
84/// Eagerly precomputed clique information.
85///
86/// Constructed from a maximum clique result, vertex pairs, edge maps, and
87/// a disambiguation closure. All fields are computed at construction time.
88#[derive(Clone, Debug, PartialEq, Eq, Hash)]
89pub struct EagerCliqueInfo<N> {
90    clique: Vec<usize>,
91    matched_edges: Vec<MatchedEdgePair<N>>,
92    vertex_matches: Vec<(N, N)>,
93    fragment_count: usize,
94    largest_fragment_edge_count: usize,
95    largest_fragment_atom_count: usize,
96}
97
98impl<N> EagerCliqueInfo<N>
99where
100    N: Eq + Copy + Ord + core::fmt::Debug,
101{
102    /// Constructs a new `EagerCliqueInfo` from MCES pipeline outputs.
103    ///
104    /// # Parameters
105    ///
106    /// - `clique` — vertex indices in the modular product (max clique result).
107    /// - `vertex_pairs` — from [`ModularProductResult::vertex_pairs()`], maps
108    ///   product vertex → `(lg1_vertex, lg2_vertex)`.
109    /// - `edge_map_first` — from [`LineGraphResult::edge_map()`] of the first
110    ///   graph.
111    /// - `edge_map_second` — same for the second graph.
112    /// - `disambiguate` — closure for isolated edge disambiguation (see
113    ///   [`infer_vertex_matches`]).
114    ///
115    /// [`ModularProductResult::vertex_pairs()`]: crate::traits::algorithms::modular_product::ModularProductResult::vertex_pairs
116    /// [`LineGraphResult::edge_map()`]: crate::traits::algorithms::line_graph::LineGraphResult::edge_map
117    #[must_use]
118    pub fn new<F>(
119        clique: Vec<usize>,
120        vertex_pairs: &[(usize, usize)],
121        edge_map_first: &[(N, N)],
122        edge_map_second: &[(N, N)],
123        disambiguate: F,
124    ) -> Self
125    where
126        F: FnMut(N, N, N, N) -> bool,
127    {
128        // 1. Decode matched edges.
129        let matched_edges: Vec<MatchedEdgePair<N>> = clique
130            .iter()
131            .map(|&k| {
132                let (lg1, lg2) = vertex_pairs[k];
133                (edge_map_first[lg1], edge_map_second[lg2])
134            })
135            .collect();
136
137        // 2. Infer vertex matches.
138        let vertex_matches = infer_vertex_matches(
139            &clique,
140            vertex_pairs,
141            edge_map_first,
142            edge_map_second,
143            disambiguate,
144        );
145
146        // 3. Compute fragment structure from G1 edges.
147        let g1_edges: Vec<(N, N)> = matched_edges.iter().map(|&(e1, _)| e1).collect();
148        let (fragment_count, largest_fragment_edge_count, largest_fragment_atom_count) =
149            compute_fragments(&g1_edges);
150
151        Self {
152            clique,
153            matched_edges,
154            vertex_matches,
155            fragment_count,
156            largest_fragment_edge_count,
157            largest_fragment_atom_count,
158        }
159    }
160}
161
162impl<N> CliqueInfo for EagerCliqueInfo<N>
163where
164    N: Eq + Copy + Ord + core::fmt::Debug,
165{
166    type NodeId = N;
167
168    #[inline]
169    fn clique(&self) -> &[usize] {
170        &self.clique
171    }
172
173    #[inline]
174    fn matched_edges(&self) -> &[MatchedEdgePair<N>] {
175        &self.matched_edges
176    }
177
178    #[inline]
179    fn vertex_matches(&self) -> &[(N, N)] {
180        &self.vertex_matches
181    }
182
183    #[inline]
184    fn fragment_count(&self) -> usize {
185        self.fragment_count
186    }
187
188    #[inline]
189    fn largest_fragment_edge_count(&self) -> usize {
190        self.largest_fragment_edge_count
191    }
192
193    #[inline]
194    fn largest_fragment_atom_count(&self) -> usize {
195        self.largest_fragment_atom_count
196    }
197}
198
199/// Computes the number of connected components and the sizes of the largest
200/// component in an edge list.
201///
202/// Uses BFS on a `BTreeMap`-based adjacency list to support arbitrary
203/// (non-contiguous) node ID types.
204///
205/// Returns `(0, 0, 0)` for an empty edge list.
206fn compute_fragments<N: Eq + Copy + Ord>(edges: &[(N, N)]) -> (usize, usize, usize) {
207    if edges.is_empty() {
208        return (0, 0, 0);
209    }
210
211    // Build adjacency list.
212    let mut adj: BTreeMap<N, Vec<N>> = BTreeMap::new();
213    for &(u, v) in edges {
214        adj.entry(u).or_default().push(v);
215        adj.entry(v).or_default().push(u);
216    }
217
218    // BFS to find connected components.
219    let mut visited: BTreeSet<N> = BTreeSet::new();
220    let mut queue: VecDeque<N> = VecDeque::new();
221    let mut num_components = 0usize;
222    let mut largest_component_edges = 0usize;
223    let mut largest_component_vertices = 0usize;
224
225    for &start in adj.keys() {
226        if visited.contains(&start) {
227            continue;
228        }
229
230        // BFS from start.
231        visited.insert(start);
232        queue.push_back(start);
233        let mut component_vertices: Vec<N> = Vec::new();
234
235        while let Some(v) = queue.pop_front() {
236            component_vertices.push(v);
237            if let Some(neighbors) = adj.get(&v) {
238                for &u in neighbors {
239                    if visited.insert(u) {
240                        queue.push_back(u);
241                    }
242                }
243            }
244        }
245
246        // Count edges in this component: edges whose both endpoints are in
247        // this component. Since we built adjacency from the edge list, we
248        // can count by summing degrees / 2.
249        let component_set: BTreeSet<N> = component_vertices.iter().copied().collect();
250        let component_edges = edges
251            .iter()
252            .filter(|&&(u, v)| component_set.contains(&u) && component_set.contains(&v))
253            .count();
254
255        num_components += 1;
256        if component_edges > largest_component_edges {
257            largest_component_edges = component_edges;
258        }
259        if component_vertices.len() > largest_component_vertices {
260            largest_component_vertices = component_vertices.len();
261        }
262    }
263
264    (num_components, largest_component_edges, largest_component_vertices)
265}
266
267/// Trait for comparing two cliques to determine ranking order.
268///
269/// Composable via [`then`](CliqueRankerExt::then) into zero-cost
270/// [`ChainedRanker`] chains. The entire chain is monomorphized at
271/// compile time — no dynamic dispatch.
272pub trait CliqueRanker<I: CliqueInfo> {
273    /// Compares two cliques. Returns `Less` if `a` is better, `Greater`
274    /// if `b` is better, `Equal` if indistinguishable by this criterion.
275    fn compare(&self, a: &I, b: &I) -> Ordering;
276}
277
278/// Extension trait providing the `.then()` chain combinator.
279///
280/// Separate from [`CliqueRanker`] to avoid requiring the `I` type parameter
281/// at chain-construction time (it's only needed when `compare` is called).
282pub trait CliqueRankerExt: Sized {
283    /// Chains this ranker with another. The first ranker breaks ties first;
284    /// the second ranker is consulted only when the first returns `Equal`.
285    #[inline]
286    fn then<R>(self, other: R) -> ChainedRanker<Self, R> {
287        ChainedRanker { first: self, second: other }
288    }
289}
290
291impl<T> CliqueRankerExt for T {}
292
293/// A chained pair of rankers applied lexicographically.
294///
295/// Created by [`CliqueRankerExt::then`]. Fully monomorphized — the compiler
296/// inlines both comparisons.
297#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
298pub struct ChainedRanker<R1, R2> {
299    first: R1,
300    second: R2,
301}
302
303impl<I: CliqueInfo, R1: CliqueRanker<I>, R2: CliqueRanker<I>> CliqueRanker<I>
304    for ChainedRanker<R1, R2>
305{
306    #[inline]
307    fn compare(&self, a: &I, b: &I) -> Ordering {
308        self.first.compare(a, b).then_with(|| self.second.compare(a, b))
309    }
310}
311
312/// Ranks cliques by fragment count: fewer connected fragments is better.
313///
314/// This is the first tiebreaker in the RASCAL-style ranking (criterion 2).
315/// A single contiguous matched subgraph (1 fragment) is preferred over
316/// a scattered match with the same number of edges.
317#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
318pub struct FragmentCountRanker;
319
320impl<I: CliqueInfo> CliqueRanker<I> for FragmentCountRanker {
321    #[inline]
322    fn compare(&self, a: &I, b: &I) -> Ordering {
323        a.fragment_count().cmp(&b.fragment_count())
324    }
325}
326
327/// Ranks cliques by largest fragment size: larger is better.
328///
329/// This is the second tiebreaker in the RASCAL-style ranking (criterion 3).
330/// Among cliques with the same fragment count, prefer the one whose largest
331/// connected component contains more edges.
332#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
333pub struct LargestFragmentRanker;
334
335impl<I: CliqueInfo> CliqueRanker<I> for LargestFragmentRanker {
336    #[inline]
337    fn compare(&self, a: &I, b: &I) -> Ordering {
338        b.largest_fragment_edge_count().cmp(&a.largest_fragment_edge_count())
339    }
340}
341
342/// Fragment-size metric used by [`LargestFragmentMetricRanker`].
343#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
344pub enum LargestFragmentMetric {
345    /// Prefer the clique with more matched edges in its largest fragment.
346    Edges,
347    /// Prefer the clique with more matched vertices in its largest fragment.
348    Atoms,
349}
350
351/// Ranks cliques by largest fragment size using a selectable metric.
352#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
353pub struct LargestFragmentMetricRanker {
354    metric: LargestFragmentMetric,
355}
356
357impl LargestFragmentMetricRanker {
358    /// Creates a new metric-selectable largest-fragment ranker.
359    #[inline]
360    #[must_use]
361    pub const fn new(metric: LargestFragmentMetric) -> Self {
362        Self { metric }
363    }
364}
365
366impl Default for LargestFragmentMetricRanker {
367    #[inline]
368    fn default() -> Self {
369        Self::new(LargestFragmentMetric::Edges)
370    }
371}
372
373impl<I: CliqueInfo> CliqueRanker<I> for LargestFragmentMetricRanker {
374    #[inline]
375    fn compare(&self, a: &I, b: &I) -> Ordering {
376        match self.metric {
377            LargestFragmentMetric::Edges => {
378                b.largest_fragment_edge_count().cmp(&a.largest_fragment_edge_count())
379            }
380            LargestFragmentMetric::Atoms => {
381                b.largest_fragment_atom_count().cmp(&a.largest_fragment_atom_count())
382            }
383        }
384    }
385}
386
387/// Ranks cliques using a user-provided comparison closure.
388///
389/// This is the escape hatch for any custom ranking logic: edge weight costs,
390/// domain-specific scoring, or any criterion not covered by the built-in
391/// rankers.
392///
393/// # Example
394///
395/// ```
396/// use core::cmp::Ordering;
397///
398/// use geometric_traits::prelude::*;
399///
400/// // Prefer cliques with more vertex matches.
401/// let _ranker = FnRanker::new(|a: &EagerCliqueInfo<u32>, b: &EagerCliqueInfo<u32>| {
402///     b.vertex_matches().len().cmp(&a.vertex_matches().len())
403/// });
404/// ```
405pub struct FnRanker<F> {
406    compare_fn: F,
407}
408
409impl<F> FnRanker<F> {
410    /// Creates a new `FnRanker` from a comparison closure.
411    #[inline]
412    #[must_use]
413    pub fn new(compare_fn: F) -> Self {
414        Self { compare_fn }
415    }
416}
417
418impl<I: CliqueInfo, F: Fn(&I, &I) -> Ordering> CliqueRanker<I> for FnRanker<F> {
419    #[inline]
420    fn compare(&self, a: &I, b: &I) -> Ordering {
421        (self.compare_fn)(a, b)
422    }
423}
424
425#[cfg(test)]
426mod tests {
427    use super::*;
428
429    #[test]
430    fn test_compute_fragments_empty() {
431        let (count, largest_edges, largest_atoms) = compute_fragments::<u32>(&[]);
432        assert_eq!(count, 0);
433        assert_eq!(largest_edges, 0);
434        assert_eq!(largest_atoms, 0);
435    }
436
437    #[test]
438    fn test_compute_fragments_single_edge() {
439        let (count, largest_edges, largest_atoms) = compute_fragments(&[(0u32, 1)]);
440        assert_eq!(count, 1);
441        assert_eq!(largest_edges, 1);
442        assert_eq!(largest_atoms, 2);
443    }
444
445    #[test]
446    fn test_compute_fragments_path() {
447        // Path: 0-1-2-3 → 1 component, 3 edges.
448        let (count, largest_edges, largest_atoms) = compute_fragments(&[(0u32, 1), (1, 2), (2, 3)]);
449        assert_eq!(count, 1);
450        assert_eq!(largest_edges, 3);
451        assert_eq!(largest_atoms, 4);
452    }
453
454    #[test]
455    fn test_compute_fragments_two_disjoint() {
456        // Two disjoint edges: (0,1) and (5,6) → 2 components, 1 edge each.
457        let (count, largest_edges, largest_atoms) = compute_fragments(&[(0u32, 1), (5, 6)]);
458        assert_eq!(count, 2);
459        assert_eq!(largest_edges, 1);
460        assert_eq!(largest_atoms, 2);
461    }
462
463    #[test]
464    fn test_compute_fragments_uneven() {
465        // Path (0,1,2) + isolated edge (5,6) → 2 components, largest has 2
466        // edges.
467        let (count, largest_edges, largest_atoms) = compute_fragments(&[(0u32, 1), (1, 2), (5, 6)]);
468        assert_eq!(count, 2);
469        assert_eq!(largest_edges, 2);
470        assert_eq!(largest_atoms, 3);
471    }
472
473    #[test]
474    fn test_compute_fragments_triangle() {
475        let (count, largest_edges, largest_atoms) = compute_fragments(&[(0u32, 1), (1, 2), (0, 2)]);
476        assert_eq!(count, 1);
477        assert_eq!(largest_edges, 3);
478        assert_eq!(largest_atoms, 3);
479    }
480}
geometric_traits/traits/algorithms/clique_ranking.rs

geometric_traits/traits/algorithms/
clique_ranking.rs
