open_hypergraphs/strict/
layer.rs

1//! A [Coffman-Graham](https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm)-inspired
2//! layering algorithm.
3use crate::array::*;
4use crate::finite_function::*;
5
6use crate::strict::graph;
7use crate::strict::graph::converse_iter;
8use crate::strict::open_hypergraph::*;
9
10/// Compute a *layering* of an [`OpenHypergraph`]: a mapping `layer : X → K` from operations to
11/// integers compatible with the partial ordering on `X` induced by hypergraph structure.
12///
13/// See also: the [Coffman-Graham Algorithm](https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm)
14///
15/// # Returns
16///
17/// - A finite function `layer : X → L` assigning a *layer* to each operation in the set `X`
18/// - An array of *flags* for each operation determining if it was visited in the layering. If any
19///   operation was unvisited, the hypergraph was not monogamous acyclic.
20pub fn layer<K: ArrayKind, O, A>(f: &OpenHypergraph<K, O, A>) -> (FiniteFunction<K>, K::Type<K::I>)
21where
22    K::Type<A>: Array<K, A>,
23    K::Type<K::I>: NaturalArray<K>,
24{
25    let a = graph::operation_adjacency(&f.h);
26    let (ordering, completed) = graph::kahn(&a);
27    (
28        FiniteFunction::new(ordering, f.h.x.0.len()).unwrap(),
29        completed,
30    )
31}
32
33/// Given an [`OpenHypergraph`], compute a layering of its operations as a finite function `X → L`,
34/// then return this as an array-of-arrays `r`.
35///
36/// # Returns
37///
38/// - A `Vec` of arrays `r`, where `r[i]` is the array of operations in layer `i`.
39/// - An array of unvisited nodes, as in [`layer`]
40pub fn layered_operations<K: ArrayKind, O, A>(
41    f: &OpenHypergraph<K, O, A>,
42) -> (Vec<K::Index>, K::Index)
43where
44    K::Type<A>: Array<K, A>,
45    K::Type<K::I>: NaturalArray<K>,
46    K::I: Into<usize>,
47{
48    let (order, unvisited) = layer(f);
49    (converse_iter(order).collect(), unvisited.into())
50}
open_hypergraphs/strict/layer.rs

open_hypergraphs/strict/
layer.rs
