goatd 0.1.1

Greatest Of All Tree Decompositions: tree decompositions of graphs — elimination orders, FlowCutter, multilevel bisection — with PACE .gr/.td I/O and a command-line solver.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//! Elimination-order choices.

/// Which elimination order to run after preprocessing.
///
/// The two sampling orders carry one weight per graph vertex. Within a set of
/// vertices tied on fill or degree, a smaller weight makes a vertex more likely
/// to be drawn and therefore eliminated earlier. Equal weights give uniform
/// sampling.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Order<'a> {
    /// Preprocess, then repeatedly eliminate a minimum-fill vertex.
    MinFill,
    /// Preprocess, then repeatedly eliminate a minimum-degree vertex.
    MinDegree,
    /// Preprocess, then recursively bisect the graph and eliminate each
    /// separator after its two sides.
    NestedDissection,
    /// Min-fill with weighted sampling from the full minimum-fill tie set.
    MinFillSampled {
        /// Per-vertex weights, one entry per input graph vertex.
        weights: &'a [u32],
    },
    /// Min-degree with weighted sampling from the full minimum-degree tie set.
    MinDegreeSampled {
        /// Per-vertex weights, one entry per input graph vertex.
        weights: &'a [u32],
    },
}

impl<'a> Order<'a> {
    /// The sampling weights carried by this order, if any.
    pub(super) fn tie_weights(self) -> Option<&'a [u32]> {
        match self {
            Order::MinFillSampled { weights } | Order::MinDegreeSampled { weights } => {
                Some(weights)
            }
            Order::MinFill | Order::MinDegree | Order::NestedDissection => None,
        }
    }

    /// Replace the sampling weights after a graph has been reindexed.
    pub(super) fn with_tie_weights<'b>(self, weights: &'b [u32]) -> Order<'b> {
        match self {
            Order::MinFill => Order::MinFill,
            Order::MinDegree => Order::MinDegree,
            Order::NestedDissection => Order::NestedDissection,
            Order::MinFillSampled { .. } => Order::MinFillSampled { weights },
            Order::MinDegreeSampled { .. } => Order::MinDegreeSampled { weights },
        }
    }

    /// Whether repeated runs can reuse the residual's initial fill counts.
    pub(super) fn uses_initial_fill_cache(self) -> bool {
        matches!(self, Order::MinFillSampled { .. })
    }
}