Spaces:
Sleeping
Sleeping
File size: 3,666 Bytes
214f910 | 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 | from __future__ import annotations
import heapq
from typing import Dict, List, Tuple
from .data_loader import load_edges
def _build_graph() -> Dict[str, List[Tuple[str, int]]]:
graph: Dict[str, List[Tuple[str, int]]] = {}
for edge in load_edges():
a = edge["from"]
b = edge["to"]
d = int(edge["distance_m"])
graph.setdefault(a, []).append((b, d))
graph.setdefault(b, []).append((a, d))
return graph
GRAPH_CACHE: Dict[str, List[Tuple[str, int]]] | None = None
def get_graph() -> Dict[str, List[Tuple[str, int]]]:
global GRAPH_CACHE
if GRAPH_CACHE is None:
GRAPH_CACHE = _build_graph()
return GRAPH_CACHE
def shortest_path_distance(start: str, goal: str) -> int:
if start == goal:
return 0
graph = get_graph()
dist: Dict[str, int] = {start: 0}
pq: List[Tuple[int, str]] = [(0, start)]
while pq:
cur_dist, node = heapq.heappop(pq)
if node == goal:
return cur_dist
if cur_dist > dist.get(node, float("inf")):
continue
for neighbor, weight in graph.get(node, []):
nd = cur_dist + weight
if nd < dist.get(neighbor, float("inf")):
dist[neighbor] = nd
heapq.heappush(pq, (nd, neighbor))
return 0
def order_by_nearest_neighbor(
attraction_ids: List[str],
node_lookup: Dict[str, str],
start_node: str = "HUB",
) -> List[str]:
"""Order attractions by geography: nearest-neighbor from start_node to minimize walking."""
current = start_node
to_visit = [a for a in attraction_ids if node_lookup.get(a)]
ordered: List[str] = []
while to_visit:
best_id: str | None = None
best_dist = float("inf")
for aid in to_visit:
node = node_lookup[aid]
d = shortest_path_distance(current, node)
if d < best_dist:
best_dist = d
best_id = aid
if best_id is None:
break
ordered.append(best_id)
to_visit.remove(best_id)
current = node_lookup[best_id]
return ordered
def greedy_schedule(
attractions_order: List[str],
start_time_minutes: int,
walking_weight: float,
wait_time_lookup: Dict[str, int],
node_lookup: Dict[str, str],
) -> Tuple[List[Dict], int, int]:
from .data_loader import walking_distance_between, load_attractions
attractions = load_attractions()
current_node = "HUB"
current_time = start_time_minutes
total_wait = 0
total_walk = 0
stops: List[Dict] = []
for attr_id in attractions_order:
attr = attractions[attr_id]
target_node = node_lookup[attr_id]
walk = walking_distance_between(current_node, target_node)
wait = wait_time_lookup.get(attr_id, 10)
total_walk += walk
total_wait += wait
start_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}"
current_time += walk // 80
current_time += wait
end_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}"
stops.append(
{
"attraction_id": attr.id,
"attraction_name": attr.name,
"node_id": attr.node_id,
"start_time": start_time_str,
"end_time": end_time_str,
"estimated_wait_minutes": wait,
"walking_distance_m": walk,
}
)
current_node = target_node
return stops, total_wait, total_walk
|