Model places, links and two kinds of cost

After this page, you should be able to:

• Translate a transport question into vertices, edges and a weight with explicit units.

• Derive consistent graph views while preserving isolated places and input assumptions.

Builds on: Maps and sets and graph representations.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Reuse the translated graph algorithms and the same invented dataset. Julia travel/build columns are 3 and 4, versus 2 and 3 in Python/JavaScript. The translated construction adjacency is named build_graph_view to distinguish it from the graph-builder function. All versions keep the isolated harbour, distinguish absence from a zero-length route, and separate minutes from construction units.

Decide what vertices and edges represent¶

A vertex is a place, not a passenger or a vehicle. An undirected edge is a candidate direct connection. The route scenarios assume all candidate links are available; the design scenario asks which subset to construct. These are distinct interpretations of the same candidate data.

A trip along a link has a travel time. Building that link has a separate construction cost. Adding those quantities together would be meaningless: minutes and construction units measure different things.

Keep one source table and derive each adjacency view¶

from transport_network import (
    bfs, path_to, dijkstra, weighted_path_to,
    DisjointSet, prim_forest, kruskal_forest,
)

places = {
    "A": "Gate", "B": "Museum", "C": "Library",
    "D": "Market", "E": "Clinic", "F": "Park", "G": "Harbour",
}
# (endpoint, endpoint, travel_minutes, construction_units)
links = [
    ("A", "B", 12, 3), ("A", "C", 3, 6),
    ("B", "C", 2, 2), ("B", "D", 3, 4),
    ("C", "D", 9, 1), ("C", "E", 12, 7),
    ("D", "E", 3, 5), ("D", "F", 8, 2),
    ("E", "F", 2, 3),
]

def adjacency_view(places, links, weight_column=None):
    if weight_column not in (None, 2, 3):
        raise ValueError("choose unweighted, travel time or construction cost")
    graph = {place: [] for place in places}
    for row in links:
        u, v = row[:2]
        if weight_column is None:
            graph[u].append(v)
            graph[v].append(u)
        else:
            weight = row[weight_column]
            graph[u].append((v, weight))
            graph[v].append((u, weight))
    return graph

hop_graph = adjacency_view(places, links)
time_graph = adjacency_view(places, links, 2)
build_graph = adjacency_view(places, links, 3)

// Use BFS, Dijkstra, DisjointSet, Prim and Kruskal from the preceding topics.
var places = new Map([["A","Gate"],["B","Museum"],["C","Library"],["D","Market"],
    ["E","Clinic"],["F","Park"],["G","Harbour"]]);
var links = [["A","B",12,3],["A","C",3,6],["B","C",2,2],["B","D",3,4],
    ["C","D",9,1],["C","E",12,7],["D","E",3,5],["D","F",8,2],["E","F",2,3]];
function adjacency_view(places, links, weight_column = null) {
    if (![null,2,3].includes(weight_column)) throw new RangeError("invalid weight column");
    const graph = new Map([...places.keys()].map(v => [v, []]));
    for (const row of links) {
        const [u,v] = row;
        if (!graph.has(u) || !graph.has(v)) throw new KeyError("unknown endpoint");
        graph.get(u).push(weight_column === null ? v : [v,row[weight_column]]);
        graph.get(v).push(weight_column === null ? u : [u,row[weight_column]]);
    }
    return graph;
}
var hop_graph = adjacency_view(places, links), time_graph = adjacency_view(places, links, 2);
var build_graph_view = adjacency_view(places, links, 3);
const edge_key = (u,v) => JSON.stringify([u,v].sort());

# Reuse the preceding topics' graph algorithms and disjoint sets.
places = Dict("A"=>"Gate","B"=>"Museum","C"=>"Library","D"=>"Market",
    "E"=>"Clinic","F"=>"Park","G"=>"Harbour")
links = [("A","B",12,3),("A","C",3,6),("B","C",2,2),("B","D",3,4),
    ("C","D",9,1),("C","E",12,7),("D","E",3,5),("D","F",8,2),("E","F",2,3)]
function adjacency_view(places, links, weight_column=nothing)
    weight_column in (nothing,3,4) || throw(ArgumentError("invalid weight column"))
    graph = Dict(v=>Any[] for v in keys(places))
    for row in links
        u,v = row[1:2]
        push!(graph[u], weight_column === nothing ? v : (v,row[weight_column]))
        push!(graph[v], weight_column === nothing ? u : (u,row[weight_column]))
    end
    return graph
end
hop_graph = adjacency_view(places, links)
time_graph = adjacency_view(places, links, 3)
build_graph_view = adjacency_view(places, links, 4)
edge_key(u,v) = u <= v ? (u,v) : (v,u)

The places dictionary is an exact-key map from a stable identifier to a display name. All places become graph keys, including G, which has no incident link. Each undirected link appears once in links and twice in adjacency storage. The input contract requires distinct valid endpoints per link, no repeated unordered pairs, and finite positive weights. The helper derives views from this declared valid table; it is not a general data-cleaning routine.

The link order controls neighbour order, and therefore tie choices in BFS. It does not give a priority to cheap edges. A coordinate on the diagram indicates layout only; it is not used to calculate a weight.

Measure an answer with the same units as its question¶

def route_total(route, links, weight_column):
    if weight_column not in (2, 3):
        raise ValueError("choose travel time or construction cost")
    if route is None:
        return None
    weights = {frozenset((row[0], row[1])): row[weight_column]
               for row in links}
    return sum(weights[frozenset((u, v))]
               for u, v in zip(route, route[1:]))

function route_total(route, links, weight_column) {
    if (![2,3].includes(weight_column)) throw new RangeError("invalid weight column");
    if (route === null) return null;
    const weights = new Map(links.map(row => [edge_key(row[0],row[1]),row[weight_column]]));
    const rest = route.slice(1); let total = 0;
    for (let i = 0; i < rest.length; i++) {
        const key = edge_key(route[i],rest[i]);
        if (!weights.has(key)) throw new KeyError("missing link"); total += weights.get(key);
    }
    return total;
}

function route_total(route, links, weight_column)
    weight_column in (3,4) || throw(ArgumentError("invalid weight column"))
    route === nothing && return nothing
    weights = Dict(edge_key(row[1],row[2])=>row[weight_column] for row in links)
    return sum((weights[edge_key(u,v)] for (u,v) in zip(route,route[2:end])); init=0)
end

This helper assumes an actual route from the graph algorithms, with valid vertices and consecutive endpoints connected by declared links. A one-vertex route costs zero; None remains absence, not a zero-cost trip. A frozenset makes an unordered endpoint-pair key, appropriate here because there are no parallel links and direction is deliberately ignored.

Adapter contracts and preparation costs¶

adjacency_view returns fresh adjacency lists without changing places or links. The unweighted view contains neighbour identifiers; weighted entries are (neighbour, weight) pairs. Column None, 2 or 3 selects the representation. Another selector raises ValueError; an undeclared endpoint raises KeyError when its adjacency list is accessed. Invalid row shapes, duplicate pairs or non-finite weights are outside this helper’s contract and are not comprehensively checked. Validate external data before adapting it.

route_total returns a number in the selected units or None for an absent route. A selector other than 2 or 3 raises ValueError, even if the route is None. A missing consecutive pair raises KeyError; this does not make the helper a complete route validator. In particular, a singleton with an unknown identifier has no pair to check. Callers must supply a valid route, rather than use a zero sum as proof of validity.

For n places and m links, each view takes O(n+m) time and returned storage under expected constant-time hashing. All three views preserve the same vertex set and edge pairs, but project different edge information. Keeping one source table prevents the time and construction views from accidentally describing different networks. Measuring a k-edge route rebuilds a pair lookup and scans k pairs; the final page accounts for that extra preparation and the Python slice.

Check your understanding¶

Predict the result or justify the choice before opening the explanation.

1. Should unreachable Harbour G be omitted from places to simplify the graph?

2. What do route_total(["A"], links, 2) and route_total(None, links, 2) mean?

Next: Fewest links.