Skip to content

USAGE.md

Latest commit

 

History

History
197 lines (127 loc) · 2.41 KB

USAGE.md

File metadata and controls

197 lines (127 loc) · 2.41 KB

Using graphkit from the Python CLI

This guide shows how to use graphkit interactively from the command line (using the Python REPL) or inside scripts.

Install first:

pip install pygraphkit

Start Python:

python

1. Working with Graphs

Import the core graph abstraction:

from graphkit import Graph

Undirected graph (default)

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

Directed graph

g = Graph(directed=True)
g.add_edge("A", "B", 5)

2. Shortest Path Algorithms

Dijkstra (non-negative weights)

dist = g.dijkstra(source)

Example:

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}

Bellman–Ford (negative weights allowed)

dist = g.bellman_ford(source)

If a negative cycle exists:

ValueError: Negative cycle detected

Floyd–Warshall (all-pairs shortest paths)

dist = g.floyd_warshall()

Access distances:

dist[u][v]

3. Minimum Spanning Tree (Undirected Graphs)

Kruskal’s Algorithm

mst, total_weight = g.kruskal()

Prim’s Algorithm

mst, total_weight = g.prim(start_node)

4. Graph Traversals

Breadth-First Search (BFS)

order = g.bfs(source)

Depth-First Search (DFS)

order = g.dfs(source)

5. Directed Acyclic Graphs (DAG)

Topological Sort

order = g.topological_sort()

If the graph contains a cycle:

ValueError: Graph contains a cycle

6. Strongly Connected Components

components = g.strongly_connected_components()

Each component is returned as a list of nodes.

7. Flow Networks (Max-Flow / Min-Cut)

Flow algorithms use a separate abstraction.

from graphkit.flow import FlowGraph

Maximum Flow (Dinic)

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

max_flow = g.max_flow(0, 2)

Minimum Cut

max_flow, (S, T) = g.max_flow_with_min_cut(0, 2)
  • S: vertices reachable from source in residual graph
  • T: remaining vertices

Notes

  • Nodes can be any hashable type (int, str, tuple, etc.)
  • Algorithms raise ValueError on invalid usage
  • The public API is stable starting from v1.0.0