Graph Algorithms with Python

In this tutorial, we’ll explore how to implement and visualize various graph algorithms using Python. We’ll use NetworkX, a powerful library for creating, manipulating, and studying complex networks.

Setting Up Your Environment

First, let’s install the necessary packages:

pip install networkx matplotlib numpy pandas

Creating Graphs in Python

Now, let’s import the libraries and create a simple graph:

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# Create an undirected graph
G = nx.Graph()

# Add nodes
G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F'])

# Add edges
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('D', 'F'), ('E', 'F')]
G.add_edges_from(edges)

# Visualize the graph
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G, seed=42)  # positions for all nodes
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, edge_color='gray', linewidths=1, 
        font_size=15, font_weight='bold')
plt.title("Simple Undirected Graph")
plt.show()

The output would look something like this:

Breadth-First Search (BFS)

BFS explores all neighbors at the present depth before moving to vertices at the next depth level. Let’s implement and visualize BFS:

def bfs_visualization(G, start_node='A'):
    # Track the visited nodes
    visited = {node: False for node in G.nodes()}

    # BFS algorithm
    queue = [start_node]
    visited[start_node] = True

    # Track traversal order
    traversal_order = []

    while queue:
        current = queue.pop(0)
        traversal_order.append(current)

        for neighbor in G.neighbors(current):
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return traversal_order

# Run BFS
bfs_order = bfs_visualization(G, 'A')
print(f"BFS Traversal Order: {' -> '.join(bfs_order)}")

Output:

BFS Traversal Order: A -> B -> C -> D -> E -> F

Let’s visualize the BFS traversal:

def visualize_traversal(G, traversal):
    plt.figure(figsize=(12, 8))
    pos = nx.spring_layout(G, seed=42)

    # Draw the graph
    nx.draw_networkx_edges(G, pos, edge_color='gray', width=1, alpha=0.7)

    # Highlight the traversal path
    path_edges = [(traversal[i], traversal[i+1]) for i in range(len(traversal)-1) 
                  if G.has_edge(traversal[i], traversal[i+1])]

    # Draw nodes with different colors for visited nodes
    node_colors = ['#FF6B6B' if node == traversal[0] else
                   '#4ECDC4' if node in traversal[1:] else
                   '#F7FFF7' for node in G.nodes()]

    nx.draw_networkx_nodes(G, pos, node_size=500, node_color=node_colors)
    nx.draw_networkx_labels(G, pos, font_size=15, font_weight='bold')

    # Add a legend
    from matplotlib.lines import Line2D
    legend_elements = [
        Line2D([0], [0], marker='o', color='w', markerfacecolor='#FF6B6B', markersize=10, label='Start Node'),
        Line2D([0], [0], marker='o', color='w', markerfacecolor='#4ECDC4', markersize=10, label='Visited Nodes')
    ]
    plt.legend(handles=legend_elements)

    plt.title(f"{traversal[0]} to {traversal[-1]} Traversal")
    plt.axis('off')
    plt.show()

# Visualize BFS traversal
visualize_traversal(G, bfs_order)

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking:

def dfs_visualization(G, start_node='A'):
    # Track the visited nodes
    visited = {node: False for node in G.nodes()}

    # For tracking the traversal order
    traversal_order = []

    # DFS recursive function
    def dfs_recursive(node):
        visited[node] = True
        traversal_order.append(node)

        for neighbor in G.neighbors(node):
            if not visited[neighbor]:
                dfs_recursive(neighbor)

    # Start DFS
    dfs_recursive(start_node)
    return traversal_order

# Run DFS
dfs_order = dfs_visualization(G, 'A')
print(f"DFS Traversal Order: {' -> '.join(dfs_order)}")

Output:

DFS Traversal Order: A -> B -> D -> C -> E -> F

Let’s visualize the DFS traversal:

# Visualize DFS traversal
visualize_traversal(G, dfs_order)

Shortest Path - Dijkstra’s Algorithm

Now, let’s create a weighted graph and implement Dijkstra’s algorithm to find the shortest path:

# Create a weighted graph
weighted_G = nx.Graph()
weighted_edges = [
    ('A', 'B', 4), ('A', 'C', 2), ('B', 'D', 5),
    ('C', 'D', 1), ('C', 'E', 7), ('D', 'E', 3),
    ('D', 'F', 6), ('E', 'F', 2)
]

# Add weighted edges
weighted_G.add_weighted_edges_from(weighted_edges)

# Find the shortest path using Dijkstra's algorithm
shortest_path = nx.dijkstra_path(weighted_G, 'A', 'F')
path_length = nx.dijkstra_path_length(weighted_G, 'A', 'F')

print(f"Shortest Path from A to F: {' -> '.join(shortest_path)}")
print(f"Path Length: {path_length}")

Output:

Shortest Path from A to F: A -> C -> D -> E -> F
Path Length: 8

Let’s visualize the weighted graph and the shortest path:

def visualize_weighted_path(G, path):
    plt.figure(figsize=(10, 7))
    pos = nx.spring_layout(G, seed=42)

    # Draw the graph
    nx.draw_networkx_nodes(G, pos, node_size=500, node_color='lightblue')
    nx.draw_networkx_labels(G, pos, font_size=15, font_weight='bold')

    # Draw all edges with their weights
    nx.draw_networkx_edges(G, pos, width=1, alpha=0.5)

    # Get edge weights
    edge_labels = {(u,v): d['weight'] for u,v,d in G.edges(data=True)}
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=12)

    # Highlight the shortest path
    path_edges = list(zip(path, path[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, width=3, edge_color='r')

    # Highlight path nodes
    nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='#FF6B6B', node_size=500)

    plt.title(f"Shortest Path from {path[0]} to {path[-1]}")
    plt.axis('off')
    plt.show()

# Visualize the weighted graph with the shortest path
visualize_weighted_path(weighted_G, shortest_path)

Minimum Spanning Tree (MST)

A minimum spanning tree is a subset of edges that forms a tree including every vertex, where the total weight is minimized.

# Find the minimum spanning tree using Kruskal's algorithm
mst = nx.minimum_spanning_tree(weighted_G)

# Get the total weight of the MST
mst_weight = sum(mst[u][v]['weight'] for u, v in mst.edges())

print(f"MST Edges: {list(mst.edges())}")
print(f"Total MST Weight: {mst_weight}")

Output:

MST Edges: [('A', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F'), ('A', 'B')]
Total MST Weight: 12

Let’s visualize the MST:

def visualize_mst(G, mst):
    plt.figure(figsize=(10, 7))
    pos = nx.spring_layout(G, seed=42)

    # Draw the original graph - faded
    nx.draw_networkx_nodes(G, pos, node_size=500, node_color='lightblue', alpha=0.5)
    nx.draw_networkx_edges(G, pos, width=1, alpha=0.2)

    # Draw MST - highlighted
    nx.draw_networkx_nodes(G, pos, node_size=500, node_color='lightblue')
    nx.draw_networkx_labels(G, pos, font_size=15, font_weight='bold')
    nx.draw_networkx_edges(G, pos, edgelist=list(mst.edges()), width=3, edge_color='red')

    # Get edge weights for MST
    edge_labels = {(u,v): G[u][v]['weight'] for u,v in mst.edges()}
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=12)

    plt.title("Minimum Spanning Tree (MST)")
    plt.axis('off')
    plt.show()

# Visualize the MST
visualize_mst(weighted_G, mst)

Interactive Example: Graph Centrality

Let’s explore the concept of centrality in graphs. Centrality measures help identify the most important vertices within a graph.

# Create a larger graph for centrality analysis
social_graph = nx.karate_club_graph()

# Calculate various centrality measures
degree_centrality = nx.degree_centrality(social_graph)
betweenness_centrality = nx.betweenness_centrality(social_graph)
closeness_centrality = nx.closeness_centrality(social_graph)
eigenvector_centrality = nx.eigenvector_centrality(social_graph)

# Find nodes with highest centrality
top_degree = sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:3]
top_betweenness = sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:3]
top_closeness = sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:3]
top_eigenvector = sorted(eigenvector_centrality.items(), key=lambda x: x[1], reverse=True)[:3]

print("Top 3 nodes by degree centrality:", top_degree)
print("Top 3 nodes by betweenness centrality:", top_betweenness)
print("Top 3 nodes by closeness centrality:", top_closeness)
print("Top 3 nodes by eigenvector centrality:", top_eigenvector)

Output:

Top 3 nodes by degree centrality: [(33, 0.5151515151515151), (0, 0.48484848484848486), (2, 0.3636363636363636)]
Top 3 nodes by betweenness centrality: [(0, 0.43763528138528146), (33, 0.3047619047619048), (2, 0.1439393939393939)]
Top 3 nodes by closeness centrality: [(33, 0.6071428571428571), (0, 0.5357142857142857), (2, 0.4583333333333333)]
Top 3 nodes by eigenvector centrality: [(33, 0.3668083400627868), (2, 0.3636095871213352), (0, 0.3576599918308433)]

Let’s visualize these centrality measures:

def visualize_centrality(G, centrality_dict, title):
    plt.figure(figsize=(12, 8))
    pos = nx.spring_layout(G, seed=5)

    # Get centrality values
    centrality_values = list(centrality_dict.values())

    # Map centrality to node size
    node_sizes = [v * 1000 + 100 for v in centrality_values]

    # Create a color map
    nodes = nx.draw_networkx_nodes(G, pos, node_size=node_sizes, 
                                   node_color=centrality_values, 
                                   cmap=plt.cm.plasma)
    nx.draw_networkx_edges(G, pos, alpha=0.3)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color='black')

    # Add a color bar
    plt.colorbar(nodes)
    plt.title(f"{title} Centrality")
    plt.axis('off')
    plt.show()

# Visualize different centrality measures
visualize_centrality(social_graph, degree_centrality, "Degree")
visualize_centrality(social_graph, betweenness_centrality, "Betweenness")

Conclusion

In this tutorial, we’ve explored several fundamental graph algorithms and their implementations in Python using the NetworkX library. We’ve covered:

Graph creation and visualization
Traversal algorithms (BFS and DFS)
Shortest path finding with Dijkstra’s algorithm
Minimum spanning tree using Kruskal’s algorithm
Centrality measures for graph analysis

These algorithms form the foundation of many applications in network analysis, routing, social network analysis, and more.

Next Steps

For further exploration, consider looking into:

Community detection algorithms
Graph embedding techniques
Dynamic graph algorithms
Specialized algorithms for directed graphs

And don’t forget to experiment with our interactive graph playground to visualize these concepts in action!

References

NetworkX Documentation
Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.

Graph Algorithms with Python - A Practical Tutorial

Graph Algorithms with Python

Setting Up Your Environment

Creating Graphs in Python

Breadth-First Search (BFS)

Depth-First Search (DFS)

Shortest Path - Dijkstra’s Algorithm

Minimum Spanning Tree (MST)

Interactive Example: Graph Centrality

Conclusion

Next Steps

References