Adjacency List Graph

An adjacency list graph stores each vertex along with a list of its neighboring vertices and edge weights. This representation is particularly efficient for sparse graphs where the number of edges is much smaller than the maximum possible number of edges.

Overview

The AdjacencyListGraph provides a memory-efficient graph implementation using adjacency lists to store vertex connections. Each vertex maintains a list of its neighbors and associated edge weights, making it ideal for sparse graphs and applications requiring dynamic vertex management.

Features

Memory efficient - uses O(V + E) space, optimal for sparse graphs
Dynamic sizing - no fixed limit on the number of vertices
Directed and undirected - supports both graph types with automatic edge management
Weighted edges - each edge can have an associated weight or cost
Fast neighbor access - O(1) time to get all neighbors of a vertex
Graph analysis - connectivity, cycle detection, topological sorting
Traversal algorithms - depth-first search (DFS) and breadth-first search (BFS)
Type safe - generic implementation supporting any vertex type

Time Complexities

Operation	Time Complexity	Description
Add Vertex	O(1)	Constant time insertion
Add Edge	O(1)	Appends to adjacency list
Remove Vertex	O(V + E)	Must check all adjacency lists
Remove Edge	O(V)	Must search through adjacency list
Check Edge	O(V)	Must search through adjacency list
Get Neighbors	O(1)	Direct access to adjacency list
DFS/BFS	O(V + E)	Visits all vertices and edges
Degree	O(1)	Direct list length
Is Connected	O(V + E)	Single DFS/BFS traversal
Has Cycle	O(V + E)	DFS with cycle detection

Space Complexity: O(V + E) where V is vertices and E is edges

Basic Usage

Creating and Initializing

from algo.data_structs.graphs import AdjacencyListGraph

# Create empty undirected graph (default)
graph = AdjacencyListGraph()
print(graph.directed)          # False
print(graph.vertex_count())    # 0
print(graph.edge_count())      # 0

# Create directed graph
directed_graph = AdjacencyListGraph(directed=True)
print(directed_graph.directed) # True

# Graph is generic - can work with any vertex type
str_graph = AdjacencyListGraph()
int_graph = AdjacencyListGraph(directed=True)

Understanding Graph Types

# Undirected graph: edges work both ways
undirected = AdjacencyListGraph(directed=False)
undirected.add_edge('A', 'B')
print(undirected.has_edge('A', 'B'))  # True
print(undirected.has_edge('B', 'A'))  # True (bidirectional)

# Directed graph: edges have direction
directed = AdjacencyListGraph(directed=True)
directed.add_edge('A', 'B')
print(directed.has_edge('A', 'B'))    # True
print(directed.has_edge('B', 'A'))    # False (unidirectional)

Adding Vertices and Edges

# Add vertices explicitly (optional - added automatically with edges)
graph = AdjacencyListGraph()
graph.add_vertex('New York')
graph.add_vertex('Chicago')
graph.add_vertex('Los Angeles')

print(graph.get_vertices())    # {'New York', 'Chicago', 'Los Angeles'}
print(graph.vertex_count())    # 3

# Add weighted edges (distances in miles)
graph.add_edge('New York', 'Chicago', 790)
graph.add_edge('Chicago', 'Los Angeles', 2015)
graph.add_edge('New York', 'Los Angeles', 2445)

print(graph.edge_count())      # 3
print(graph.get_edge_weight('New York', 'Chicago'))  # 790

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

Viewing Graph Information

# Check edge existence
print(graph.has_edge('New York', 'Chicago'))     # True
print(graph.has_edge('Chicago', 'New York'))     # True (undirected)
print(graph.has_edge('New York', 'Miami'))       # False

# Get edge weights
weight = graph.get_edge_weight('Chicago', 'Los Angeles')
print(f"Distance: {weight} miles")               # Distance: 2015 miles

# Get all edges
edges = graph.get_edges()
for from_city, to_city, distance in edges:
    print(f"{from_city} → {to_city}: {distance} miles")

# Get neighbors of a vertex (fast O(1) operation)
neighbors = graph.get_neighbors('Chicago')
for neighbor, distance in neighbors:
    print(f"Chicago to {neighbor}: {distance} miles")

Removing Elements

# Remove edges
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
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 (removes all connected edges)
graph.add_edge('X', 'Y')
graph.add_edge('Y', 'Z')
graph.add_edge('X', 'Z')
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
undirected = AdjacencyListGraph(directed=False)
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
directed = AdjacencyListGraph(directed=True)
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 = AdjacencyListGraph(directed=False)
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 = AdjacencyListGraph(directed=False)
disconnected_graph.add_edge('A', 'B')
disconnected_graph.add_vertex('C')  # Isolated vertex
print(f"Connected: {disconnected_graph.is_connected()}")  # False

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

cyclic = AdjacencyListGraph(directed=False)
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 = AdjacencyListGraph(directed=True)
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 = AdjacencyListGraph()
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 explores deeply before backtracking
dfs_result = graph.dfs('A')
print(f"DFS from A: {dfs_result}")
# Output: ['A', 'B', 'D', 'F', 'E', 'C'] (or similar order)

# 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 explores level by level
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_bfs(graph, start, end):
    """Find shortest path using BFS."""
    if start == end:
        return [start]

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

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

        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_bfs(graph, 'A', 'F')
print(f"Shortest path A to F: {path}")

Practical Examples

# Model friendships in a social network
social_network = AdjacencyListGraph(directed=False)

# Add friendships
friendships = [
    ('Alice', 'Bob'), ('Alice', 'Carol'), ('Bob', 'David'),
    ('Carol', 'Eve'), ('David', 'Eve'), ('Eve', 'Frank'),
    ('Frank', 'Grace'), ('Grace', 'Henry')
]

for person1, person2 in friendships:
    social_network.add_edge(person1, person2)

# Analyze the network
print(f"People in network: {len(social_network.get_vertices())}")
print(f"Friendships: {social_network.edge_count()}")

# Find most connected person
max_connections = 0
most_popular = None
for person in social_network.get_vertices():
    connections = social_network.degree(person)
    if connections > max_connections:
        max_connections = connections
        most_popular = person

print(f"Most popular person: {most_popular} ({max_connections} friends)")

# Check if everyone is connected
print(f"Network is fully connected: {social_network.is_connected()}")

# Find Alice's network reach
alice_reach = social_network.bfs('Alice')
print(f"Alice can reach {len(alice_reach)} people: {alice_reach}")

Transportation Network

# Model a transportation system with costs
transport = AdjacencyListGraph(directed=True)

# Add routes with costs (dollars)
routes = [
    ('Airport', 'Downtown', 25.0),   # Taxi
    ('Airport', 'Subway', 3.0),      # Airport express
    ('Subway', 'Downtown', 2.5),     # Subway fare
    ('Downtown', 'Hotel', 10.0),     # Short taxi ride
    ('Subway', 'University', 2.5),   # Subway fare
    ('University', 'Hotel', 8.0),    # Bus fare
    ('Downtown', 'Mall', 5.0),       # Bus fare
    ('Mall', 'Hotel', 12.0)          # Taxi
]

for origin, destination, cost in routes:
    transport.add_edge(origin, destination, cost)

# Analyze the network
print(f"Locations: {transport.get_vertices()}")
print(f"Routes: {transport.edge_count()}")

# Find options from Airport
airport_options = transport.get_neighbors('Airport')
print("From Airport:")
for destination, cost in airport_options:
    print(f"  → {destination}: ${cost}")

# Check accessibility
downtown_reachable = transport.bfs('Airport')
print(f"Reachable from Airport: {downtown_reachable}")

# Analyze degrees
for location in transport.get_vertices():
    in_deg = transport.in_degree(location)
    out_deg = transport.out_degree(location)
    print(f"{location}: {in_deg} incoming, {out_deg} outgoing routes")

Project Dependencies

# Model software project dependencies
dependencies = AdjacencyListGraph(directed=True)

# Define build dependencies (A depends on B means B → A)
deps = [
    ('database', 'models'),      # models depend on database
    ('models', 'services'),      # services depend on models
    ('services', 'controllers'), # controllers depend on services
    ('controllers', 'views'),    # views depend on controllers
    ('models', 'tests'),         # tests depend on models
    ('services', 'tests'),       # tests also depend on services
    ('config', 'database'),      # database depends on config
    ('config', 'services')       # services also depend on config
]

for dependency, dependent in deps:
    dependencies.add_edge(dependency, dependent)

# Check for circular dependencies
if dependencies.has_cycle():
    print("ERROR: Circular dependency detected!")
else:
    print("✓ No circular dependencies found")

    # Get build order
    build_order = dependencies.topological_sort()
    print(f"Build order: {' → '.join(build_order)}")

# Analyze dependencies
print("\nDependency analysis:")
for component in dependencies.get_vertices():
    depends_on = dependencies.in_degree(component)
    depended_by = dependencies.out_degree(component)
    print(f"{component}: depends on {depends_on}, depended by {depended_by}")

# Model a simple maze
maze = AdjacencyListGraph(directed=False)

# Define maze layout (connections between rooms)
maze_layout = [
    ('Start', 'Room1'), ('Start', 'Room2'),
    ('Room1', 'Room3'), ('Room2', 'Room4'),
    ('Room3', 'Room5'), ('Room4', 'Room5'),
    ('Room5', 'Exit'), ('Room1', 'Room2')  # Secret passage
]

for room1, room2 in maze_layout:
    maze.add_edge(room1, room2)

# Explore the maze
print("Maze exploration:")
print(f"DFS path: {maze.dfs('Start')}")
print(f"BFS path: {maze.bfs('Start')}")

# Find all paths to exit (using DFS)
def find_all_paths(graph, start, end, path=[]):
    """Find all paths between start and end."""
    path = path + [start]
    if start == end:
        return [path]

    all_paths = []
    for neighbor, _ in graph.get_neighbors(start):
        if neighbor not in path:  # Avoid cycles
            new_paths = find_all_paths(graph, neighbor, end, path)
            all_paths.extend(new_paths)

    return all_paths

paths_to_exit = find_all_paths(maze, 'Start', 'Exit')
print(f"\nAll paths to exit ({len(paths_to_exit)} found):")
for i, path in enumerate(paths_to_exit, 1):
    print(f"  Path {i}: {' → '.join(path)}")

# Check maze properties
print(f"\nMaze has loops: {maze.has_cycle()}")
print(f"All rooms connected: {maze.is_connected()}")

Web Crawler or Link Analysis

# Model web page links
web_graph = AdjacencyListGraph(directed=True)

# Add page links
links = [
    ('index.html', 'about.html'),
    ('index.html', 'products.html'),
    ('index.html', 'contact.html'),
    ('about.html', 'team.html'),
    ('products.html', 'product1.html'),
    ('products.html', 'product2.html'),
    ('product1.html', 'contact.html'),
    ('product2.html', 'contact.html'),
    ('contact.html', 'index.html')  # Back to home
]

for from_page, to_page in links:
    web_graph.add_edge(from_page, to_page)

# Analyze website structure
print(f"Total pages: {web_graph.vertex_count()}")
print(f"Total links: {web_graph.edge_count()}")

# Find pages reachable from index
reachable = web_graph.bfs('index.html')
print(f"Pages reachable from index: {reachable}")

# Find most linked-to pages (highest in-degree)
page_popularity = []
for page in web_graph.get_vertices():
    in_links = web_graph.in_degree(page)
    page_popularity.append((page, in_links))

page_popularity.sort(key=lambda x: x[1], reverse=True)
print("Most popular pages:")
for page, links in page_popularity[:3]:
    print(f"  {page}: {links} incoming links")

# Check for dead ends (pages with no outgoing links)
dead_ends = []
for page in web_graph.get_vertices():
    if web_graph.out_degree(page) == 0:
        dead_ends.append(page)

print(f"Dead end pages: {dead_ends}")

Working with Different Types

Integer Vertices

# Graph with integer vertices
int_graph = AdjacencyListGraph()
int_graph.add_edge(1, 2, 0.5)
int_graph.add_edge(2, 3, 1.0)
int_graph.add_edge(1, 3, 2.0)

print(f"Path 1→3 weight: {int_graph.get_edge_weight(1, 3)}")

Custom Object Vertices

class City:
    def __init__(self, name, population):
        self.name = name
        self.population = population

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, other):
        return isinstance(other, City) and self.name == other.name

# Use custom objects as vertices
city_graph = AdjacencyListGraph()
nyc = City("New York", 8400000)
la = City("Los Angeles", 4000000)
chicago = City("Chicago", 2700000)

city_graph.add_edge(nyc, la, 2445)  # Distance in miles
city_graph.add_edge(nyc, chicago, 790)
city_graph.add_edge(la, chicago, 2015)

# Works with custom objects
print(f"Cities: {[str(city) for city in city_graph.get_vertices()]}")
print(f"NYC to LA distance: {city_graph.get_edge_weight(nyc, la)} miles")

When to Use Adjacency Lists

Ideal Use Cases

Sparse Graphs: When E << V², adjacency lists save significant memory
Dynamic Graphs: When vertices and edges are frequently added/removed
Unknown Graph Size: When the number of vertices isn't known in advance
Traversal-Heavy Applications: When you frequently need to iterate over neighbors
Memory Constraints: When minimizing memory usage is important
Variable Vertex Types: When working with diverse vertex data types

Consider Alternatives When

Dense Graphs: When most vertex pairs have edges, matrices might be more efficient
Frequent Edge Queries: If you often check has_edge(), matrices provide O(1) lookup
Fixed Size: When the graph size is known and limited, matrices can be simpler
Mathematical Operations: When you need matrix operations on the graph

Memory Usage

The adjacency list representation uses approximately: - Undirected Graph: 2E + V list entries (each edge stored twice) - Directed Graph: E + V list entries - Overhead: Python object overhead for lists and tuples

Memory Comparison Examples

For a graph with 1000 vertices and 5000 edges: - Adjacency List: ~10,000 entries (undirected) or ~5,000 entries (directed)
- Adjacency Matrix: 1,000,000 entries (regardless of edge count)

For a social network with 10,000 users and average 50 friends each: - Adjacency List: ~500,000 entries (very efficient) - Adjacency Matrix: 100,000,000 entries (wasteful)

This makes adjacency lists much more memory-efficient for sparse graphs.

Performance Tips

Optimize for Your Use Case

# If you frequently check edge existence, consider caching
class OptimizedAdjacencyList(AdjacencyListGraph):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self._edge_cache = set()

    def add_edge(self, from_v, to_v, weight=1.0):
        super().add_edge(from_v, to_v, weight)
        self._edge_cache.add((from_v, to_v))
        if not self.directed:
            self._edge_cache.add((to_v, from_v))

    def has_edge_fast(self, from_v, to_v):
        return (from_v, to_v) in self._edge_cache

Batch Operations

# When adding many edges, batch them for better performance
edges_to_add = [
    ('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 3),
    ('D', 'E', 4), ('E', 'F', 5)
]

graph = AdjacencyListGraph()
for from_v, to_v, weight in edges_to_add:
    graph.add_edge(from_v, to_v, weight)

Efficient Traversal

# Use get_neighbors() for efficient neighbor iteration
def analyze_vertex_connectivity(graph, vertex):
    """Efficiently analyze a vertex's connections."""
    neighbors = graph.get_neighbors(vertex)  # O(1) operation

    total_weight = sum(weight for _, weight in neighbors)
    neighbor_count = len(neighbors)

    return {
        'degree': neighbor_count,
        'total_weight': total_weight,
        'average_weight': total_weight / neighbor_count if neighbor_count > 0 else 0
    }

# This is much faster than checking each possible edge
stats = analyze_vertex_connectivity(graph, 'A')
print(f"Vertex A stats: {stats}")

API Reference

Adjacency list graph implementation.

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

`AdjacencyListGraph(directed=False)`

Bases: Graph

Graph implementation using adjacency lists.

Supports both directed and undirected graphs with weighted edges.

`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 (number of adjacent edges).

`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.

Adjacency List Graph

Overview

Features

Time Complexities

Basic Usage

Creating and Initializing

Understanding Graph Types

Adding Vertices and Edges

Viewing Graph Information

Removing Elements

Graph Analysis

Degree Calculations

Connectivity and Structure Analysis

Graph Traversal

Depth-First Search (DFS)

Breadth-First Search (BFS)

Practical Examples

Social Network Analysis

Transportation Network

Project Dependencies

Maze or Grid Navigation

Web Crawler or Link Analysis

Working with Different Types

Integer Vertices

Custom Object Vertices

When to Use Adjacency Lists

Ideal Use Cases

Consider Alternatives When

Memory Usage

Memory Comparison Examples

Performance Tips

Optimize for Your Use Case

Batch Operations

Efficient Traversal

API Reference

AdjacencyListGraph(directed=False)

__repr__()

__str__()

add_edge(from_vertex, to_vertex, weight=1.0)

add_vertex(vertex)

bfs(start_vertex)

degree(vertex)

dfs(start_vertex, visited=None)

edge_count()

get_edge_weight(from_vertex, to_vertex)

get_edges()

get_neighbors(vertex)

get_vertices()

has_cycle()

has_edge(from_vertex, to_vertex)

in_degree(vertex)

is_connected()

out_degree(vertex)

remove_edge(from_vertex, to_vertex)

remove_vertex(vertex)

topological_sort()

vertex_count()