Advanced Project 7 — Campus Navigation¶

Difficulty: Advanced · Estimated effort: 2 weeks · Prerequisites: Module 11 — RAII and Smart Pointers, Module 14 — The STL with OOP, Module 15 — SOLID and Design Patterns · Demanded pattern decisions: strategy, observer

This is one of the designated integration projects, and one of the projects that requires a design-pattern decision: at least two patterns must be named and justified by a requirement, and one alternative must be considered and declined in writing.

No complete solution is provided. The routing policies and the update mechanism are the design decisions, and they are yours.

1. Scenario¶

A campus map has buildings, pathways and accessible routes, with distances, step counts and whether a route is step-free. Students want directions between two places, and the answer must be able to optimise for different things: least walking, fewest turns, or step-free only. The facilities office edits the map during the year — closed paths, new ramps — and wants the directions to change accordingly.

The previous tool hard-coded one route metric and had to be changed in three places to support a second one, which is the design problem this project is about.

2. Problem statement¶

Build a navigation system over an editable graph: nodes are places, edges are routes with attributes, and a routing policy turns a request into a path. Editing the map must update dependent answers without the routing code knowing about editing, and the system must report what changed and how it affected existing routes.

3. User requirements¶

[ ] Load a map from a file; report it as a node and edge count.
[ ] Ask for a route between two places under a named policy.
[ ] Ask for a step-free route specifically, and be told when none exists.
[ ] Close a path or open a new one, and see which routes are affected.
[ ] List all places reachable from a given place under the current map.
[ ] Save the edited map and load it back.

4. Functional requirements¶

[ ] Place and Route with attributes: distance, steps, step-free flag, name.
[ ] A Map owning places and routes, with edit operations and validation.
[ ] A RoutingPolicy interface with at least two implementations: shortest distance and fewest steps, plus a filtered variant for step-free only.
[ ] A routing result that includes the path, each leg, and the totals per metric.
[ ] Reachability and connectivity queries, with disconnected components reported.
[ ] A documented file format for places and routes, with line-numbered errors.
[ ] Errors for an unknown place, no route found, and a malformed map (duplicate place, edge to a missing place, negative distance).

5. Non-functional requirements¶

[ ] The routing policies contain no knowledge of the map's storage — they work through a small documented interface.
[ ] Adding a third policy touches no existing file except the registry or configuration.
[ ] A refused edit leaves the map unchanged.
[ ] Route results are deterministic: equal-cost paths are broken by a documented rule.
[ ] Builds warning-free with g++ -std=c++17 -Wall -Wextra -Werror.

6. Suggested features¶

A route description in words: "head north past the library, then turn left".
Weighted accessibility penalties rather than a hard filter, with the weights in the map file.
An "affected routes" report after an edit, listing cached queries that are now stale.
A comparison of two policies for the same pair, printed side by side.

7. OOP concepts involved¶

Concept	Required	Where it appears
Multiple classes	yes	`Place`, `Route`, `Map`, policies, route result, repository of queries, error types
Relationships	yes	Map ◆ places and routes; route ──> two places; policy ──> map through an interface
Encapsulation	yes	The graph's adjacency structure is private; edits go through validating operations
Inheritance or composition	yes	Policies behind an interface; the map has a route repository rather than deriving from it
Polymorphism	yes	Policy dispatch; the route-finding algorithm is written once against the interface
The STL	yes	`std::map`/`std::unordered_map` for adjacency, `std::priority_queue` for the frontier, `std::set` for visited
Exception handling	yes	Unknown places, unreachable requests and malformed maps throw distinct types

8. Suggested design considerations¶

The pattern decision you must make and justify¶

Strategy, for the routing metric. The requirement that earns it is a third policy without editing the routing code. The alternative is a comparator or a lambda cost function, which is lighter and may be enough if you only ever vary one thing. Say which you chose and why, and bear in mind that this project varies the filter as well as the cost.

Observer, for map edits. Existing route queries must be invalidated when the map changes, without the map knowing what a query is. Registration and notification is the observer. The alternative is explicit invalidation by the caller, or recomputation on every lookup — argue which fits your requirement, and decline the other in writing: that is the declined-pattern item.

Ideas worth weighing and recording: composite, for a route that contains sub-routes (probably not earned unless you add named multi-leg journeys); flyweight, for shared route descriptions (a temptation that is almost never worth it here).

Other design points¶

Define the policy interface by what a routing algorithm needs. If it needs the whole map, the interface is wrong and the strategy is decorative. Write the smallest interface that lets Dijkstra's algorithm run, and document it.

Determinism is a requirement, not a nicety. Equal-cost paths must break ties by a documented rule, or your tests will be flaky and your users will get different answers to the same question.

Validate the map at load, once. A malformed edge discovered halfway through a query is a design failure; the loader is the right place, and the errors should be batched with line numbers.

9. Minimum viable version¶

Places and routes in memory, one routing policy (shortest distance), a route query printing the path and the total, and errors for unknown places and no route. No file loading, no policies.

10. Intermediate extension¶

Add the second policy and the step-free filter, plus file loading with three kinds of malformed map rejected with line numbers. Then verify that equal-cost ties break by your documented rule across repeated runs.

11. Advanced extension¶

Add the edit operations with the staleness report, the reachability query with disconnected components, and the third policy from the configuration. Then write the design note: the two patterns, the declined alternative, and the decision you would reverse — with its cost.

12. Testing checklist¶

[ ] A two-place map routes directly and reports the right totals
[ ] A route between a place and itself is an empty path with zero totals, as documented
[ ] An unreachable destination is reported as no route, not as an infinite path
[ ] The shortest-distance and fewest-steps policies differ on the documented map
[ ] A step-free request across a map without a step-free route is refused with a reason
[ ] Closing a route invalidates dependent queries, or they are recomputed, per your design
[ ] A refused edit (duplicate place, missing endpoint, negative distance) leaves the map as it was
[ ] Reachability from a place lists exactly its component, and disconnected components are reported
[ ] Equal-cost paths are resolved by the documented tie-break, identically on repeated runs
[ ] Save → load → save produces identical files
[ ] Each leg's metric sums to the reported total

13. Documentation checklist¶

[ ] The map file format with a full example and three invalid ones
[ ] The policy interface, and why it is the smallest one that works
[ ] The tie-break rule for equal-cost paths
[ ] The class diagram with ownership and the injected policy
[ ] The staleness policy, with one worked example of an edit affecting a query

14. Self-evaluation rubric¶

Criterion	Excellent looks like	Weight
Policy design	Policies independent, third policy added with no edits to routing	25%
Graph correctness	Routing, reachability and tie-breaks verified on a documented map	25%
Pattern decisions	Strategy and observer justified; the declined alternative argued	20%
Edit handling	Edits validated, refusals rolled back, staleness handled by design	15%
Failure handling	Malformed maps and unreachable requests rejected with context	10%
Documentation	Format, interface, tie-break and staleness policy written down	5%