gryf 0.2.1

Graph data structure library with focus on convenience, versatility, correctness and performance.
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

use std::iter;

use gryf::{
    core::{
        GraphBase, Neighbors,
        base::NeighborReference,
        borrow::OwnableRef,
        id::{EdgeId, IdType, VertexId},
        marker::{Directed, Direction},
    },
    visit::{Visitor, dfs::Dfs},
};

// https://stackoverflow.com/questions/58870416/can-you-explain-implicit-graphsin-graph-theory-with-a-simple-example/58887179#58887179
struct Collatz;

fn to_vertex(n: u64) -> VertexId {
    VertexId::from_bits(n)
}

fn to_num(v: VertexId) -> u64 {
    v.as_bits()
}

struct Neighbor {
    pred: VertexId,
}

impl NeighborReference<VertexId, EdgeId> for Neighbor {
    fn id(&self) -> OwnableRef<'_, VertexId> {
        let n = self.pred.as_bits();
        let c = if n.is_multiple_of(2) {
            n / 2
        } else {
            3 * n + 1
        };
        OwnableRef::Owned(to_vertex(c))
    }

    fn edge(&self) -> OwnableRef<'_, EdgeId> {
        OwnableRef::Owned(EdgeId::from_bits(self.pred.as_bits()))
    }

    fn pred(&self) -> OwnableRef<'_, VertexId> {
        self.pred.into()
    }

    fn dir(&self) -> Direction {
        Direction::Outgoing
    }
}

impl GraphBase for Collatz {
    type VertexId = VertexId;
    type EdgeId = EdgeId;
    type EdgeType = Directed;
}

impl Neighbors for Collatz {
    type NeighborRef<'a> = Neighbor;

    type NeighborsIter<'a>
        = iter::Once<Self::NeighborRef<'a>>
    where
        Self: 'a;

    fn neighbors_undirected(&self, from: &VertexId) -> Self::NeighborsIter<'_> {
        iter::once(Neighbor { pred: *from })
    }

    fn neighbors_directed(&self, from: &VertexId, dir: Direction) -> Self::NeighborsIter<'_> {
        assert_eq!(dir, Direction::Outgoing, "incoming edges are not available");
        iter::once(Neighbor { pred: *from })
    }
}

fn main() {
    let collatz = Collatz;

    let sequence = Dfs::new(&collatz)
        .start(to_vertex(9))
        .iter(&collatz)
        .map(to_num)
        .collect::<Vec<_>>();
    println!("A Collatz sequence: {sequence:?}");
}