Qu

← All demos

Data & I/O

Linked list & graph

a double-ended `linked_list` used to build a small road network's edge list, then a weighted `graph` over the same five towns, solved with Dijkstra's algorithm via `.shortest_path`.

catalog/qu_linked_list_and_graph.qu

The linked_list plays a genuinely double-ended role here: edges are discovered in two directions during a (fictional) survey -- forward discoveries get appended with `.push_back`, but a late report of a previously-missed direct link between the depot and the first town needs to be recorded as the FIRST leg of the route, so it goes in with `.push_front`. `.to_vec()` then materializes the whole deque, in final front-to-back order, for printing.

What it exercises

How it works

Part 1: linked_list -- recording a road survey's discovered legs

legs = linked_list()
legs.push_back("Depot->A")
legs.push_back("A->B")
legs.push_back("B->C")
legs.push_back("C->D")
# Late correction: a direct Depot->A link was actually surveyed FIRST,
# before any of the above -- push it onto the front, not the back.
legs.push_front("Survey-start marker")

print("Survey legs recorded (front to back): {legs.to_vec()}")
print("Leg count: {len(legs)}")

first_leg = legs.pop_front()
last_leg = legs.pop_back()
print("Popped front: {first_leg}")
print("Popped back: {last_leg}")
print("Remaining legs: {legs.to_vec()}")

Part 2: graph -- five towns (Depot, A, B, C, D), weighted roads, Dijkstra

g = graph()
g.add_node("Depot")
g.add_edge("Depot", "A", weight=4)
g.add_edge("Depot", "C", weight=1)
g.add_edge("C", "A", weight=2)
g.add_edge("A", "B", weight=5)
g.add_edge("C", "D", weight=8)
g.add_edge("B", "D", weight=1)
g.add_edge("D", "A", weight=3)

print("")
print("Town count: {len(g)}")
print("Neighbors of C: {g.neighbors('C')}")
print("Direct Depot<->B road exists: {g.has_edge('Depot', 'B')}")
print("Direct Depot<->A road exists: {g.has_edge('Depot', 'A')}")

cost = g.shortest_path("Depot", "D")
print("Shortest Depot->D route cost: {cost}")
# Hand-verified Dijkstra trace from Depot (undirected graph, so every edge
# weight applies both ways):
#   dist(Depot) = 0
#   relax Depot's edges: dist(A) = 4, dist(C) = 1
#   pop C (dist 1): relax C's edges: dist(A) = min(4, 1+2) = 3, dist(D) = min(inf, 1+8) = 9
#   pop A (dist 3): relax A's edges: dist(B) = min(inf, 3+5) = 8, dist(D) = min(9, 3+3) = 6
#   pop D (dist 6): relax D's edges: dist(B) = min(8, 6+1) = 7
#   pop B (dist 7): done
# Cheapest route Depot->D costs 6, via Depot->C->A->D (1 + 2 + 3 = 6) --
# matching the printed `cost` value exactly.

unreachable = graph(directed=true)
unreachable.add_node("X")
unreachable.add_node("Y")
result = unreachable.shortest_path("X", "Y")
print("Shortest path with no edge at all (directed, unreachable): {result}")

Results

printed
Survey legs recorded (front to back): ("Survey-start marker", "Depot->A", "A->B", "B->C", "C->D")
Leg count: 5
Popped front: Survey-start marker
Popped back: C->D
Remaining legs: ("Depot->A", "A->B", "B->C")

Town count: 5
Neighbors of C: ("Depot", "A", "D")
Direct Depot<->B road exists: false
Direct Depot<->A road exists: true
Shortest Depot->D route cost: 6
Shortest path with no edge at all (directed, unreachable): none

The whole program

Runnable as it stands: qu run catalog/qu_linked_list_and_graph.qu

# qu_linked_list_and_graph.qu -- a double-ended `linked_list` used to build

# a small road network's edge list, then a weighted `graph` over the same

# five towns, solved with Dijkstra's algorithm via `.shortest_path`.

#

# The linked_list plays a genuinely double-ended role here: edges are

# discovered in two directions during a (fictional) survey -- forward

# discoveries get appended with `.push_back`, but a late report of a

# previously-missed direct link between the depot and the first town needs

# to be recorded as the FIRST leg of the route, so it goes in with

# `.push_front`. `.to_vec()` then materializes the whole deque, in final

# front-to-back order, for printing.

#

# Constructs exercised (all real, verified-working builtins):

#   linked_list()                         -- new empty deque

#   l.push_back(v), l.push_front(v)        -- append / prepend

#   l.pop_front(), l.pop_back()            -- remove from either end

#   l.to_vec()                            -- materialize front-to-back

#   len(l)                                -- element count

#   graph([directed=])                     -- new node+edge graph

#   g.add_node(id), g.add_edge(a, b, weight=)

#   g.neighbors(id), g.has_edge(a, b)

#   g.shortest_path(source, target)        -- Dijkstra

#   len(g)                                -- node count


backend auto

#%% Part 1: linked_list -- recording a road survey's discovered legs

legs = linked_list()
legs.push_back("Depot->A")
legs.push_back("A->B")
legs.push_back("B->C")
legs.push_back("C->D")
# Late correction: a direct Depot->A link was actually surveyed FIRST,

# before any of the above -- push it onto the front, not the back.

legs.push_front("Survey-start marker")

print("Survey legs recorded (front to back): {legs.to_vec()}")
print("Leg count: {len(legs)}")

first_leg = legs.pop_front()
last_leg = legs.pop_back()
print("Popped front: {first_leg}")
print("Popped back: {last_leg}")
print("Remaining legs: {legs.to_vec()}")

#%% Part 2: graph -- five towns (Depot, A, B, C, D), weighted roads, Dijkstra

g = graph()
g.add_node("Depot")
g.add_edge("Depot", "A", weight=4)
g.add_edge("Depot", "C", weight=1)
g.add_edge("C", "A", weight=2)
g.add_edge("A", "B", weight=5)
g.add_edge("C", "D", weight=8)
g.add_edge("B", "D", weight=1)
g.add_edge("D", "A", weight=3)

print("")
print("Town count: {len(g)}")
print("Neighbors of C: {g.neighbors('C')}")
print("Direct Depot<->B road exists: {g.has_edge('Depot', 'B')}")
print("Direct Depot<->A road exists: {g.has_edge('Depot', 'A')}")

cost = g.shortest_path("Depot", "D")
print("Shortest Depot->D route cost: {cost}")
# Hand-verified Dijkstra trace from Depot (undirected graph, so every edge

# weight applies both ways):

#   dist(Depot) = 0

#   relax Depot's edges: dist(A) = 4, dist(C) = 1

#   pop C (dist 1): relax C's edges: dist(A) = min(4, 1+2) = 3, dist(D) = min(inf, 1+8) = 9

#   pop A (dist 3): relax A's edges: dist(B) = min(inf, 3+5) = 8, dist(D) = min(9, 3+3) = 6

#   pop D (dist 6): relax D's edges: dist(B) = min(8, 6+1) = 7

#   pop B (dist 7): done

# Cheapest route Depot->D costs 6, via Depot->C->A->D (1 + 2 + 3 = 6) --

# matching the printed `cost` value exactly.


unreachable = graph(directed=true)
unreachable.add_node("X")
unreachable.add_node("Y")
result = unreachable.shortest_path("X", "Y")
print("Shortest path with no edge at all (directed, unreachable): {result}")