PROJECT / 004 · GRAPH ALGORITHMS
Graph ADT & Algorithms
Connections, explored from first principles.
Conceptual illustration · not a screenshot or measured result
Overview
ADTGraph is a first-year Python project implementing directed and undirected graphs, with optional edge weights and handwritten graph algorithms. It combines a mutable graph API, BFS and DFS iterators, text-file storage, and automated tests using only the Python standard library.
Motivation
Implementing a graph abstract data type makes the connection between representation and algorithms explicit. The project brings together vertex and edge operations, traversal, and pathfinding in one small library, exposing the work that a ready-made graph package would usually handle.
How it works
Graphs can be constructed in memory or read from text files. BFS and DFS iterators explore reachable vertices and retain paths. Dijkstra and Euclidean A* find shortest paths, while topological sorting, Kosaraju's strongly connected components, bridges, and bipartite checks examine graph structure. Exact maximum-clique and travelling-salesperson searches cover small graphs.
Architecture
domain/Graph.py owns the graph representation and algorithms, using dictionaries of inbound and outbound neighbour lists. domain/Iterator.py separates stateful BFS and DFS traversal from storage. Sample graph and coordinate files exercise file I/O; main.py runs the automated unittest suites. The implementation has no third-party runtime or test dependencies.
Implementation decisions
Neighbour lists keep the representation easy to inspect. Shortest-path routines use heapq and return the path, distance, and operation counters. A* validates vertex coordinates and checks that edge weights support its Euclidean heuristic. File parsing reports line-specific errors, and shortest-path routines reject negative weights even though the graph can store them.
Challenges
Algorithms need clear assumptions about direction, reachability, and weights. Tests cover graph operations and regression cases around these contracts. Performance also depends on the algorithm: the bridge routine repeats BFS for each edge, while clique and travelling-salesperson searches are exhaustive. Those routines are intended for understandable, small examples rather than large-scale workloads.
What I learned
The project connects abstract graph theory with concrete Python data structures, iterator state, and priority queues. It shows how representation choices affect both clarity and cost, and why an algorithm's preconditions belong in its API. Operation counters and automated tests make behavior easier to inspect beyond a single successful example.