map_model/connectivity/
mod.rs

Help
1// TODO Possibly these should be methods on Map.
2
3use serde::{Deserialize, Serialize};
4use std::collections::{BinaryHeap, HashMap, HashSet};
5
6use petgraph::graphmap::DiGraphMap;
7
8use abstutil::PriorityQueueItem;
9use geom::Duration;
10
11pub use self::walking::{all_walking_costs_from, WalkingOptions};
12pub use crate::pathfind::{vehicle_cost, WalkingNode};
13use crate::{BuildingID, DirectedRoadID, IntersectionID, LaneID, Map, PathConstraints};
14
15mod walking;
16
17#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, PartialOrd, Ord, Serialize, Deserialize)]
18pub enum Spot {
19    Building(BuildingID),
20    Border(IntersectionID),
21    DirectedRoad(DirectedRoadID),
22}
23
24/// Calculate the strongly connected components (SCC) of the part of the map accessible by
25/// constraints (ie, the graph of sidewalks or driving+bike lanes). The largest component is the
26/// "main" graph; the rest is disconnected. Returns (lanes in the largest "main" component, all
27/// other disconnected lanes)
28pub fn find_scc(map: &Map, constraints: PathConstraints) -> (HashSet<LaneID>, HashSet<LaneID>) {
29    let mut graph = DiGraphMap::new();
30    for turn in map.all_turns() {
31        if constraints.can_use(map.get_l(turn.id.src), map)
32            && constraints.can_use(map.get_l(turn.id.dst), map)
33        {
34            graph.add_edge(turn.id.src, turn.id.dst, 1);
35        }
36    }
37    let components = petgraph::algo::kosaraju_scc(&graph);
38    if components.is_empty() {
39        return (HashSet::new(), HashSet::new());
40    }
41    let largest_group: HashSet<LaneID> = components
42        .into_iter()
43        .max_by_key(|c| c.len())
44        .unwrap()
45        .into_iter()
46        .collect();
47    let disconnected = map
48        .all_lanes()
49        .filter_map(|l| {
50            if constraints.can_use(l, map) && !largest_group.contains(&l.id) {
51                Some(l.id)
52            } else {
53                None
54            }
55        })
56        .collect();
57    (largest_group, disconnected)
58}
59
60/// Starting from some initial spot, calculate the cost to all buildings. If a destination isn't
61/// reachable, it won't be included in the results. Ignore results greater than the time_limit
62/// away.
63pub fn all_vehicle_costs_from(
64    map: &Map,
65    starts: Vec<Spot>,
66    time_limit: Duration,
67    constraints: PathConstraints,
68) -> HashMap<BuildingID, Duration> {
69    assert!(constraints != PathConstraints::Pedestrian);
70    // TODO We have a graph of DirectedRoadIDs, but mapping a building to one isn't
71    // straightforward. In the common case it'll be fine, but some buildings are isolated from the
72    // graph by some sidewalks.
73
74    let mut bldg_to_road = HashMap::new();
75    for b in map.all_buildings() {
76        if constraints == PathConstraints::Car {
77            if let Some((pos, _)) = b.driving_connection(map) {
78                bldg_to_road.insert(b.id, map.get_l(pos.lane()).get_directed_parent());
79            }
80        } else if constraints == PathConstraints::Bike {
81            if let Some((pos, _)) = b.biking_connection(map) {
82                bldg_to_road.insert(b.id, map.get_l(pos.lane()).get_directed_parent());
83            }
84        }
85    }
86
87    let mut queue: BinaryHeap<PriorityQueueItem<Duration, DirectedRoadID>> = BinaryHeap::new();
88
89    for spot in starts {
90        match spot {
91            Spot::Building(b_id) => {
92                if let Some(start_road) = bldg_to_road.get(&b_id).cloned() {
93                    queue.push(PriorityQueueItem {
94                        cost: Duration::ZERO,
95                        value: start_road,
96                    });
97                }
98            }
99            Spot::Border(i_id) => {
100                let intersection = map.get_i(i_id);
101
102                let incoming_lanes = intersection.get_incoming_lanes(map, constraints);
103                let mut outgoing_lanes = intersection.get_outgoing_lanes(map, constraints);
104                let mut all_lanes = incoming_lanes;
105                all_lanes.append(&mut outgoing_lanes);
106
107                for l_id in all_lanes {
108                    queue.push(PriorityQueueItem {
109                        cost: Duration::ZERO,
110                        value: map.get_l(l_id).get_directed_parent(),
111                    });
112                }
113            }
114            Spot::DirectedRoad(dr) => {
115                queue.push(PriorityQueueItem {
116                    cost: Duration::ZERO,
117                    value: dr,
118                });
119            }
120        }
121    }
122
123    let mut cost_per_node: HashMap<DirectedRoadID, Duration> = HashMap::new();
124    while let Some(current) = queue.pop() {
125        if cost_per_node.contains_key(&current.value) {
126            continue;
127        }
128        if current.cost > time_limit {
129            continue;
130        }
131        cost_per_node.insert(current.value, current.cost);
132
133        for mvmnt in map.get_movements_for(current.value, constraints) {
134            if let Some(cost) =
135                vehicle_cost(mvmnt.from, mvmnt, constraints, map.routing_params(), map)
136            {
137                queue.push(PriorityQueueItem {
138                    cost: current.cost + cost,
139                    value: mvmnt.to,
140                });
141            }
142        }
143    }
144
145    let mut results = HashMap::new();
146    for (b, road) in bldg_to_road {
147        if let Some(duration) = cost_per_node.get(&road).cloned() {
148            results.insert(b, duration);
149        }
150    }
151    results
152}
map_model/connectivity/mod.rs

map_model/connectivity/
mod.rs
