graphkit

graphkit is a clean, reusable Python library providing standard graph algorithms with a unified and intuitive API.

It is designed for:

• Learning and revision of graph algorithms
• Interview and competitive programming preparation
• Real-world projects requiring graph processing
• Avoiding repeated reimplementation of well-known algorithms

---

✨ Features

• Simple Graph abstraction
• Object-oriented API
• Readable and canonical implementations
• Fully tested with CI
• No external runtime dependencies

Algorithms included

Shortest Path

• Dijkstra’s Algorithm
• Bellman–Ford Algorithm

Minimum Spanning Tree

• Kruskal’s Algorithm
• Prim’s Algorithm

Traversals

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

---

📦 Installation

pip install pygraphkit

For development:

pip install -e .

---

🚀 Quick Start

from graphkit import Graph

g = Graph()
g.add_edge(1, 2, 4)
g.add_edge(1, 3, 1)
g.add_edge(3, 2, 2)

print(g.dijkstra(1))

Output

{1: 0, 2: 3, 3: 1}

---

🧠 Core Concept

Graph Abstraction

All algorithms operate on a single Graph class.

Graph(directed=False)

• directed=False → undirected graph
• directed=True → directed graph

---

Adding edges

g.add_edge(u, v, weight)

• Default weight is 1
• For undirected graphs, edges are added both ways

---

Removing edges

Edges can be removed dynamically using remove_edge.

g.remove_edge(u, v)

Remove a specific weighted edge

g.remove_edge(u, v, weight)

Behavior

• For undirected graphs, both directions are removed
• For directed graphs, only u → v is removed
• If the edge does not exist, the operation is a no-op

---

📐 API Reference

Dijkstra’s Algorithm

Finds shortest paths from a source node (non-negative weights).

g.dijkstra(source)

Returns:

{node: shortest_distance}

---

Bellman–Ford Algorithm

Supports negative edge weights and detects negative cycles.

g.bellman_ford(source)

Raises:

ValueError: Negative cycle detected

---

Kruskal’s Algorithm

Computes the Minimum Spanning Tree (undirected graphs only).

mst, total_weight = g.kruskal()

Returns:

• mst: list of edges (u, v, w)
• total_weight: sum of MST edge weights

---

Prim’s Algorithm

Computes the Minimum Spanning Tree starting from a given node.

mst, total_weight = g.prim(start)

• Works on undirected graphs
• Uses a greedy priority-queue approach

---

Topological Sort

Returns a topological ordering of a directed acyclic graph (DAG).

order = g.topological_sort()

• Works only on directed graphs
• Raises ValueError if the graph contains a cycle

---

Floyd–Warshall Algorithm

Computes all-pairs shortest paths.

dist = g.floyd_warshall()

• Supports negative weights
• Raises ValueError if a negative cycle exists
• Returns a distance matrix as a nested dictionary

---

Strongly Connected Components (SCC)

Computes strongly connected components of a directed graph.

components = g.strongly_connected_components()

• Works only on directed graphs
• Uses kosaraju's algorithm
• Returns a list of node groups

---

Breadth-First Search (BFS)

g.bfs(source)

Returns traversal order as a list.

---

Depth-First Search (DFS)

g.dfs(source)

Returns traversal order as a list.

---

Maximum Flow (Dinic)

Computes the maximum flow in a directed flow network.

from graphkit.flow import FlowGraph

g = FlowGraph()
g.add_edge(0, 1, 3)
g.add_edge(1, 2, 2)

max_flow = g.max_flow(0, 2)

• Uses Dinic's algorithm
• Automatically manages residual edges
• Runs efficiently on large graphs

---

Minimum Cut (from Max Flow)

Returns the minimum cut after computing maximum flow.

from graphkit.flow import FlowGraph

g = FlowGraph()
g.add_edge(0, 1, 3)
g.add_edge(1, 2, 2)

max_flow, (S, T) = g.max_flow_with_min_cut(0, 2)

• Uses residual graph from Dinic's algorithm
• Returns (S, T) partition of vertices
• S contains the source

---

🧪 Testing

graphkit uses pytest for testing all core algorithms.

The test suite covers:

• Shortest path correctness
• Negative edge weights
• Negative cycle detection
• Disconnected graphs
• Error handling for invalid usage

Run tests locally:

pip install -e .
pytest -v

All tests must pass before a release is published.

---

📁 Project Structure

graphkit/
├── graphkit/
│   ├── graph.py
│   ├── algorithms/
│   ├── utils/
│   └── __init__.py
│
├── tests/
│   └── test_*.py
│
├── README.md
├── pyproject.toml
└── LICENSE

---

🎯 Design Philosophy

• One canonical implementation per algorithm
• Code clarity over cleverness
• No premature optimization
• Easy to rewrite during competitive programming
• Reusable in real-world systems

---

🛣️ Roadmap

Planned additions:

• Floyd–Warshall Algorithm
• Topological Sort
• Strongly Connected Components (Kosaraju / Tarjan)
• Maximum Flow algorithms (Edmonds–Karp, Dinic)
• Benchmarking utilities

---

🤝 Contributing

Contributions are welcome.

You can help by:

• Adding algorithms
• Improving test coverage
• Enhancing documentation

Please keep implementations:

• Clean
• Readable
• Well-tested

---

📜 License

MIT License

---

📘 Documentation

• Usage Guide
• API Reference