A clean Python implementation of graph data structures and algorithms using city networks. Features graph representations, traversal algorithms, and shortest path calculations.
- Graph Representations: Edge lists, adjacency lists, and adjacency matrices
- Traversal Algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS)
- Shortest Paths: Dijkstra's algorithm with path reconstruction
- Graph Analysis: Connectivity, cycle detection, and statistics
- Modern Python: Type hints, error handling, comprehensive tests
-
Clone and setup:
git clone <repository-url> cd Graph-Cities-1 ./setup_venv.sh
-
Run the demo:
source venv/bin/activate python examples/main.py
Graph-Cities/
βββ src/ # Core graph classes
β βββ Node.py # Node implementation
β βββ Edge.py # Edge implementation
β βββ Graph.py # Main graph class
βββ examples/ # Demo applications
β βββ main.py # Basic demo
β βββ demo_enhanced.py # Advanced features
β βββ graph_utils.py # Utility functions
βββ tests/ # Unit tests
β βββ test_graph.py # Core tests
β βββ test_algorithms.py # Algorithm tests
βββ setup_venv.sh # Setup script
from src.Graph import Graph # Create graph graph = Graph() graph.set_node_names(('New York', 'Los Angeles', 'Chicago')) # Add connections (weight, from, to) graph.insert_edge(2445, 0, 1) # NY β LA graph.insert_edge(713, 0, 2) # NY β Chicago graph.insert_edge(1745, 1, 2) # LA β Chicago # Traverse dfs_path = graph.dfs_names(0) # DFS from NY bfs_path = graph.bfs_names(0) # BFS from NY # Find shortest path path, distance = graph.shortest_path(0, 1) # NY to LA
# Run tests source venv/bin/activate pytest tests/ # Run specific test pytest tests/test_graph.py -v
The demo includes major world cities:
- Mountain View β San Francisco (51 miles)
- London β Berlin (932 miles)
- Shanghai β San Francisco (9,900 miles)
- And more realistic connections...
- Python 3.8+
- No external dependencies for core functionality
- pytest for testing (optional)
If you prefer manual setup:
# Create virtual environment python3 -m venv venv source venv/bin/activate # On Windows: venv\Scripts\activate # Install test dependencies (optional) pip install pytest # Run demo python examples/main.py