Skip to content

Graph Interface

The Graph interface defines the common API that all graph implementations must follow, ensuring consistency and interoperability across different graph representations. It serves as an abstract base class that provides a unified interface for graph operations regardless of the underlying implementation.

Overview

The Graph interface establishes a standardized contract for graph data structures, enabling polymorphic usage of different graph implementations. This design allows developers to write algorithms that work with any graph representation and easily switch between implementations based on performance requirements.

Features

  • Unified API - consistent method signatures across all implementations
  • Polymorphic design - write code that works with any graph implementation
  • Type safety - comprehensive type hints for all methods
  • Complete functionality - covers all essential graph operations
  • Implementation flexibility - allows for optimized implementations
  • Algorithm compatibility - enables graph algorithms to work with any implementation
  • Easy testing - facilitates testing with different graph representations

Design Principles

The Graph interface follows these key principles:

Consistency

All graph implementations provide the same method signatures, making it easy to switch between different representations without changing client code.

Flexibility

The interface supports both directed and undirected graphs, with optional edge weights for all operations.

Completeness

The interface covers all essential graph operations from basic manipulation to advanced analysis algorithms.

Performance Transparency

While the interface is uniform, implementations can optimize for their specific use cases (sparse vs dense graphs).

Interface Methods

Basic Graph Operations

# Vertex operations
graph.add_vertex(vertex)                    # Add a vertex to the graph
graph.remove_vertex(vertex)                 # Remove vertex and all its edges
graph.get_vertices()                        # Get all vertices as a set
graph.vertex_count()                        # Get number of vertices

# Edge operations  
graph.add_edge(from_v, to_v, weight=1.0)    # Add weighted edge
graph.remove_edge(from_v, to_v)             # Remove edge
graph.has_edge(from_v, to_v)                # Check if edge exists
graph.get_edge_weight(from_v, to_v)         # Get edge weight (returns None if no edge)
graph.get_edges()                           # Get all edges as (from, to, weight) tuples
graph.edge_count()                          # Get number of edges
graph.get_neighbors(vertex)                 # Get adjacent vertices with weights

Graph Analysis

# Degree calculations
graph.degree(vertex)                        # Total degree (in + out for directed)
graph.in_degree(vertex)                     # In-degree (directed graphs)
graph.out_degree(vertex)                    # Out-degree (directed graphs)

# Structural analysis
graph.is_connected()                        # Check connectivity (undirected graphs)
graph.has_cycle()                           # Detect cycles
graph.topological_sort()                    # Topological ordering (DAGs only)

Graph Traversal

# Traversal algorithms
graph.dfs(start_vertex)                     # Depth-first search
graph.bfs(start_vertex)                     # Breadth-first search

Implementation Requirements

All concrete graph classes must:

  1. Inherit from Graph: Use the abstract base class as the parent
  2. Implement all abstract methods: Every method in the interface must be implemented
  3. Follow type hints: Use the specified parameter and return types
  4. Handle edge cases: Gracefully handle non-existent vertices/edges
  5. Maintain consistency: Ensure directed/undirected behavior is consistent
  6. Preserve invariants: Maintain graph properties and constraints

Example Implementation Pattern

from abc import ABC, abstractmethod
from typing import List, Set, Optional, Tuple, Any
from .graph_interface import Graph

class MyCustomGraph(Graph):
    """Example implementation following the Graph interface."""

    def __init__(self, directed: bool = False):
        self.directed = directed
        # Initialize implementation-specific data structures
        self._vertices = set()
        self._edges = {}  # Implementation-specific storage

    def add_vertex(self, vertex: Any) -> None:
        """Add a vertex to the graph."""
        self._vertices.add(vertex)
        # Implementation-specific logic

    def add_edge(self, from_vertex: Any, to_vertex: Any, weight: float = 1.0) -> None:
        """Add a weighted edge between vertices."""
        # Ensure vertices exist
        self.add_vertex(from_vertex)
        self.add_vertex(to_vertex)
        # Implementation-specific edge storage

    def has_edge(self, from_vertex: Any, to_vertex: Any) -> bool:
        """Check if edge exists between vertices."""
        # Implementation-specific lookup
        pass

    def get_edge_weight(self, from_vertex: Any, to_vertex: Any) -> Optional[float]:
        """Get weight of edge between vertices."""
        if self.has_edge(from_vertex, to_vertex):
            # Return implementation-specific weight
            pass
        return None

    # ... implement all other abstract methods

    def __str__(self) -> str:
        return f"MyCustomGraph(directed={self.directed}, vertices={self.vertex_count()}, edges={self.edge_count()})"

Benefits of the Interface

Polymorphism

Write algorithms that work with any graph implementation:

def analyze_graph(graph: Graph) -> dict:
    """Analyze any graph implementation using the common interface."""
    analysis = {
        'vertices': graph.vertex_count(),
        'edges': graph.edge_count(),
        'is_connected': graph.is_connected(),
        'has_cycle': graph.has_cycle(),
        'density': 0.0
    }

    # Calculate density
    v = analysis['vertices']
    if v > 1:
        max_edges = v * (v - 1) if graph.directed else v * (v - 1) // 2
        analysis['density'] = analysis['edges'] / max_edges if max_edges > 0 else 0

    # Analyze degree distribution
    degrees = []
    for vertex in graph.get_vertices():
        degrees.append(graph.degree(vertex))

    if degrees:
        analysis['avg_degree'] = sum(degrees) / len(degrees)
        analysis['max_degree'] = max(degrees)
        analysis['min_degree'] = min(degrees)

    return analysis

# Works with any graph implementation
list_graph = AdjacencyListGraph()
matrix_graph = AdjacencyMatrixGraph()

# Same analysis code works for both
print("List Graph Analysis:", analyze_graph(list_graph))
print("Matrix Graph Analysis:", analyze_graph(matrix_graph))

Algorithm Compatibility

Graph algorithms can work with any implementation:

def shortest_path_unweighted(graph: Graph, start: Any, end: Any) -> Optional[List[Any]]:
    """Find shortest path using BFS - works with any graph implementation."""
    if start == end:
        return [start]

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

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

        # get_neighbors() works the same across all implementations
        for neighbor, _ in graph.get_neighbors(current):
            if neighbor == end:
                return path + [neighbor]

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

    return None  # No path found

def find_articulation_points(graph: Graph) -> Set[Any]:
    """Find articulation points - works with any undirected graph implementation."""
    if graph.directed:
        raise ValueError("Algorithm requires undirected graph")

    vertices = graph.get_vertices()
    if len(vertices) <= 2:
        return set()

    articulation_points = set()

    # Test each vertex for articulation
    for vertex in vertices:
        # Create temporary graph without this vertex
        temp_components = 0
        visited = {vertex}  # Mark articulation candidate as visited

        # Count components in remaining graph
        for start_vertex in vertices:
            if start_vertex not in visited:
                # BFS to find component
                component = graph.bfs(start_vertex)
                visited.update(component)
                temp_components += 1

        # If removing vertex increases components, it's an articulation point
        if temp_components > 1:
            articulation_points.add(vertex)

    return articulation_points

# These algorithms work with both implementations
path = shortest_path_unweighted(any_graph, 'A', 'Z')
critical_vertices = find_articulation_points(any_graph)

Easy Testing

Test graph algorithms with different implementations to ensure correctness:

def test_algorithm_with_all_implementations():
    """Test algorithms across different graph implementations."""
    implementations = [
        ("AdjacencyListGraph", AdjacencyListGraph()),
        ("AdjacencyMatrixGraph", AdjacencyMatrixGraph(max_vertices=10))
    ]

    # Test data
    edges = [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 3), ('A', 'D', 4)]

    for impl_name, graph in implementations:
        print(f"\nTesting with {impl_name}:")

        # Set up same graph structure
        for from_v, to_v, weight in edges:
            graph.add_edge(from_v, to_v, weight)

        # Test basic operations
        assert graph.vertex_count() == 4
        assert graph.edge_count() == 4
        assert graph.has_edge('A', 'B')
        assert graph.get_edge_weight('A', 'B') == 1

        # Test traversal
        bfs_result = graph.bfs('A')
        dfs_result = graph.dfs('A')
        assert len(bfs_result) == 4
        assert len(dfs_result) == 4

        # Test analysis
        assert not graph.has_cycle()  # Should be acyclic

        print(f"  ✓ All tests passed for {impl_name}")

# Run compatibility tests
test_algorithm_with_all_implementations()

Implementation Switching

Easily switch between implementations based on requirements:

def create_optimal_graph(vertex_count: int, edge_count: int, directed: bool = False) -> Graph:
    """Create the most appropriate graph implementation based on characteristics."""

    # Calculate graph density
    max_edges = vertex_count * (vertex_count - 1)
    if not directed:
        max_edges //= 2

    density = edge_count / max_edges if max_edges > 0 else 0

    if density > 0.5 and vertex_count <= 1000:
        # Dense graph with reasonable size - use matrix
        print(f"Creating AdjacencyMatrixGraph (density: {density:.2f})")
        return AdjacencyMatrixGraph(directed=directed, max_vertices=vertex_count * 2)
    else:
        # Sparse graph or large graph - use list
        print(f"Creating AdjacencyListGraph (density: {density:.2f})")
        return AdjacencyListGraph(directed=directed)

# Usage - same code works regardless of implementation returned
graph = create_optimal_graph(100, 2000, directed=True)
graph.add_edge('start', 'end', 1.0)
path = graph.bfs('start')

Interface Validation

Type Checking

def validate_graph_interface(graph: Graph) -> bool:
    """Validate that an object properly implements the Graph interface."""
    required_methods = [
        'add_vertex', 'remove_vertex', 'get_vertices', 'vertex_count',
        'add_edge', 'remove_edge', 'has_edge', 'get_edge_weight', 
        'get_edges', 'edge_count', 'get_neighbors',
        'degree', 'in_degree', 'out_degree',
        'is_connected', 'has_cycle', 'topological_sort',
        'dfs', 'bfs'
    ]

    for method in required_methods:
        if not hasattr(graph, method):
            print(f"Missing method: {method}")
            return False
        if not callable(getattr(graph, method)):
            print(f"Not callable: {method}")
            return False

    return True

# Check implementation compliance
is_valid = validate_graph_interface(my_graph)
print(f"Graph implementation is valid: {is_valid}")

Behavioral Testing

def test_graph_interface_behavior(graph: Graph):
    """Test that graph behaves according to interface contract."""
    # Test vertex operations
    initial_count = graph.vertex_count()
    graph.add_vertex('test')
    assert graph.vertex_count() == initial_count + 1
    assert 'test' in graph.get_vertices()

    # Test edge operations
    graph.add_vertex('test2')
    graph.add_edge('test', 'test2', 5.0)
    assert graph.has_edge('test', 'test2')
    assert graph.get_edge_weight('test', 'test2') == 5.0
    assert graph.edge_count() > 0

    # Test neighbors
    neighbors = graph.get_neighbors('test')
    assert len(neighbors) > 0
    assert any(neighbor == 'test2' for neighbor, _ in neighbors)

    # Test degree calculations
    degree = graph.degree('test')
    assert degree > 0

    print("All interface behavior tests passed!")

# Test any implementation
test_graph_interface_behavior(my_graph)

Best Practices for Implementers

Error Handling

class RobustGraph(Graph):
    """Example of robust error handling in graph implementation."""

    def add_edge(self, from_vertex: Any, to_vertex: Any, weight: float = 1.0) -> None:
        # Validate inputs
        if weight < 0:
            raise ValueError("Edge weight cannot be negative")

        # Handle self-loops based on implementation policy
        if from_vertex == to_vertex:
            # Either allow or reject based on requirements
            pass

        # Implementation logic here

    def get_edge_weight(self, from_vertex: Any, to_vertex: Any) -> Optional[float]:
        # Validate vertices exist
        if from_vertex not in self.get_vertices():
            return None
        if to_vertex not in self.get_vertices():
            return None

        # Return weight or None
        # Implementation logic here

Performance Documentation

class DocumentedGraph(Graph):
    """Example of well-documented performance characteristics."""

    def has_edge(self, from_vertex: Any, to_vertex: Any) -> bool:
        """
        Check if edge exists between vertices.

        Time Complexity: O(1) for matrix implementation, O(V) for list implementation
        Space Complexity: O(1)

        Args:
            from_vertex: Source vertex
            to_vertex: Target vertex

        Returns:
            True if edge exists, False otherwise
        """
        # Implementation here
        pass

API Reference

Graph interface definition.

This module provides an abstract base class that defines the common interface for all graph implementations.

Graph

Bases: ABC

Abstract base class defining the interface for graph data structures.

This interface ensures consistent method signatures across different graph implementations like adjacency lists and adjacency matrices.

add_edge(from_vertex, to_vertex, weight=1.0) abstractmethod

Add an edge between two vertices.

add_vertex(vertex) abstractmethod

Add a vertex to the graph.

bfs(start_vertex) abstractmethod

Perform breadth-first search starting from a vertex.

degree(vertex) abstractmethod

Get the degree of a vertex (number of adjacent edges).

dfs(start_vertex, visited=None) abstractmethod

Perform depth-first search starting from a vertex.

edge_count() abstractmethod

Get the number of edges in the graph.

get_edge_weight(from_vertex, to_vertex) abstractmethod

Get the weight of an edge between two vertices.

get_edges() abstractmethod

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

get_neighbors(vertex) abstractmethod

Get all neighbors of a vertex with their edge weights.

get_vertices() abstractmethod

Get all vertices in the graph.

has_cycle() abstractmethod

Check if the graph has a cycle.

has_edge(from_vertex, to_vertex) abstractmethod

Check if there's an edge between two vertices.

in_degree(vertex) abstractmethod

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

is_connected() abstractmethod

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

out_degree(vertex) abstractmethod

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

remove_edge(from_vertex, to_vertex) abstractmethod

Remove an edge between two vertices.

remove_vertex(vertex) abstractmethod

Remove a vertex and all its edges from the graph.

topological_sort() abstractmethod

Perform topological sorting (for directed acyclic graphs).

vertex_count() abstractmethod

Get the number of vertices in the graph.