open-hypergraphs 0.3.1

Data-Parallel Algorithms for Open Hypergraphs
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

use open_hypergraphs::array::vec::*;
use open_hypergraphs::finite_function::FiniteFunction;
use open_hypergraphs::lax::{Hyperedge, Hypergraph as LaxHypergraph, NodeId};
use open_hypergraphs::strict::hypergraph::arrow::{HypergraphArrow, InvalidHypergraphArrow};
use open_hypergraphs::strict::hypergraph::Hypergraph;

type Obj = usize;
type Arr = usize;

fn build_hypergraph(
    node_labels: Vec<usize>,
    edges: &[(usize, Vec<usize>, Vec<usize>)],
) -> Hypergraph<VecKind, Obj, Arr> {
    let mut h = LaxHypergraph::empty();
    h.nodes = node_labels;
    for (label, sources, targets) in edges {
        let edge = Hyperedge {
            sources: sources.iter().map(|&i| NodeId(i)).collect(),
            targets: targets.iter().map(|&i| NodeId(i)).collect(),
        };
        h.new_edge(*label, edge);
    }
    h.to_hypergraph()
}

fn ff(table: Vec<usize>, target: usize) -> FiniteFunction<VecKind> {
    FiniteFunction::new(VecArray(table), target).unwrap()
}

#[test]
fn test_validate_rejects_non_natural_w() {
    let source = build_hypergraph(vec![0], &[]);
    let target = build_hypergraph(vec![1], &[]);
    let w = ff(vec![0], 1);
    let x = ff(vec![], 0);
    let err = HypergraphArrow::new(source, target, w, x).unwrap_err();
    assert!(matches!(err, InvalidHypergraphArrow::NotNaturalW));
}

#[test]
fn test_validate_rejects_non_natural_x() {
    let source = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);
    let target = build_hypergraph(vec![0, 0], &[(1, vec![0], vec![1])]);
    let w = ff(vec![0, 1], 2);
    let x = ff(vec![0], 1);
    let err = HypergraphArrow::new(source, target, w, x).unwrap_err();
    assert!(matches!(err, InvalidHypergraphArrow::NotNaturalX));
}

#[test]
fn test_validate_rejects_undefined_w_composition() {
    let source = build_hypergraph(vec![0], &[]);
    let target = build_hypergraph(vec![0], &[]);
    // valid finite function, but codomain size (2) does not match h.w.len() (1),
    // so w ; h.w is undefined and validate should return TypeMismatchW.
    let w = ff(vec![0], 2);
    let x = ff(vec![], 0);
    let err = HypergraphArrow::new(source, target, w, x).unwrap_err();
    assert!(matches!(err, InvalidHypergraphArrow::TypeMismatchW));
}

#[test]
fn test_validate_accepts_incidence_natural_arrow() {
    let source = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);
    let target = build_hypergraph(vec![0, 0], &[(0, vec![1], vec![1])]);

    let w = ff(vec![1, 1], 2);
    let x = ff(vec![0], 1);
    assert!(HypergraphArrow::new(source, target, w, x).is_ok());
}

#[test]
fn test_validate_rejects_non_natural_s() {
    let source = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);
    let target = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);

    let w = ff(vec![1, 1], 2);
    let x = ff(vec![0], 1);
    let err = HypergraphArrow::new(source, target, w, x).unwrap_err();
    assert!(matches!(err, InvalidHypergraphArrow::NotNaturalS));
}

#[test]
fn test_validate_rejects_non_natural_t() {
    let source = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);
    let target = build_hypergraph(vec![0, 0], &[(0, vec![0], vec![1])]);

    let w = ff(vec![0, 0], 2);
    let x = ff(vec![0], 1);
    let err = HypergraphArrow::new(source, target, w, x).unwrap_err();
    assert!(matches!(err, InvalidHypergraphArrow::NotNaturalT));
}