CampusNavigation

Imported from CrocodileWoodGordon/CampusNavigation (AGENTS.md). Install upstream with npx skills add CrocodileWoodGordon/CampusNavigation. Copyright stays with the author.

CampusNavigation Project Guide

This repository is for a Data Structures course project: a campus navigation system based on an undirected dynamic graph. The teacher-provided files are under resources/校园导航/; treat them as the source of truth for requirements, command formats, sample data, and the optional skeleton.

Source Documents

• Main requirement: resources/校园导航/新版课程项目说明.md
• Mandatory CLI contract: resources/校园导航/命令接口规范.md
• Optional extra-credit tasks: resources/校园导航/扩展与加分要求.md
• Test data description: resources/校园导航/测试数据/README.md
• Optional reference skeleton: resources/校园导航/CampusNavigation/

Do not edit teacher-provided files unless the user explicitly asks. Copy or reimplement the skeleton into the real project area if needed.

Project Goal

Build a C++17 program named CampusNavigation that can be evaluated in batch mode:

./CampusNavigation < command.txt > answer.txt

The program must model places and roads as an undirected graph, support dynamic updates, provide queries, and implement graph algorithms using only self-written data structures and algorithms. Do not use external graph algorithm libraries.

Required Data Model

Places use these fields:

• place_id: unique string ID, no spaces, for example P0001
• display_name: display name, no spaces
• category: for example Teaching, Dining, Dormitory, Sports, Medical, Other
• stay_time: integer minutes
• open_time: HH:MM
• close_time: HH:MM

Roads use these fields:

• from_id: start place ID
• to_id: end place ID
• distance: integer meters
• walk_time: integer minutes
• status: open or closed

Graph rules:

• The graph is undirected by default.
• Core algorithms only use roads with status=open.
• The graph must support add, delete, update, open, and close operations after loading.
• places.csv and roads.csv must support both header and no-header forms, and should ignore empty lines.

Mandatory Features

Implement these first, before any optional work:

• CSV load/save for places and roads.
• Add, delete, and update places.
• Add, delete, and update roads.
• Open and close roads.
• Query one place by ID.
• Query all place IDs in a category.
• Query all adjacent roads of a place.
• Connected components using only open roads.
• Dijkstra shortest path with both DIST and TIME weight modes, using one parameterized implementation.
• Timed shortest path that filters out places closed at the given HH:MM time.
• Must-pass path planning by splitting into ordered shortest-path segments and concatenating them.
• Minimum spanning tree over open roads by distance; output DISCONNECTED if the current open graph is disconnected.
• Critical node and critical edge analysis over open roads.

Mandatory CLI Commands

The command names, argument order, keywords, output formats, and sorting rules must exactly follow resources/校园导航/命令接口规范.md.

Required commands:

• LOAD <places_file> <roads_file>
• SAVE <places_out_file> <roads_out_file>
• QUERY_PLACE <place_id>
• QUERY_CATEGORY <category>
• ADJ <place_id>
• ADD_PLACE <place_id> <display_name> <category> <stay_time> <open_time> <close_time>
• DELETE_PLACE <place_id>
• UPDATE_PLACE <place_id> <field> <value>
• ADD_ROAD <from_id> <to_id> <distance> <walk_time> <status>
• DELETE_ROAD <from_id> <to_id>
• UPDATE_ROAD <from_id> <to_id> <field> <value>
• CLOSE_ROAD <from_id> <to_id>
• OPEN_ROAD <from_id> <to_id>
• COMPONENTS
• SHORTEST <from_id> <to_id> <DIST|TIME>
• TIMED_SHORTEST <from_id> <to_id> <time> <DIST|TIME>
• MUST_PASS <from_id> <to_id> <DIST|TIME> <k> <p1> ... <pk>
• MST
• CRITICAL
• QUIT

Common output/error rules:

• Successful maintenance operations output OK.
• Unknown commands output ERROR unknown_command.
• Missing places output ERROR place_not_found.
• Duplicate places output ERROR place_already_exists.
• Missing roads output ERROR road_not_found.
• Duplicate roads output ERROR road_already_exists.
• Unsupported update fields output ERROR invalid_field.
• Unreachable paths output NO_PATH.
• QUIT has no output.

Sorting rules:

• QUERY_CATEGORY: place IDs in lexicographic ascending order.
• ADJ: neighbors in lexicographic ascending order by neighbor place ID.
• COMPONENTS: component sizes in descending order.
• MST: edges sorted by (min(u,v), max(u,v)) lexicographically; print smaller endpoint first.
• CRITICAL: nodes lexicographically; edges by (min(u,v), max(u,v)) lexicographically.

Recommended Implementation Structure

The provided skeleton is optional, but this structure is recommended because it matches the course documents:

• LocationInfo.h/.cpp: place and road data structs.
• LGraph.h/.cpp: graph ADT, internal storage, dynamic updates, and basic queries.
• Algorithm.h/.cpp: BFS/DFS, Dijkstra, must-pass path, MST, critical nodes/edges.
• CsvIO.h/.cpp: CSV parsing and writing.
• CommandProcessor.h/.cpp: stdin command parsing and exact stdout formatting.
• main.cpp: create processor, read commands until QUIT.
• GraphException.h: project-specific exceptions or error codes.
• CMakeLists.txt: C++17 build configuration.

Keep command parsing and output formatting separate from graph algorithms. Algorithms should return structured results; CommandProcessor should be responsible for converting them to the required text format.

Data Structure Rules

Prefer an adjacency-list design because the project emphasizes dynamic sparse graphs and larger test cases:

• Store places in unordered_map<string, Place> or an equivalent ID-indexed structure.
• Store adjacency by place ID, for example unordered_map<string, unordered_map<string, Road>>.
• For undirected roads, keep both adjacency directions consistent or provide a single canonical edge store plus adjacency references.
• Define a canonical road key using (min(from_id, to_id), max(from_id, to_id)) to avoid duplicate undirected roads.
• Deleting a place must remove all adjacent roads.
• Updating road status must affect all algorithm visibility immediately.

The report must explain the chosen graph representation, alternatives considered, and time/space complexity tradeoffs.

Algorithm Rules

• BFS/DFS components must ignore closed roads.
• Dijkstra must be one implementation parameterized by weight mode (distance or walk_time).
• Timed shortest path should filter unavailable places first; open_time <= time <= close_time works with HH:MM string comparison.
• Must-pass path should run shortest path between consecutive required stops; if any segment fails, output NO_PATH.
• MST should use either Kruskal with DSU or Prim; Kruskal is usually simpler with a canonical edge list.
• Critical nodes and edges may be implemented with Tarjan algorithms for efficiency. A brute-force remove-and-recompute method is easier but may be too slow on large cases.
• All algorithms must handle disconnected graphs, empty graphs, closed roads, missing IDs, duplicate IDs, and self/invalid road edge cases consistently with the CLI spec.

Testing Rules

Use the teacher-provided cases under resources/校园导航/测试数据/.

Required test groups:

• Small required cases: 必做/small_cases/*
• Medium required cases: 必做/medium_cases/*
• Large required cases: 必做/large_cases/*
• Historical ECNU sample: 必做/sample_ecnu

For each case, run the program with that case's command.txt and compare against answer.txt. The current project spec says the CLI output format is mandatory, so aim for exact output unless a teacher note explicitly says semantic comparison is acceptable.

Recommended verification command pattern:

./CampusNavigation < path/to/command.txt > /tmp/answer.txt
diff -u path/to/answer.txt /tmp/answer.txt

Also add self-made edge tests for:

• CSV with and without headers.
• Empty lines in CSV.
• Duplicate place and road insertion.
• Deleting a place with incident roads.
• Closed roads changing reachability.
• Timed path where start, end, or middle node is closed.
• Must-pass with repeated or unreachable required nodes.
• Disconnected MST.
• Graphs with no critical nodes and graphs where every edge is critical.

Optional Extra Credit

Only start optional work after the mandatory features and tests are stable.

• SHORTEST_K <from_id> <to_id> <K>: layered shortest path with up to 10 acceleration tickets; output PATH <total_time> K_USED <k_used> NODES ... FAST <count> ....
• Custom micro dataset and adversarial dataset with explanation documents.
• GUI or visualization that still preserves the mandatory CLI entry point.

Extra credit must follow resources/校园导航/扩展与加分要求.md and the optional command section in 命令接口规范.md.

Progress Assignment

Use these milestones to divide work and report progress:

1. Project setup: create real source tree, CMake build, executable name CampusNavigation, and minimal stdin loop.
2. Data model and CSV: implement place/road structs, graph storage, load/save, and validation.
3. Basic maintenance commands: implement add/delete/update/open/close and exact OK/ERROR behavior.
4. Query commands: implement QUERY_PLACE, QUERY_CATEGORY, and ADJ with required sorting.
5. Core path algorithms: implement components, Dijkstra SHORTEST, timed shortest, and must-pass.
6. MST and critical analysis: implement MST and CRITICAL, optimize for medium/large tests.
7. Full CLI conformance: verify every command's parameter order, output fields, error handling, and sorting.
8. Required testing: run all small and medium cases, then large cases; fix mismatches before moving on.
9. Documentation: write README with build/run instructions and write the experiment report sections.
10. Optional extras: implement only after mandatory behavior is correct and documented.

When multiple people or agents work together, assign only one milestone owner at a time for files that overlap heavily, especially LGraph, Algorithm, and CommandProcessor. Before changing those files, check recent changes and avoid overwriting unrelated work.

Coding Standards

• Use C++17.
• Keep code modular and readable; prefer small focused classes/functions.
• Do not rely on non-standard compiler extensions for required functionality.
• Avoid global mutable state except constants.
• Prefer deterministic output everywhere, even where unordered containers are used internally.
• Parse commands robustly but do not invent output formats not listed in the spec.
• Keep comments brief and useful, especially for non-trivial algorithms.
• Do not add external dependencies unless the user explicitly approves them.
• Keep generated build directories, binaries, and temporary outputs out of version control.

Report Requirements

The final submission must include source code, README, and an experiment report. The report should cover:

• Graph data structure design and alternatives.
• Algorithm ideas and complexity analysis.
• Test plan and results, including boundary cases.
• Problems encountered and solutions.
• AI collaboration record if AI was used.

If AI is used, the report must include selected key prompts, debugging stories, at least one rejected AI suggestion, and a summary of what was AI-assisted versus independently decided. Do not fabricate AI conversations.