hypergraph 3.0.0

Hypergraph is data structure library to create a directed hypergraph in which an hyperedge can join any number of vertices.
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! Integration tests.

mod common;

use common::{
    Hyperedge,
    Vertex,
};
use hypergraph::Hypergraph;

#[test]
fn integration_dijkstra() {
    // Create a new hypergraph.
    let mut graph = Hypergraph::<Vertex, Hyperedge>::new();

    // Create some vertice weights.
    let vertex_one = Vertex::new("one");
    let vertex_two = Vertex::new("two");
    let vertex_three = Vertex::new("three");
    let vertex_four = Vertex::new("four");
    let vertex_five = Vertex::new("five");

    // Create some hyperedge weights.
    let hyperedge_one = Hyperedge::new("one", 10);
    let hyperedge_two = Hyperedge::new("two", 20);
    let hyperedge_three = Hyperedge::new("three", 1);
    let hyperedge_four = Hyperedge::new("four", 100);

    // Create some vertices.
    let a = graph.add_vertex(vertex_one).unwrap();
    let b = graph.add_vertex(vertex_two).unwrap();
    let c = graph.add_vertex(vertex_three).unwrap();
    let d = graph.add_vertex(vertex_four).unwrap();
    let e = graph.add_vertex(vertex_five).unwrap();

    // Create some hyperedges.
    // ---------------------------------
    //                 alpha
    //         ┌-----------------------┐
    //  alpha  |  gamma      gamma     |
    // ┌-----┐ | ┌-----┐ ┌-----------┐ |
    // |     | | |     | |           | |
    // |     v | |     v |           v v
    // ┌-┐   ┌---┐     ┌-┐    ┌-┐    ┌-┐
    // |a|   | b |     |c|    |d|    |e|
    // └-┘   └---┘     └-┘    └-┘    └-┘
    // |     ^ | |            ^ ^    | ^
    // |     | | |            | |    | |
    // |     | | |    delta   | └----┘ |
    // |     | | └------------┘  beta  |
    // └-----┘ └-----------------------┘
    //   beta            beta
    // ---------------------------------
    let alpha = graph.add_hyperedge(vec![a, b, e], hyperedge_one).unwrap();
    let beta = graph
        .add_hyperedge(vec![a, b, e, d], hyperedge_two)
        .unwrap();
    let gamma = graph.add_hyperedge(vec![b, c, e], hyperedge_three).unwrap();
    let _delta = graph.add_hyperedge(vec![b, d], hyperedge_four).unwrap();

    // Get the cheapest path via Dijkstra based on the hyperedges' costs.
    assert_eq!(
        graph.get_dijkstra_connections(a, d),
        Ok(vec![
            (a, None),
            (b, Some(alpha)),
            (c, Some(gamma)),
            (e, Some(gamma)),
            (d, Some(beta))
        ]),
        "should follow a, b, c, e, d with their matching traversed hyperedges"
    );
}

#[test]
fn integration_dijkstra_parallel_hyperedges() {
    // Regression test: with multiple hyperedges between the same two vertices,
    // Dijkstra must pick the cheapest one, not merely the first.
    let mut graph = Hypergraph::<Vertex, Hyperedge>::new();

    let s = graph.add_vertex(Vertex::new("s")).unwrap();
    let t = graph.add_vertex(Vertex::new("t")).unwrap();

    // Insert the expensive hyperedge first so it appears first in iteration order.
    let _expensive = graph
        .add_hyperedge(vec![s, t], Hyperedge::new("expensive", 10))
        .unwrap();
    let cheap = graph
        .add_hyperedge(vec![s, t], Hyperedge::new("cheap", 1))
        .unwrap();

    assert_eq!(
        graph.get_dijkstra_connections(s, t),
        Ok(vec![(s, None), (t, Some(cheap))]),
        "should use the cheaper parallel hyperedge"
    );
}

#[test]
fn integration_dijkstra_dead_end_branch() {
    // Regression test: vertices explored in dead-end branches must not appear
    // in the returned path.
    let mut graph = Hypergraph::<Vertex, Hyperedge>::new();

    let s = graph.add_vertex(Vertex::new("s")).unwrap();
    let a = graph.add_vertex(Vertex::new("a")).unwrap(); // dead-end branch
    let b = graph.add_vertex(Vertex::new("b")).unwrap();
    let c = graph.add_vertex(Vertex::new("c")).unwrap(); // unreachable from b to t
    let t = graph.add_vertex(Vertex::new("t")).unwrap();

    // s→a is cheap but a only leads to c, which is a dead end.
    let _he_sa = graph
        .add_hyperedge(vec![s, a], Hyperedge::new("s-a", 1))
        .unwrap();
    let _he_ac = graph
        .add_hyperedge(vec![a, c], Hyperedge::new("a-c", 1))
        .unwrap();

    // s→b→t is the only route to t.
    let he_sb = graph
        .add_hyperedge(vec![s, b], Hyperedge::new("s-b", 2))
        .unwrap();
    let he_bt = graph
        .add_hyperedge(vec![b, t], Hyperedge::new("b-t", 1))
        .unwrap();

    assert_eq!(
        graph.get_dijkstra_connections(s, t),
        Ok(vec![(s, None), (b, Some(he_sb)), (t, Some(he_bt))]),
        "dead-end vertex a should not appear in the path"
    );
}