Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/yeremyacuna/LYNX/llms.txt

Use this file to discover all available pages before exploring further.

Graph<T> is a weighted adjacency-list graph that forms the backbone of LYNX’s geographic routing layer. Each vertex stores an arbitrary data value of type T; edges carry integer weights and are stored as a singly-linked list hanging off each vertex. LYNX instantiates the graph as Graph<string> where vertex data is a city ID string, and the graph is configured as undirected so that road distances apply symmetrically between any two cities. The full city graph is loaded once at startup and then queried repeatedly to price trip routes via Dijkstra’s algorithm.

​
Adjacency-List Structure

Internally, the graph is an array of Vertex structs. Each vertex owns a linked list of Edge structs: 
struct Edge {
    int   to;      // index of the destination vertex
    int   weight;  // edge weight (distance in 100-metre units)
    Edge* next;    // next edge in this vertex's list
};

struct Vertex {
    T     data;    // vertex payload (e.g. city ID string)
    Edge* edges;   // head of the adjacency list
    bool  active;  // true once the vertex has been added
};
New edges are prepended to the adjacency list, so addEdge is O(1). For an undirected graph, two Edge objects are created — one in each direction.

​
Template

template <typename T>
class Graph
T is the vertex data type. LYNX uses Graph<string> with short city ID strings (e.g., "LIM", "CUS").

​
Constructor

Graph(int capacity, bool directed = false)
  • capacity — fixed maximum number of vertices. LYNX allocates 7000 for the city graph.
  • directed — pass true for a directed graph; LYNX uses false (undirected).
Capacity is fixed at construction; the vertex array is not resized at runtime.

​
Method Reference

MethodSignatureDescription
addVertexint addVertex(T value)Appends a new vertex and returns its index; returns -1 if the graph is full
addEdgevoid addEdge(int from, int to, int weight = 1)Adds a weighted edge; adds the reverse edge automatically if undirected
removeEdgevoid removeEdge(int from, int to)Removes the edge (and its reverse for undirected graphs)
hasEdgebool hasEdge(int from, int to) constReturns true if a direct edge exists from from to to
degreeint degree(int v) constReturns the number of edges leaving vertex v
bfsvoid bfs(int start) constBreadth-first traversal from start; uses an internal Queue<int> and prints vertices in BFS order
dfsvoid dfs(int start) constIterative depth-first traversal using an internal Stack<int>
dfsRecursivevoid dfsRecursive(int start) constRecursive DFS traversal
dijkstravoid dijkstra(int start) constPrints shortest distances and full paths from start to all reachable vertices
dijkstraDistanceint dijkstraDistance(int start, int target) constReturns the shortest-path distance as an integer; returns -1 if unreachable
getDataT getData(int v) constReturns the data stored at vertex v
isEmptybool isEmpty() constReturns true when no vertices have been added
getSizeint getSize() constCurrent vertex count
isDirectedbool isDirected() constReturns true if the graph was constructed as directed
printvoid print() constPrints the full adjacency list with weights
clearvoid clear()Removes all edges and marks all vertices inactive; resets size to 0
findVertexint findVertex(T value) constLinear scan; returns the index of the first vertex whose data equals value, or -1

​
Dijkstra’s Algorithm in Detail

Both dijkstra and dijkstraDistance use an internal Heap<DijkstraNode> configured as a min-heap priority queue. DijkstraNode is a private nested struct inside Graph<T> — it is not accessible from outside the class: 
// private nested struct — internal to Graph<T>
struct DijkstraNode {
    int dist;    // tentative distance from source
    int vertex;  // vertex index
};

auto minCmp = [](const DijkstraNode& a, const DijkstraNode& b) {
    return a.dist < b.dist;
};
Heap<DijkstraNode, decltype(minCmp)> heap(size_ * 2 + 1, minCmp);
The algorithm initialises all distances to 2147483647 (the sentinel “infinity” constant used in the source), sets dist[start] = 0, and relaxes edges by pushing updated DijkstraNode entries onto the heap. Stale entries (where curr.dist > dist[v]) are skipped with a continue check, avoiding the need to support a decrease-key operation.
  • dijkstra(start) — prints distances and reconstructed paths to every reachable vertex. Useful for debugging the city graph.
  • dijkstraDistance(start, target) — returns only the integer distance to a single target. Returns -1 if the target is unreachable. This is the method called by TripManager to price a route.

​
City Graph Loading

TripManager::loadCityGraph(FileManager&) builds the production graph:
  1. Reads cities.csv — each row provides a city ID and display name. Every city is added with addVertex, and the returned index is stored in an unordered_map<string, int> keyed by city ID.
  2. Reads connections.csv — each row provides two city IDs and a distance in kilometres. The loader multiplies by 100 to convert to integer units of 100 metres before calling addEdge.
  3. A second unordered_map<string, string> maps display names back to city IDs so that user-facing city name input can be translated to graph vertex indices.
Weight unit. Edge weights in the graph are stored in units of 100 metres (i.e., kilometres × 100, cast to int). The value returned by dijkstraDistance is therefore in these same units. Divide by 100.0 to recover kilometres:
int raw = g.dijkstraDistance(lima, cusco);
if (raw != -1) {
    double km = raw / 100.0;
    cout << "Distance: " << km << " km";
}

​
Code Example

Graph<string> g(100, false); // undirected, capacity 100

int lima     = g.addVertex("LIM");
int cusco    = g.addVertex("CUS");
int arequipa = g.addVertex("AQP");

g.addEdge(lima, cusco,     110000); // 1100 km in 100m units
g.addEdge(lima, arequipa,   79700);

// BFS traversal
g.bfs(lima);

// Shortest path distance
int dist = g.dijkstraDistance(lima, cusco);
if (dist != -1) {
    double km = dist / 100.0;
    cout << "Distance: " << km << " km";
}

// Print full adjacency list
g.print();

// Find vertex index by city ID
int idx = g.findVertex("CUS"); // returns 1

​
Complexity

OperationTime Complexity
addVertexO(1)
addEdgeO(1)
removeEdgeO(E) per vertex adjacency list
hasEdgeO(E)
degreeO(E)
bfsO(V + E)
dfsO(V + E)
dfsRecursiveO(V + E)
dijkstraO((V + E) log V)
dijkstraDistanceO((V + E) log V)
findVertexO(V)
clearO(V + E)

Build docs developers (and LLMs) love

Get started for freeTalk to us