Skip to content

mamut_routing_tools.generation.matrices

Distance/time/euclidean matrices for a set of instance vertices, plus the depot-edge road geometry the workbench meta files embed.

Shortest = metres, fastest = seconds (3.6 * metres / km-per-hour class speed), both ceil'd to int, exactly like the Julia workbench. Matrix rows are computed with scipy's C Dijkstra over the road graph in CSR form.

metric_csr 

metric_csr(graph: RoadGraph, metric: str) -> csr_matrix

The road graph as a CSR weight matrix under one metric.

shortest weights are edge lengths in metres, fastest are free-flow traversal times in seconds. Public because the campaign city profiler runs its own partial Dijkstras over exactly these weights.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/matrices.py 
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def metric_csr(graph: RoadGraph, metric: str) -> csr_matrix:
    """The road graph as a CSR weight matrix under one metric.

    ``shortest`` weights are edge lengths in metres, ``fastest`` are free-flow
    traversal times in seconds. Public because the campaign city profiler runs
    its own partial Dijkstras over exactly these weights.
    """
    rows = np.empty(graph.edge_count, dtype=np.int64)
    cols = np.empty(graph.edge_count, dtype=np.int64)
    data = np.empty(graph.edge_count, dtype=np.float64)
    for index, (osm_u, osm_v) in enumerate(graph.edges):
        rows[index] = graph.vertex_of[osm_u]
        cols[index] = graph.vertex_of[osm_v]
        if metric == "fastest":
            data[index] = 3.6 * graph.edge_weight[index] / SPEED_ROADS_URBAN[graph.edge_class[index]]
        else:
            data[index] = graph.edge_weight[index]
    size = graph.vertex_count
    return csr_matrix((data, (rows, cols)), shape=(size, size))

compute_matrices 

compute_matrices(graph: RoadGraph, vertices: list[int]) -> tuple[list[list[int]], list[list[int]], EdgeGeometry, EdgeGeometry]

(D_short, D_fast, depot-edge geometry per metric) for instance vertices.

Geometry covers exactly the depot edges the workbench meta embeds: from the depot (vertices[0]) to every customer, and from every customer back to the depot, keyed "{u}_{v}" on graph vertex ids with [lon, lat] polylines.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/matrices.py 
 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
def compute_matrices(
    graph: RoadGraph,
    vertices: list[int],
) -> tuple[list[list[int]], list[list[int]], EdgeGeometry, EdgeGeometry]:
    """(D_short, D_fast, depot-edge geometry per metric) for instance vertices.

    Geometry covers exactly the depot edges the workbench meta embeds: from the
    depot (vertices[0]) to every customer, and from every customer back to the
    depot, keyed ``"{u}_{v}"`` on graph vertex ids with [lon, lat] polylines.
    """
    n = len(vertices)
    index_array = np.asarray(vertices, dtype=np.int64)
    matrices: dict[str, list[list[int]]] = {}
    geometry: dict[str, EdgeGeometry] = {}

    for metric in ("shortest", "fastest"):
        csr = metric_csr(graph, metric)
        block = _instance_block(csr, index_array)
        if not np.all(np.isfinite(block)):
            raise ValueError("Some instance vertices are mutually unreachable on the road graph")
        matrices[metric] = [[math.ceil(value) for value in row] for row in block]

        edge_geom: EdgeGeometry = {}
        depot = vertices[0]
        _, pred_out = dijkstra(csr, directed=True, indices=depot, return_predecessors=True)
        _, pred_in = dijkstra(csr.T.tocsr(), directed=True, indices=depot, return_predecessors=True)
        for k in range(1, n):
            target = vertices[k]
            path_out = _reconstruct_path(pred_out, depot, target)
            if path_out is not None:
                edge_geom[f"{depot}_{target}"] = _path_lonlat(graph, path_out)
            path_back = _reconstruct_path(pred_in, depot, target)
            if path_back is not None:
                edge_geom[f"{target}_{depot}"] = _path_lonlat(graph, list(reversed(path_back)))
        geometry[metric] = edge_geom

    return matrices["shortest"], matrices["fastest"], geometry["shortest"], geometry["fastest"]

euclidean_matrix_from_vertices 

euclidean_matrix_from_vertices(graph: RoadGraph, vertices: list[int]) -> tuple[list[list[int]], list[tuple[float, float]]]

ENU-plane euclidean matrix (ceil'd metres) + per-vertex ENU coords.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/matrices.py 
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
def euclidean_matrix_from_vertices(
    graph: RoadGraph,
    vertices: list[int],
) -> tuple[list[list[int]], list[tuple[float, float]]]:
    """ENU-plane euclidean matrix (ceil'd metres) + per-vertex ENU coords."""
    coords: list[tuple[float, float]] = []
    for vertex in vertices:
        east, north, _up = graph.node_enu[graph.node_of[vertex]]
        coords.append((east, north))
    n = len(vertices)
    matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            dx = coords[i][0] - coords[j][0]
            dy = coords[i][1] - coords[j][1]
            matrix[i][j] = math.ceil(math.hypot(dx, dy))
    return matrix, coords