osmgraphing 0.4.0

Playing around with graphs created via parsing OpenStreetMap data
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
133
134
135
136
137

use std::borrow::Cow;
use std::cmp::Ordering;
use std::collections::BinaryHeap;

use crate::network::{Edge, Graph};

//------------------------------------------------------------------------------------------------//
// nodes

#[derive(Copy, Clone)]
struct CostNode {
    pub idx: usize,
    pub cost: u32,
}

impl Ord for CostNode {
    fn cmp(&self, other: &CostNode) -> Ordering {
        // (1) cost in float, but cmp uses only m, which is ok
        // (2) inverse order since BinaryHeap is max-heap, but min-heap is needed
        other
            .cost
            .cmp(&self.cost)
            .then_with(|| other.idx.cmp(&self.idx))
    }
}

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

impl Eq for CostNode {}

impl PartialEq for CostNode {
    fn eq(&self, other: &CostNode) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

//------------------------------------------------------------------------------------------------//
// Dijkstra's type of path

#[derive(Clone)]
pub struct Path<'a> {
    pub cost: Vec<u32>,
    pub predecessors: Vec<Option<&'a Edge>>,
}

//------------------------------------------------------------------------------------------------//
// Dijkstra

pub struct Dijkstra<'a> {
    pub graph: &'a Graph,
    pub path: Path<'a>,
}

impl<'a> Dijkstra<'a> {
    pub fn new(graph: &'a Graph) -> Dijkstra {
        Dijkstra {
            graph,
            path: Path {
                cost: vec![std::u32::MAX; graph.node_count()],
                predecessors: vec![None; graph.node_count()],
            },
        }
    }
}

impl<'a> Dijkstra<'a> {
    pub fn compute_shortest_path(&mut self, src_idx: usize, dst_idx: usize) -> Cow<Path> {
        //----------------------------------------------------------------------------------------//
        // initialize, but check path-"cache" before

        self.path.cost = vec![std::u32::MAX; self.graph.node_count()];
        self.path.predecessors = vec![None; self.graph.node_count()];
        let mut queue = BinaryHeap::new(); // max-heap, but CostNode's natural order is reversed

        // prepare first iteration
        queue.push(CostNode {
            idx: src_idx,
            cost: 0,
        });
        self.path.cost[src_idx] = 0;

        //----------------------------------------------------------------------------------------//
        // compute

        while let Some(CostNode { idx, cost }) = queue.pop() {
            // shortest path found
            if idx == dst_idx {
                break;
            }

            // if node has already been visited
            if cost > self.path.cost[idx] {
                continue;
            }

            if let Some(leaving_edges) = self.graph.leaving_edges(idx) {
                // if not -> update "official" cost
                // and add successors
                for edge in leaving_edges {
                    let new_cost = cost + edge.meters();

                    if new_cost < self.path.cost[edge.dst_idx()] {
                        self.path.predecessors[edge.dst_idx()] = Some(&edge);
                        self.path.cost[edge.dst_idx()] = new_cost;
                        queue.push(CostNode {
                            idx: edge.dst_idx(),
                            cost: new_cost,
                        });
                    }
                }
            }
        }

        Cow::Borrowed(&self.path)
    }

    // TODO
    // pub fn get_path(&mut self, src: usize, dst: usize) -> std::vec::Vec<usize> {
    //     if src >= self.graph.node_count() || dst >= self.graph.node_count() {
    //         let result = vec![];
    //         result
    //     } else {
    //         let mut shortest_path = Vec::new();
    //         let mut current_predec = dst;
    //         while current_predec != src {
    //             let edge = self.graph.edge(self.path.predecessors[current_predec]);
    //             shortest_path.push(edge.id);
    //             current_predec = edge.src;
    //         }
    //         shortest_path
    //     }
    // }
}