hypergraph 1.3.9

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

#![deny(unsafe_code, nonstandard_style)]
#![forbid(rust_2021_compatibility)]

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"
    );
}