sinistra 0.1.0-202603071957

A generic graph framework with pluggable storage and topology and streaming graph algorithms.
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

use std::{collections::HashMap, f64, ops::Add};

use sinistra::graph::{
    BasicGraph, DijkstraEvent, Graph, GraphEdgesMutExt, GraphVertexSetMutExt, HashMapStorage,
    HashMapTopology, VertexHandle, Weight, Weighted, dijkstra,
};

fn main() {
    let storage = HashMapStorage::<City, Distance>::new();
    let topology = HashMapTopology::new();
    let mut graph = BasicGraph::new(storage, topology);

    let istanbul = graph.add_vertex(City::İstanbul);
    let ankara = graph.add_vertex(City::Ankara);
    let izmir = graph.add_vertex(City::İzmir);
    let ordu = graph.add_vertex(City::Ordu);
    let canakkale = graph.add_vertex(City::Çanakkale);

    graph.add_edge(Distance(450.0), istanbul, ankara);
    graph.add_edge(Distance(330.0), istanbul, izmir);
    graph.add_edge(Distance(380.0), ankara, izmir);
    graph.add_edge(Distance(190.0), ankara, ordu);
    graph.add_edge(Distance(300.0), ankara, canakkale);
    graph.add_edge(Distance(250.0), izmir, canakkale);
    graph.add_edge(Distance(350.0), izmir, ordu);
    graph.add_edge(Distance(200.0), ordu, canakkale);
    graph.add_edge(Distance(400.0), canakkale, ordu);

    println!("Cities:\n");
    for v in graph.vertices() {
        let city = graph.vertex(v).unwrap();
        println!("{:?} (v{})", city, v.index());
    }
    println!("\nRunning Dijkstra from İstanbul...\n");
    let mut distances: HashMap<VertexHandle, Distance> = HashMap::new();
    for event in dijkstra::<_, Distance>(&graph, istanbul) {
        if let DijkstraEvent::RelaxEdge { target, weight, .. } = event {
            distances.insert(target, weight);
        }
    }
    println!("Shortest distances:\n");
    println!("İstanbul: 0 km");
    for (v, d) in distances {
        let city = graph.vertex(v).unwrap();
        println!("{:?}: {:.1} km", city, d.0);
    }
}

#[derive(Debug)]
enum City {
    İstanbul,
    Ankara,
    İzmir,
    Ordu,
    Çanakkale,
}

// Unit: KM
#[derive(Debug, Clone, Copy)]
struct Distance(f64);

impl Add for Distance {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Distance(self.0 + rhs.0)
    }
}

impl Default for Distance {
    fn default() -> Self {
        Distance(0.0)
    }
}

impl Weight for Distance {
    fn infinity() -> Self {
        Distance(f64::INFINITY)
    }
}

impl Ord for Distance {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

impl PartialOrd for Distance {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Eq for Distance {}

impl PartialEq for Distance {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl Weighted for Distance {
    type Weight = Distance;

    fn weight(&self) -> Self::Weight {
        *self
    }
}