xbe.at

Python / Data structures and algorithms

Implementing Undirected Graphs in Python

6 min read, 14 sections

Contents
  1. Graph Representation Using Adjacency List
  2. Edge Operations and Graph Manipulation
  3. Graph Traversal - Depth First Search
  4. Graph Traversal - Breadth First Search
  5. Cycle Detection in Undirected Graphs
  6. Connected Components Analysis
  7. Path Finding Between Vertices
  8. Graph Metrics and Analysis
  9. Real-World Application - Social Network Analysis
  10. Real-World Application - Results for Social Network Analysis
  11. Graph Search Optimization
  12. Graph Validation and Integrity Checks
  13. Graph Mathematical Properties
  14. Additional Resources

Graph Representation Using Adjacency List

An adjacency list representation provides an efficient way to store graph connections by maintaining a dictionary where each vertex maps to a list of its neighbors. This approach optimizes space complexity for sparse graphs compared to adjacency matrices.

class UndirectedGraph:
    def __init__(self):
        self.graph = {}  # Dictionary to store adjacency list
        
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
            
    def add_edge(self, v1, v2):
        if v1 not in self.graph:
            self.add_vertex(v1)
        if v2 not in self.graph:
            self.add_vertex(v2)
        # Add bidirectional edges
        self.graph[v1].append(v2)
        self.graph[v2].append(v1)

Edge Operations and Graph Manipulation

Implementing robust edge operations is crucial for maintaining graph integrity. The remove_edge method handles bidirectional edge removal while ensuring the graph remains consistent, with error handling for non-existent vertices or edges.

def remove_edge(self, v1, v2):
    if v1 in self.graph and v2 in self.graph:
        if v2 in self.graph[v1]:
            self.graph[v1].remove(v2)
            self.graph[v2].remove(v1)
            return True
    return False

def get_neighbors(self, vertex):
    return self.graph.get(vertex, [])

def get_vertices(self):
    return list(self.graph.keys())

Graph Traversal - Depth First Search

Depth-First Search (DFS) explores the graph by traversing as far as possible along each branch before backtracking. This implementation uses recursion and maintains a visited set to prevent cycles in the traversal.

def dfs(self, start_vertex, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start_vertex)
    print(f"Visiting vertex: {start_vertex}")
    
    for neighbor in self.graph[start_vertex]:
        if neighbor not in visited:
            self.dfs(neighbor, visited)
    
    return visited

Graph Traversal - Breadth First Search

Breadth-First Search (BFS) explores the graph level by level, visiting all neighbors of a vertex before moving to the next level. This implementation uses a queue to maintain the order of vertex exploration.

from collections import deque

def bfs(self, start_vertex):
    visited = set()
    queue = deque([start_vertex])
    visited.add(start_vertex)
    
    while queue:
        vertex = queue.popleft()
        print(f"Visiting vertex: {vertex}")
        
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

Cycle Detection in Undirected Graphs

Detecting cycles in an undirected graph requires tracking both visited vertices and parent relationships to distinguish between valid paths and back edges that form cycles.

def has_cycle(self, vertex, visited, parent):
    visited.add(vertex)
    
    for neighbor in self.graph[vertex]:
        if neighbor not in visited:
            if self.has_cycle(neighbor, visited, vertex):
                return True
        elif parent != neighbor:
            return True
    return False

def contains_cycle(self):
    visited = set()
    for vertex in self.graph:
        if vertex not in visited:
            if self.has_cycle(vertex, visited, None):
                return True
    return False

Connected Components Analysis

Finding connected components in an undirected graph reveals isolated subgraphs. This implementation uses DFS to identify and group vertices that are reachable from each other.

def find_connected_components(self):
    components = []
    visited = set()
    
    for vertex in self.graph:
        if vertex not in visited:
            component = set()
            self._dfs_component(vertex, visited, component)
            components.append(component)
    
    return components

def _dfs_component(self, vertex, visited, component):
    visited.add(vertex)
    component.add(vertex)
    
    for neighbor in self.graph[vertex]:
        if neighbor not in visited:
            self._dfs_component(neighbor, visited, component)

Path Finding Between Vertices

Implementing path finding functionality helps determine if two vertices are connected and finds the sequence of vertices that connect them using breadth-first search for shortest path.

def find_path(self, start, end):
    if start not in self.graph or end not in self.graph:
        return None
    
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        vertex, path = queue.popleft()
        
        if vertex == end:
            return path
            
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

Graph Metrics and Analysis

Computing various metrics helps understand graph properties such as vertex degrees, graph density, and average connectivity, providing insights into the graph's structure and characteristics.

def compute_metrics(self):
    metrics = {
        'num_vertices': len(self.graph),
        'num_edges': sum(len(neighbors) for neighbors in self.graph.values()) // 2,
        'avg_degree': 0,
        'density': 0,
        'degrees': {}
    }
    
    for vertex in self.graph:
        metrics['degrees'][vertex] = len(self.graph[vertex])
    
    if metrics['num_vertices'] > 0:
        metrics['avg_degree'] = sum(metrics['degrees'].values()) / metrics['num_vertices']
        max_edges = metrics['num_vertices'] * (metrics['num_vertices'] - 1) // 2
        metrics['density'] = metrics['num_edges'] / max_edges if max_edges > 0 else 0
    
    return metrics

Real-World Application - Social Network Analysis

A practical implementation of graph analysis for social networks, demonstrating friend relationships, influence measurement, and community detection using the undirected graph structure.

class SocialNetwork(UndirectedGraph):
    def __init__(self):
        super().__init__()
        self.user_data = {}
    
    def add_user(self, user_id, data=None):
        self.add_vertex(user_id)
        self.user_data[user_id] = data or {}
    
    def add_friendship(self, user1, user2):
        self.add_edge(user1, user2)
    
    def get_influence_score(self, user_id):
        if user_id not in self.graph:
            return 0
        direct_friends = len(self.graph[user_id])
        second_degree = sum(len(self.graph[friend]) for friend in self.graph[user_id])
        return direct_friends + second_degree * 0.5

Real-World Application - Results for Social Network Analysis

Implementation of test cases and visualization of social network metrics, demonstrating the practical application of graph algorithms in analyzing user relationships and influence patterns.

# Create sample social network
social_net = SocialNetwork()

# Add users and friendships
users = ['Alice', 'Bob', 'Charlie', 'David', 'Eve']
for user in users:
    social_net.add_user(user, {'active': True})

# Add friendship connections
friendships = [
    ('Alice', 'Bob'), ('Alice', 'Charlie'),
    ('Bob', 'David'), ('Charlie', 'Eve'),
    ('David', 'Eve')
]
for u1, u2 in friendships:
    social_net.add_friendship(u1, u2)

# Calculate and display metrics
print("Network Metrics:")
for user in users:
    influence = social_net.get_influence_score(user)
    friends = len(social_net.get_neighbors(user))
    print(f"{user}: {friends} friends, Influence Score: {influence}")

# Output:
# Network Metrics:
# Alice: 2 friends, Influence Score: 5.0
# Bob: 2 friends, Influence Score: 4.5
# Charlie: 2 friends, Influence Score: 4.5
# David: 2 friends, Influence Score: 4.5
# Eve: 2 friends, Influence Score: 4.5

Graph Search Optimization

Advanced search optimization techniques improve graph traversal efficiency by implementing priority-based exploration and early termination conditions for specific search scenarios.

def optimized_search(self, start, target, max_depth=None):
    if start not in self.graph:
        return None
    
    visited = {start: 0}  # vertex: depth
    queue = deque([(start, [start])])
    
    while queue:
        vertex, path = queue.popleft()
        current_depth = visited[vertex]
        
        if vertex == target:
            return path
            
        if max_depth and current_depth >= max_depth:
            continue
            
        # Sort neighbors by potential relevance
        neighbors = sorted(self.graph[vertex], 
                         key=lambda x: len(self.graph[x]),
                         reverse=True)
        
        for neighbor in neighbors:
            if neighbor not in visited:
                visited[neighbor] = current_depth + 1
                queue.append((neighbor, path + [neighbor]))
    
    return None

Graph Validation and Integrity Checks

Implementing robust validation methods ensures graph integrity by checking for inconsistencies, invalid edges, and maintaining bidirectional relationship constraints in the undirected graph.

def validate_graph(self):
    validation_results = {
        'is_valid': True,
        'errors': []
    }
    
    # Check bidirectional consistency
    for vertex in self.graph:
        for neighbor in self.graph[vertex]:
            if vertex not in self.graph.get(neighbor, []):
                validation_results['is_valid'] = False
                validation_results['errors'].append(
                    f"Inconsistent edge: {vertex}->{neighbor}")
    
    # Check for self-loops
    for vertex in self.graph:
        if vertex in self.graph[vertex]:
            validation_results['is_valid'] = False
            validation_results['errors'].append(
                f"Self-loop detected at vertex: {vertex}")
    
    # Check for isolated vertices
    isolated = [v for v in self.graph if not self.graph[v]]
    if isolated:
        validation_results['errors'].append(
            f"Isolated vertices found: {isolated}")
    
    return validation_results

Graph Mathematical Properties

Mathematical analysis of graph properties using theorems from graph theory, including connectivity measures and structural characteristics expressed in mathematical notation.

def calculate_graph_properties(self):
    """
    Mathematical properties of the graph including:
    - Vertex degree distribution
    - Graph density
    - Connectivity metrics
    """
    properties = {}
    n = len(self.graph)  # Number of vertices
    
    # Vertex degree distribution
    # Formula: $$P(k) = \frac{n_k}{n}$$
    degree_dist = {}
    for vertex in self.graph:
        k = len(self.graph[vertex])
        degree_dist[k] = degree_dist.get(k, 0) + 1
    
    # Graph density
    # Formula: $$\rho = \frac{2|E|}{|V|(|V|-1)}$$
    m = sum(len(neighbors) for neighbors in self.graph.values()) // 2
    density = (2 * m) / (n * (n - 1)) if n > 1 else 0
    
    properties.update({
        'degree_distribution': degree_dist,
        'density': density,
        'average_degree': (2 * m) / n if n > 0 else 0
    })
    
    return properties

Additional Resources

More in Data structures and algorithms

  1. Key Python List Methods for Manipulation10 min

    The append() method efficiently adds elements to the end of a list with O(1) time complexity, while insert() places elements at specific positions with O(n)...

  2. Implementing Python Data Structures Without External Libraries4 min

    The underscore (\) in Python is a versatile character with multiple uses. It serves as a convention to indicate that a value is meant to be ignored or is...

  3. Linear and Binary Search Algorithms in Python8 min

    Linear search is a simple search algorithm used to find an element in a list or array. It works by iterating through the elements one by one, comparing each...

  4. Implementing Graph Data Structures in Python9 min

    A graph is a non-linear data structure consisting of vertices (nodes) and edges connecting these vertices. In Python, we can implement a graph using...

  5. Lists and List Functions in Python7 min

    Lists serve as fundamental data structures in Python, offering a mutable and ordered sequence of elements. They can store heterogeneous data types, making...

  6. Implementing Efficient Graph Structures in Python9 min

    The adjacency list representation of graphs offers an efficient way to store sparse graphs where the number of edges is much less than the maximum possible...