Skip to content

Adjacency Matrix Graph

An adjacency matrix graph stores vertex connections in a 2D matrix where entry (i,j) represents the edge weight between vertex i and vertex j. This representation provides O(1) edge lookup but uses O(V²) space regardless of the actual number of edges.

Overview

The AdjacencyMatrixGraph provides a graph implementation using a 2D matrix for fast edge lookup operations. Each matrix cell represents a potential edge between two vertices, making it ideal for dense graphs and applications requiring frequent edge existence queries.

Features

  • Fast edge lookup - O(1) time to check if an edge exists
  • Fast edge operations - O(1) insertion, deletion, and weight retrieval
  • Fixed maximum size - pre-allocated matrix with configurable maximum vertices
  • Directed and undirected - supports both graph types with automatic symmetry
  • Weighted edges - each edge can have an associated weight or cost
  • Dense graph efficient - optimal space usage when most vertex pairs have edges
  • Simple implementation - straightforward matrix operations and indexing
  • Mathematical operations - enables matrix-based graph algorithms

Time Complexities

Operation Time Complexity Description
Add Vertex O(1)* Constant time until max_vertices limit
Add Edge O(1) Direct matrix assignment
Remove Vertex O(V) Simplified implementation - clears row/column
Remove Edge O(1) Direct matrix assignment
Check Edge O(1) Direct matrix lookup
Get Neighbors O(V) Must scan entire row
DFS/BFS O(V²) Must check all matrix entries
Degree O(V) Must scan row/column
Is Connected O(V²) Matrix-based traversal
Has Cycle O(V²) Matrix-based DFS

Space Complexity: O(V²) where V is max_vertices (fixed size)

Basic Usage

Creating and Initializing

from algo.data_structs.graphs import AdjacencyMatrixGraph

# Create empty undirected graph with default max vertices (100)
graph = AdjacencyMatrixGraph()
print(graph.directed)          # False
print(graph.max_vertices)      # 100
print(graph.vertex_count())    # 0
print(graph.edge_count())      # 0

# Create directed graph with custom max vertices
directed_graph = AdjacencyMatrixGraph(directed=True, max_vertices=50)
print(directed_graph.directed) # True
print(directed_graph.max_vertices)  # 50

# Create small graph for dense networks
small_graph = AdjacencyMatrixGraph(max_vertices=10)
print(small_graph.max_vertices)     # 10

Understanding Graph Types

# Undirected graph: matrix is symmetric
undirected = AdjacencyMatrixGraph(directed=False)
undirected.add_edge('A', 'B', 5.0)
print(undirected.has_edge('A', 'B'))  # True
print(undirected.has_edge('B', 'A'))  # True (symmetric)
print(undirected.get_edge_weight('A', 'B'))  # 5.0
print(undirected.get_edge_weight('B', 'A'))  # 5.0

# Directed graph: matrix can be asymmetric
directed = AdjacencyMatrixGraph(directed=True)
directed.add_edge('A', 'B', 3.0)
print(directed.has_edge('A', 'B'))    # True
print(directed.has_edge('B', 'A'))    # False (not symmetric)
print(directed.get_edge_weight('A', 'B'))  # 3.0
print(directed.get_edge_weight('B', 'A'))  # None

Adding Vertices and Edges

# Add vertices explicitly (optional - added automatically with edges)
graph = AdjacencyMatrixGraph(max_vertices=5)
graph.add_vertex('Server1')
graph.add_vertex('Server2')
graph.add_vertex('Server3')

print(graph.get_vertices())    # {'Server1', 'Server2', 'Server3'}
print(graph.vertex_count())    # 3

# Add weighted edges (latency in ms)
graph.add_edge('Server1', 'Server2', 100)  # 100ms latency
graph.add_edge('Server2', 'Server3', 50)   # 50ms latency
graph.add_edge('Server1', 'Server3', 200)  # 200ms latency

print(graph.edge_count())      # 3
print(graph.get_edge_weight('Server1', 'Server2'))  # 100

# Vertices are added automatically when creating edges
auto_graph = AdjacencyMatrixGraph(max_vertices=10)
auto_graph.add_edge('A', 'B', 1.0)
print(auto_graph.get_vertices())  # {'A', 'B'}

# Cannot exceed max_vertices limit
try:
    for i in range(15):  # Try to add more than max_vertices
        auto_graph.add_vertex(f"Node{i}")
    print(f"Added {auto_graph.vertex_count()} vertices")  # Limited to max_vertices
except:
    print("Cannot exceed max_vertices limit")

Viewing Graph Information

# Fast edge existence checks (O(1))
print(graph.has_edge('Server1', 'Server2'))     # True
print(graph.has_edge('Server2', 'Server1'))     # True (undirected)
print(graph.has_edge('Server1', 'Server4'))     # False

# Fast edge weight retrieval (O(1))
latency = graph.get_edge_weight('Server2', 'Server3')
print(f"Latency: {latency}ms")                  # Latency: 50ms

# Get all edges
edges = graph.get_edges()
for from_server, to_server, latency in edges:
    print(f"{from_server} → {to_server}: {latency}ms")

# Get neighbors (O(V) operation - scans matrix row)
neighbors = graph.get_neighbors('Server1')
for neighbor, latency in neighbors:
    print(f"Server1 to {neighbor}: {latency}ms")

Removing Elements

# Remove edges (O(1) operation)
graph.add_edge('A', 'B', 5.0)
graph.add_edge('A', 'C', 3.0)
print(graph.has_edge('A', 'B'))  # True

graph.remove_edge('A', 'B')
print(graph.has_edge('A', 'B'))  # False
print(graph.has_edge('A', 'C'))  # True (other edges preserved)

# Remove vertices (O(V) operation - clears matrix row/column)
graph.add_edge('X', 'Y', 1.0)
graph.add_edge('Y', 'Z', 2.0)
graph.add_edge('X', 'Z', 3.0)
print(graph.vertex_count())      # 3
print(graph.edge_count())        # 3

graph.remove_vertex('Y')
print(graph.vertex_count())      # 2
print(graph.edge_count())        # 1 (only X-Z remains)
print(graph.has_edge('X', 'Z'))  # True

Graph Analysis

Degree Calculations

# Undirected graph degrees (O(V) to scan row)
undirected = AdjacencyMatrixGraph(directed=False, max_vertices=10)
undirected.add_edge('A', 'B')
undirected.add_edge('A', 'C')
undirected.add_edge('B', 'C')

print(f"A's connections: {undirected.degree('A')}")  # 2
print(f"B's connections: {undirected.degree('B')}")  # 2
print(f"C's connections: {undirected.degree('C')}")  # 2

# Directed graph degrees (O(V) each to scan row/column)
directed = AdjacencyMatrixGraph(directed=True, max_vertices=10)
directed.add_edge('A', 'B')
directed.add_edge('A', 'C')
directed.add_edge('D', 'A')

print(f"A out-degree: {directed.out_degree('A')}")  # 2 (outgoing edges)
print(f"A in-degree: {directed.in_degree('A')}")    # 1 (incoming edges)
print(f"Total degree: {directed.degree('A')}")      # 3 (in + out)

Connectivity and Structure Analysis

# Check if graph is connected (undirected graphs)
connected_graph = AdjacencyMatrixGraph(directed=False, max_vertices=10)
connected_graph.add_edge('A', 'B')
connected_graph.add_edge('B', 'C')
connected_graph.add_edge('C', 'D')
print(f"Connected: {connected_graph.is_connected()}")  # True

disconnected_graph = AdjacencyMatrixGraph(directed=False, max_vertices=10)
disconnected_graph.add_edge('A', 'B')
disconnected_graph.add_vertex('C')  # Isolated vertex
print(f"Connected: {disconnected_graph.is_connected()}")  # False

# Cycle detection
acyclic = AdjacencyMatrixGraph(directed=False, max_vertices=10)
acyclic.add_edge('A', 'B')
acyclic.add_edge('B', 'C')
print(f"Has cycle: {acyclic.has_cycle()}")  # False

cyclic = AdjacencyMatrixGraph(directed=False, max_vertices=10)
cyclic.add_edge('A', 'B')
cyclic.add_edge('B', 'C')
cyclic.add_edge('C', 'A')
print(f"Has cycle: {cyclic.has_cycle()}")  # True

# Topological sorting (for directed acyclic graphs)
dag = AdjacencyMatrixGraph(directed=True, max_vertices=10)
dag.add_edge('compile', 'link')
dag.add_edge('test', 'compile')
dag.add_edge('package', 'test')

if not dag.has_cycle():
    topo_order = dag.topological_sort()
    print(f"Build order: {topo_order}")
    # Output: ['package', 'test', 'compile', 'link'] (or valid permutation)

Graph Traversal

Depth-First Search (DFS)

# Create a sample graph
graph = AdjacencyMatrixGraph(max_vertices=10)
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'E')
graph.add_edge('D', 'F')
graph.add_edge('E', 'F')

# DFS with matrix representation (O(V²) complexity)
dfs_result = graph.dfs('A')
print(f"DFS from A: {dfs_result}")
# Output: ['A', 'B', 'D', 'F', 'E', 'C'] (or similar order)

# Matrix DFS can find connected components
all_vertices = graph.get_vertices()
visited = set()
components = []

for vertex in all_vertices:
    if vertex not in visited:
        component = graph.dfs(vertex)
        components.append(component)
        visited.update(component)

print(f"Connected components: {len(components)}")

Breadth-First Search (BFS)

# BFS with matrix representation (O(V²) complexity)
bfs_result = graph.bfs('A')
print(f"BFS from A: {bfs_result}")
# Output: ['A', 'B', 'C', 'D', 'E', 'F'] (level order)

# BFS finds shortest path (unweighted)
def shortest_path_matrix_bfs(graph, start, end):
    """Find shortest path using BFS on matrix graph."""
    if start == end:
        return [start]

    from collections import deque
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        vertex, path = queue.popleft()

        # Matrix graphs return neighbors as list of (neighbor, weight) tuples
        for neighbor, _ in graph.get_neighbors(vertex):
            if neighbor == end:
                return path + [neighbor]

            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path found

# Find shortest path
path = shortest_path_matrix_bfs(graph, 'A', 'F')
print(f"Shortest path A to F: {path}")

Basic Graph Creation

from algo.data_structs.graphs import AdjacencyMatrixGraph

# Create a directed graph with maximum 10 vertices
graph = AdjacencyMatrixGraph(directed=True, max_vertices=10)

# Add vertices and edges for a small network
graph.add_edge('Server1', 'Server2', 100)  # 100ms latency
graph.add_edge('Server2', 'Server3', 50)   # 50ms latency
graph.add_edge('Server1', 'Server3', 200)  # 200ms latency

# Fast edge lookups
print(f"Direct connection S1->S3: {graph.has_edge('Server1', 'Server3')}")
print(f"Latency S1->S2: {graph.get_edge_weight('Server1', 'Server2')}ms")

# Check vertex degrees
print(f"Server1 outgoing connections: {graph.out_degree('Server1')}")
print(f"Server3 incoming connections: {graph.in_degree('Server3')}")

Dense Graph Example

# Model a complete tournament where every team plays every other team
tournament = AdjacencyMatrixGraph(directed=True, max_vertices=8)

teams = ['Team A', 'Team B', 'Team C', 'Team D', 'Team E']

# Add match results (1 = win, 0 = loss)
match_results = [
    ('Team A', 'Team B', 1), ('Team B', 'Team A', 0),
    ('Team A', 'Team C', 1), ('Team C', 'Team A', 0),
    ('Team A', 'Team D', 0), ('Team D', 'Team A', 1),
    ('Team B', 'Team C', 1), ('Team C', 'Team B', 0),
    ('Team B', 'Team D', 0), ('Team D', 'Team B', 1),
    ('Team C', 'Team D', 1), ('Team D', 'Team C', 0),
]

for team1, team2, result in match_results:
    tournament.add_edge(team1, team2, result)

# Quick lookup of any match result (O(1))
print(f"Team A beat Team B: {tournament.get_edge_weight('Team A', 'Team B') == 1}")
print(f"Team D beat Team A: {tournament.get_edge_weight('Team D', 'Team A') == 1}")

# Calculate win statistics
print("\nTournament Results:")
for team in teams:
    if team in tournament.get_vertices():
        wins = 0
        games = 0
        for opponent in teams:
            if opponent != team and tournament.has_edge(team, opponent):
                games += 1
                if tournament.get_edge_weight(team, opponent) == 1:
                    wins += 1

        win_percentage = (wins / games * 100) if games > 0 else 0
        print(f"{team}: {wins}/{games} wins ({win_percentage:.1f}%)")

Network Connectivity Analysis

# Model a computer network with known topology
network = AdjacencyMatrixGraph(directed=False, max_vertices=6)

# Add network connections with bandwidth (Mbps)
connections = [
    ('Router1', 'Router2', 1000),  # Gigabit link
    ('Router1', 'Router3', 100),   # Fast ethernet
    ('Router2', 'Router4', 1000),  # Gigabit link
    ('Router2', 'Router5', 100),   # Fast ethernet
    ('Router3', 'Router4', 10),    # Legacy connection
    ('Router4', 'Router5', 10),    # Legacy connection
]

for router1, router2, bandwidth in connections:
    network.add_edge(router1, router2, bandwidth)

# Analyze network connectivity
print(f"Network is connected: {network.is_connected()}")
print(f"Network has redundant paths: {network.has_cycle()}")

# Find bottlenecks (O(1) edge lookups)
print("\nNetwork Analysis:")
routers = list(network.get_vertices())
for i, router1 in enumerate(routers):
    for router2 in routers[i+1:]:
        if network.has_edge(router1, router2):
            bandwidth = network.get_edge_weight(router1, router2)
            if bandwidth <= 10:
                print(f"BOTTLENECK: {router1} ↔ {router2}: {bandwidth} Mbps")
            else:
                print(f"Good link: {router1} ↔ {router2}: {bandwidth} Mbps")

# Check redundancy for each router
print("\nRedundancy Analysis:")
for router in network.get_vertices():
    connections = len(network.get_neighbors(router))
    if connections == 1:
        print(f"SINGLE POINT OF FAILURE: {router} has only 1 connection")
    else:
        print(f"{router} has {connections} connections (good redundancy)")

Matrix-Based Algorithms

# Create a weighted graph for shortest path analysis using Floyd-Warshall
city_network = AdjacencyMatrixGraph(directed=True, max_vertices=5)

# Add distances between cities
distances = [
    ('New York', 'Chicago', 790),
    ('New York', 'Miami', 1280),
    ('Chicago', 'Atlanta', 605),
    ('Chicago', 'Denver', 920),
    ('Miami', 'Atlanta', 640),
    ('Atlanta', 'Denver', 1200),
]

for city1, city2, distance in distances:
    city_network.add_edge(city1, city2, distance)

print(f"Direct routes: {city_network.edge_count()}")

# Matrix representation enables efficient all-pairs shortest path algorithms
# (This would typically use the Floyd-Warshall algorithm)
print("\nDirect flight distances:")
cities = list(city_network.get_vertices())
for city1 in cities:
    for city2 in cities:
        if city1 != city2 and city_network.has_edge(city1, city2):
            distance = city_network.get_edge_weight(city1, city2)
            print(f"{city1} → {city2}: {distance} miles")

# Check connectivity matrix properties
print(f"\nCities: {len(cities)}")
print(f"Possible routes: {len(cities) * (len(cities) - 1)}")
print(f"Actual routes: {city_network.edge_count()}")
print(f"Route density: {city_network.edge_count() / (len(cities) * (len(cities) - 1)) * 100:.1f}%")

Working with Different Types

Small Fixed Networks

# Perfect for small, known-size networks
small_net = AdjacencyMatrixGraph(max_vertices=5)

# Add connections between numbered nodes
for i in range(1, 5):
    for j in range(i+1, 5):
        small_net.add_edge(i, j, i * j)  # Weight based on product

# Fast analysis of complete connectivity
print(f"Network density: {small_net.edge_count()}/{5*4//2} = {small_net.edge_count()/(5*4//2)*100:.0f}%")

Graph with Self-Loops

# Matrix graphs can easily handle self-loops
self_loop_graph = AdjacencyMatrixGraph(max_vertices=5)
self_loop_graph.add_edge('A', 'A', 1.0)  # Self-loop
self_loop_graph.add_edge('A', 'B', 2.0)

print(f"A has self-loop: {self_loop_graph.has_edge('A', 'A')}")
print(f"Self-loop weight: {self_loop_graph.get_edge_weight('A', 'A')}")

When to Use Adjacency Matrix

Ideal Use Cases

  • Dense graphs - when the number of edges approaches V²
  • Frequent edge queries - when you often need to check if edges exist
  • Fixed graph size - when you know the maximum number of vertices in advance
  • Mathematical operations - when you need to perform matrix operations on the graph
  • All-pairs algorithms - when using algorithms like Floyd-Warshall
  • Game state spaces - when modeling state transitions in games
  • Small networks - when the vertex count is small and known

Consider Alternatives When

  • Sparse graphs - when E << V², matrices waste significant memory
  • Large graphs - when V is very large, V² space becomes prohibitive
  • Dynamic size - when the number of vertices changes frequently
  • Memory constraints - when memory usage is a primary concern
  • Unknown size - when you don't know the maximum vertex count

Memory Usage

The adjacency matrix always uses O(V²) space: - Fixed size - uses max_vertices² entries regardless of actual edges - Space efficient for dense graphs - when most entries are used - Space inefficient for sparse graphs - many entries remain unused

Memory Examples

For different graph sizes: - 10 vertices: 100 matrix entries (manageable) - 100 vertices: 10,000 matrix entries (reasonable for dense graphs) - 1,000 vertices: 1,000,000 matrix entries (large but feasible) - 10,000 vertices: 100,000,000 matrix entries (very large - use with caution)

Memory vs Edge Density

# Memory efficiency depends on edge density
def analyze_memory_efficiency(max_vertices, actual_edges):
    matrix_entries = max_vertices * max_vertices
    list_entries = actual_edges * 2  # Approximate for adjacency list

    if actual_edges > matrix_entries // 4:
        return "Matrix more efficient"
    else:
        return "List more efficient"

# Examples
print(analyze_memory_efficiency(100, 5000))    # "Matrix more efficient"
print(analyze_memory_efficiency(100, 500))     # "List more efficient"
print(analyze_memory_efficiency(1000, 50000))  # "List more efficient"

Configuration and Performance Tips

Choosing Maximum Vertices

# Conservative sizing for memory efficiency
small_network = AdjacencyMatrixGraph(max_vertices=10)    # For small, known networks
medium_network = AdjacencyMatrixGraph(max_vertices=100)  # For medium networks
large_network = AdjacencyMatrixGraph(max_vertices=1000)  # Use carefully

# Check memory implications
import sys
matrix_size = 1000 * 1000 * sys.getsizeof(0.0)  # Approximate matrix memory
print(f"1000x1000 matrix uses approximately {matrix_size // 1024 // 1024} MB")

Optimization Strategies

# For frequent edge existence checks, matrix is optimal
def check_all_possible_edges(graph, vertices):
    """Efficiently check all possible edges with matrix."""
    edge_count = 0
    for v1 in vertices:
        for v2 in vertices:
            if v1 != v2 and graph.has_edge(v1, v2):  # O(1) for matrix
                edge_count += 1
    return edge_count

# This is much more efficient with matrix than adjacency list
vertices = ['A', 'B', 'C', 'D', 'E']
total_edges = check_all_possible_edges(network, vertices)
print(f"Total edges found: {total_edges}")

Integration with Algorithms

# Matrix graphs work well with matrix-based algorithms
def graph_to_adjacency_matrix(graph):
    """Convert graph to raw matrix for numerical algorithms."""
    vertices = list(graph.get_vertices())
    n = len(vertices)
    matrix = [[0 for _ in range(n)] for _ in range(n)]

    for i, v1 in enumerate(vertices):
        for j, v2 in enumerate(vertices):
            if graph.has_edge(v1, v2):
                matrix[i][j] = graph.get_edge_weight(v1, v2)

    return matrix, vertices

# Use with numerical libraries
matrix, vertex_names = graph_to_adjacency_matrix(city_network)
print(f"Matrix dimensions: {len(matrix)}x{len(matrix[0])}")
print(f"Vertex mapping: {vertex_names}")

API Reference

Adjacency matrix graph implementation.

This module provides a graph representation using adjacency matrices, supporting both directed and undirected graphs with weighted edges.

AdjacencyMatrixGraph(directed=False, max_vertices=100)

Bases: Graph

Graph implementation using adjacency matrix.

Supports both directed and undirected graphs with weighted edges. Note: This implementation is more memory-intensive but provides O(1) edge lookup.

__repr__()

Detailed representation for debugging.

__str__()

String representation of the graph.

add_edge(from_vertex, to_vertex, weight=1.0)

Add an edge between two vertices.

add_vertex(vertex)

Add a vertex to the graph.

bfs(start_vertex)

Perform breadth-first search starting from a vertex.

degree(vertex)

Get the degree of a vertex.

dfs(start_vertex, visited=None)

Perform depth-first search starting from a vertex.

edge_count()

Get the number of edges in the graph.

get_edge_weight(from_vertex, to_vertex)

Get the weight of an edge between two vertices.

get_edges()

Get all edges in the graph as (from, to, weight) tuples.

get_neighbors(vertex)

Get all neighbors of a vertex with their edge weights.

get_vertices()

Get all vertices in the graph.

has_cycle()

Check if the graph has a cycle.

has_edge(from_vertex, to_vertex)

Check if there's an edge between two vertices.

in_degree(vertex)

Get the in-degree of a vertex (for directed graphs).

is_connected()

Check if the graph is connected (for undirected graphs).

out_degree(vertex)

Get the out-degree of a vertex (for directed graphs).

remove_edge(from_vertex, to_vertex)

Remove an edge between two vertices.

remove_vertex(vertex)

Remove a vertex and all its edges from the graph.

topological_sort()

Perform topological sorting (for directed acyclic graphs).

vertex_count()

Get the number of vertices in the graph.