How jlittle22/skimap works
Project Type and Purpose
• This is a command-line C application that builds an in-memory graph (“SkiMap”) from two input files (vertex data and edge data), applies a modified Bellman-Ford algorithm to satisfy user preferences, and prints a ski-trail path.
• Key features: file parsing, custom data structures (LinkedList, MinHeap, SmallFloat), graph representation (Vertex, Edge, SkiMap), algorithm module, error handling.
File Structure
• Top-level modules (each .c/.h pair):
• Edge – represents a directed ski‐trail segment
• Vertex – represents an intersection/endpoint, holds list of outgoing edges
• SkiMap – container for all vertices and start points, the graph object
• LinkedList – polymorphic singly linked list (used by Vertex/SkiMap)
• MinHeap – dynamic array min-heap (present but unused)
• SmallFloat – custom float‐packing utility
• Errors – centralized error reporting and assertions
• main.c – driver: parses arguments, reads .vdata/.edata files, initializes graph, invokes pathfinding, prints results
• Support files: Makefile, sample .edata/.vdata inputs.
Extract Architectural Insights from the README
• The “Abstract Description” outlines:
• Flags passed in an 8-bit field → Driver → Parser → Object loaders → SkiMap graph → Modified Bellman-Ford → Path output.
• The “STRUCTURE” ASCII art shows a layered graph model: SkiMap → Vertex list → Vertex → Edge list → Edge → Destination vertex.
a. Main Components to Represent
1. CLI Driver (main.c)
2. Input Parser (vertex & edge file readers)
3. Data Model Layer
– Vertex module
– Edge module
– SkiMap module (graph container)
4. Utility Modules
– LinkedList
– SmallFloat
– MinHeap (can be shaded as “planned/unused”)
– Errors
5. Algorithm Module
– Bellman-Ford implementation (within SkiMap.c or separate algorithm block)
6. Output Layer
– Console/STDOUT reporting of path
b. Relationships & Interactions
• CLI Driver invokes Parser →
• Parser creates Vertex objects (Vertex.h/.c) and stores them in a LinkedList →
• Parser creates Edge objects (Edge.h/.c), links source/destination, attaches to Vertex.edges list →
• After loading, CLI Driver constructs SkiMap object (holds two Lists: allVertices, startPoints) →
• Driver calls SkiMap_search(userFlags) → Algorithm module manipulates Vertex.data via SmallFloat, relaxes edges →
• Results returned as a path (sequence of Edge/Vertex names) →
• Driver prints the path or error report (via Errors module).
c. Architectural Patterns & Principles
• Modular layering (separate parsing, data, utilities, algorithm, UI)
• Encapsulation via C structs + “member” functions
• Custom dynamic data structures for flexibility (LinkedList, MinHeap)
• Single Responsibility: each module focused on one concern
d. Key Technologies & Libraries
• C99 (structs, stdlib, stdio, assertions)
• Makefile for build orchestration
• Custom memory management (malloc/free in LinkedList, MinHeap)
• Bit‐packing (SmallFloat) for space optimisation