Graph Types - Learning Module

Loading content...

0/276

Mixed and Special Graph Types

Beyond the Basics: Specialized Graph Structures

The directed, undirected, and weighted graph classifications we've covered form the foundation—but real-world problems often require more specialized structures. What if some edges are one-way and others bidirectional? What if multiple edges connect the same pair of vertices? What if edges connect more than two vertices simultaneously? What if vertices naturally partition into distinct groups?

These questions lead to specialized graph types: multigraphs, hypergraphs, bipartite graphs, DAGs, and more. Each extends the basic graph model to capture specific structural patterns that arise in practice. Understanding these variants unlocks more precise modeling and more efficient algorithms tailored to their special properties.

What You Will Learn

By the end of this page, you will understand mixed graphs that combine directed and undirected edges, multigraphs and pseudographs with multiple edges and self-loops, hypergraphs where edges connect multiple vertices, bipartite graphs with two-set vertex partitioning, DAGs and their unique properties, and several other important graph classifications.

Mixed Graphs

In many real-world networks, some connections are inherently one-way while others are bidirectional. A mixed graph combines directed and undirected edges in a single structure.

Definition:

A mixed graph G is defined as G = (V, E_d, E_u), where:

V is a finite set of vertices
E_d is a set of directed edges (arcs): ordered pairs (u, v)
E_u is a set of undirected edges: unordered pairs {u, v}

Directed and undirected edges coexist, each behaving according to its type.

Real-World Examples:

Road Networks: Most roads are bidirectional (undirected), but one-way streets are directed. A realistic road graph is mixed.
Social Networks: Friendships might be undirected (mutual), while 'follows' are directed (asymmetric). A combined model is mixed.
Academic Citations + Collaboration: Co-authorship is undirected; citations are directed. Combining both creates a mixed graph.

Handling Mixed Graphs

Mixed graphs can be converted to pure directed graphs by replacing each undirected edge {u, v} with two directed edges (u, v) and (v, u). This allows using directed-graph algorithms, though it doubles the edge count for undirected edges.

mixed_graph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from typing import Dict, List, Set, Tuple
 
class MixedGraph:
    """
    A graph with both directed and undirected edges.
    
    Internally, we store:
    - directed_out[u] = list of vertices v where (u, v) is a directed edge
    - undirected[u] = list of vertices v where {u, v} is undirected
    """
    def __init__(self):
        self.directed_out: Dict[str, List[str]] = {}
        self.undirected: Dict[str, List[str]] = {}
    
    def add_vertex(self, v: str):
        if v not in self.directed_out:
            self.directed_out[v] = []
        if v not in self.undirected:
            self.undirected[v] = []
    
    def add_directed_edge(self, u: str, v: str):
        """Add a one-way edge from u to v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.directed_out[u].append(v)
    
    def add_undirected_edge(self, u: str, v: str):
        """Add a two-way edge between u and v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.undirected[u].append(v)
        self.undirected[v].append(u)
    
    def get_outgoing_neighbors(self, u: str) -> List[str]:
        """Get all vertices reachable from u in one step."""
        # Directed: outgoing edges
        # Undirected: both directions
        return self.directed_out.get(u, []) + self.undirected.get(u, [])
    
    def get_incoming_neighbors(self, u: str) -> List[str]:
        """Get all vertices that can reach u in one step."""
        incoming = list(self.undirected.get(u, []))  # Undirected edges
        # Check all directed edges pointing to u
        for v, neighbors in self.directed_out.items():
            if u in neighbors:
                incoming.append(v)
        return incoming
    
    def to_pure_directed(self) -> Dict[str, List[str]]:
        """
        Convert to pure directed graph by doubling undirected edges.
        Useful for applying directed-graph algorithms.
        """
        result: Dict[str, List[str]] = {}
        for v in self.directed_out:
            result[v] = list(self.directed_out[v])  # Copy directed edges
            result[v].extend(self.undirected[v])     # Add undirected as directed
        return result
 
 
# Example: Road network with one-way streets
road_network = MixedGraph()
 
# Bidirectional roads
road_network.add_undirected_edge('A', 'B')
road_network.add_undirected_edge('B', 'C')
road_network.add_undirected_edge('C', 'D')
 
# One-way streets
road_network.add_directed_edge('D', 'A')  # D -> A only
road_network.add_directed_edge('B', 'D')  # B -> D only
 
print("From B, can reach:", road_network.get_outgoing_neighbors('B'))
# Output: ['D', 'A', 'C'] — can go to D (directed), A and C (undirected)
 
print("Can reach B from:", road_network.get_incoming_neighbors('B'))
# Output: ['A', 'C'] — A and C via undirected edges only
 
print("Pure directed version:", road_network.to_pure_directed())

Multigraphs and Pseudographs

Standard simple graphs allow at most one edge between any pair of vertices and no edges from a vertex to itself. But real-world scenarios often violate these constraints.

Multigraph:

A multigraph allows multiple edges (also called parallel edges) between the same pair of vertices. Each edge is distinct, potentially with different properties (weights, labels).

Example Applications:

Transportation: Multiple flights between same cities at different times/prices
Communication: Multiple channels or links between same network nodes
Electrical circuits: Multiple resistors in parallel between same junctions

Pseudograph:

A pseudograph allows both multiple edges AND self-loops (edges from a vertex to itself).

Example Applications:

State machines: A state can transition to itself (self-loop)
Network routing: A packet can loop back at certain nodes
Graph coloring with constraints: Self-loops represent additional restrictions

Graph Type Comparison
Graph Type	Multiple Edges	Self-Loops	Example
Simple Graph	❌	❌	Basic graph theory, most algorithms
Multigraph	✅	❌	Multiple flights between cities
Pseudograph	✅	✅	State machines with self-transitions
Simple Pseudograph	❌	✅	Graph with only self-loops allowed

Algorithm Implications

Many standard algorithms assume simple graphs. With multigraphs: edge counts change (adjacency matrix can have values > 1), BFS/DFS may traverse the same 'connection' multiple times. Self-loops affect degree counts (a self-loop contributes 2 to the degree). Always verify algorithm assumptions against your graph type.

Representation Strategies:

For multigraphs, the standard adjacency list and matrix need modification:

Adjacency List for Multigraph: Store edges as objects with IDs, or maintain a list of (neighbor, edge_id, properties) tuples.

Adjacency Matrix for Multigraph: Instead of boolean values, store edge counts or lists of edge IDs.

Edge List Representation: Often the cleanest for multigraphs—simply list all edges, even duplicates between same vertices. Each edge is a distinct entity.

multigraph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from typing import Dict, List, Tuple, Any
from collections import defaultdict
 
class Multigraph:
    """
    A graph allowing multiple edges between same vertex pairs.
    Each edge has a unique ID and optional properties.
    """
    def __init__(self):
        self.vertices: set = set()
        self.edges: Dict[int, Tuple[str, str, Dict[str, Any]]] = {}
        self.adjacency: Dict[str, List[int]] = defaultdict(list)  # vertex -> edge IDs
        self.next_edge_id = 0
    
    def add_vertex(self, v: str):
        self.vertices.add(v)
        if v not in self.adjacency:
            self.adjacency[v] = []
    
    def add_edge(self, u: str, v: str, **properties) -> int:
        """
        Add an edge from u to v with optional properties.
        Returns the unique edge ID.
        """
        self.add_vertex(u)
        self.add_vertex(v)
        
        edge_id = self.next_edge_id
        self.next_edge_id += 1
        
        self.edges[edge_id] = (u, v, properties)
        self.adjacency[u].append(edge_id)
        if u != v:  # Undirected: add reverse (for directed multigraph, remove this)
            self.adjacency[v].append(edge_id)
        
        return edge_id
    
    def get_edges_between(self, u: str, v: str) -> List[Tuple[int, Dict[str, Any]]]:
        """Get all edges (with IDs and properties) between u and v."""
        result = []
        for edge_id in self.adjacency.get(u, []):
            eu, ev, props = self.edges[edge_id]
            if (eu == u and ev == v) or (eu == v and ev == u):
                result.append((edge_id, props))
        return result
    
    def edge_count_between(self, u: str, v: str) -> int:
        """Count edges between u and v."""
        return len(self.get_edges_between(u, v))
    
    def get_neighbors_with_edges(self, u: str) -> Dict[str, List[int]]:
        """Get neighbors with edge IDs for each connection."""
        neighbors: Dict[str, List[int]] = defaultdict(list)
        for edge_id in self.adjacency.get(u, []):
            eu, ev, _ = self.edges[edge_id]
            neighbor = ev if eu == u else eu
            neighbors[neighbor].append(edge_id)
        return dict(neighbors)
 
 
# Example: Multiple flights between cities
flights = Multigraph()
 
# Multiple flights from NYC to LA
flights.add_edge('NYC', 'LA', airline='United', price=350, time='6:00')
flights.add_edge('NYC', 'LA', airline='Delta', price=380, time='9:30')
flights.add_edge('NYC', 'LA', airline='JetBlue', price=320, time='14:00')
 
# Single flight each way for other routes
flights.add_edge('NYC', 'Chicago', airline='United', price=180, time='8:00')
flights.add_edge('LA', 'Chicago', airline='American', price=200, time='10:00')
 
print(f"Flights from NYC to LA: {flights.edge_count_between('NYC', 'LA')}")
# Output: 3
 
print("NYC to LA options:")
for edge_id, props in flights.get_edges_between('NYC', 'LA'):
    print(f"  Flight {edge_id}: {props}")
 
print(f"\nNeighbors of NYC with edge counts:")
for neighbor, edge_ids in flights.get_neighbors_with_edges('NYC').items():
    print(f"  {neighbor}: {len(edge_ids)} edge(s)")

Hypergraphs

Standard graphs have edges connecting exactly two vertices. But many real-world relationships involve more than two entities simultaneously. Hypergraphs generalize graphs by allowing edges (called hyperedges) to connect any number of vertices.

Definition:

A hypergraph H is defined as H = (V, E), where:

V is a finite set of vertices
E is a set of hyperedges, where each hyperedge e ∈ E is a subset of V: e ⊆ V

A hyperedge can contain 1 vertex (singleton), 2 vertices (standard edge), or any number of vertices.

When to Use Hypergraphs:

Hypergraphs are the right model when relationships inherently involve groups, not pairs:

Database relations: A tuple in a relational table connects multiple attribute values
Co-authorship: A paper connects all its authors (3+ can co-author a single paper)
Email threads: An email connects sender and all recipients
Group memberships: A club connects all its members
Chemical reactions: Reactants and products as a single hyperedge

Hypergraphs vs Cliques

You can model a k-vertex hyperedge as a clique in a standard graph (all k(k-1)/2 pairwise edges). However, this loses information: cliques don't distinguish between 'all vertices participated in one event' vs 'all pairs happened to interact separately.' Hypergraphs preserve this distinction.

Representation:

Incidence Matrix: For a hypergraph with n vertices and m hyperedges, the incidence matrix I is n×m where I[v][e] = 1 if vertex v ∈ hyperedge e.

Adjacency List: For each hyperedge, store the set of vertices it contains. For each vertex, store the set of hyperedges it belongs to.

Algorithms on Hypergraphs:

Many graph algorithms have hypergraph generalizations:

Connectivity: Hypergraph connectivity considers paths through hyperedges
Clustering: Hypergraph partitioning minimizes hyperedge 'cuts' (hyperedges spanning multiple clusters)
Random walks: Transition through hyperedges (pick a hyperedge containing current vertex, then move to another vertex in that hyperedge)

Hypergraph problems are often computationally harder than their graph counterparts.

hypergraph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from typing import Dict, Set, List, FrozenSet
from collections import defaultdict
 
class Hypergraph:
    """
    A hypergraph where hyperedges can connect any number of vertices.
    """
    def __init__(self):
        self.vertices: Set[str] = set()
        self.hyperedges: Dict[int, Set[str]] = {}  # edge_id -> set of vertices
        self.vertex_to_edges: Dict[str, Set[int]] = defaultdict(set)
        self.next_edge_id = 0
    
    def add_vertex(self, v: str):
        self.vertices.add(v)
    
    def add_hyperedge(self, vertices: Set[str], **properties) -> int:
        """
        Add a hyperedge connecting the given vertices.
        Returns the hyperedge ID.
        """
        for v in vertices:
            self.add_vertex(v)
        
        edge_id = self.next_edge_id
        self.next_edge_id += 1
        
        self.hyperedges[edge_id] = vertices
        for v in vertices:
            self.vertex_to_edges[v].add(edge_id)
        
        return edge_id
    
    def get_hyperedges_containing(self, v: str) -> List[int]:
        """Get all hyperedge IDs containing vertex v."""
        return list(self.vertex_to_edges.get(v, set()))
    
    def get_vertices_in_hyperedge(self, edge_id: int) -> Set[str]:
        """Get all vertices in a hyperedge."""
        return self.hyperedges.get(edge_id, set())
    
    def get_neighbors(self, v: str) -> Set[str]:
        """Get all vertices that share at least one hyperedge with v."""
        neighbors = set()
        for edge_id in self.vertex_to_edges.get(v, set()):
            neighbors.update(self.hyperedges[edge_id])
        neighbors.discard(v)  # Remove v itself
        return neighbors
    
    def to_clique_expansion(self) -> Dict[str, Set[str]]:
        """
        Convert to standard graph by replacing each hyperedge
        with a clique connecting all its vertices.
        """
        adjacency: Dict[str, Set[str]] = defaultdict(set)
        for edge_id, vertices in self.hyperedges.items():
            vertex_list = list(vertices)
            for i, u in enumerate(vertex_list):
                for j, v in enumerate(vertex_list):
                    if i != j:
                        adjacency[u].add(v)
        return dict(adjacency)
 
 
# Example: Academic paper co-authorship
papers = Hypergraph()
 
# Paper 1: Three authors
papers.add_hyperedge({'Alice', 'Bob', 'Carol'})
 
# Paper 2: Two authors (standard edge)
papers.add_hyperedge({'Alice', 'Dan'})
 
# Paper 3: Four authors
papers.add_hyperedge({'Bob', 'Carol', 'Eve', 'Frank'})
 
# Paper 4: Solo paper (single-vertex hyperedge)
papers.add_hyperedge({'Alice'})
 
print("Alice's co-authors:", papers.get_neighbors('Alice'))
# Output: {'Bob', 'Carol', 'Dan'}
 
print("Hyperedges containing Bob:", papers.get_hyperedges_containing('Bob'))
 
print("\nClique expansion:")
clique_graph = papers.to_clique_expansion()
for v, neighbors in clique_graph.items():
    print(f"  {v}: {neighbors}")

Bipartite Graphs

Many problems involve two distinct types of entities where relationships only exist between types, never within. Bipartite graphs formalize this structure.

Definition:

A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint sets U and W such that every edge connects a vertex in U to a vertex in W. No edge connects two vertices within the same set.

Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

Real-World Examples:

Job Matching: Workers (U) and jobs (W); edges connect workers to jobs they're qualified for
Recommendation Systems: Users (U) and items (W); edges represent user-item interactions
Course Enrollment: Students (U) and courses (W); edges represent enrollment
Graph Coloring: Bipartite = 2-colorable (can color vertices with 2 colors such that no adjacent vertices share a color)

Bipartite Check via BFS

To check if a graph is bipartite: run BFS/DFS and try to 2-color the graph. Start with a vertex colored 0, color its neighbors 1, their neighbors 0, etc. If you ever find an edge connecting same-colored vertices, the graph is not bipartite. Otherwise, the coloring proves it is.

Bipartite Matching:

The most important algorithm on bipartite graphs is maximum bipartite matching: find the maximum number of edges such that no vertex appears in more than one selected edge.

Applications:

Job assignment: Assign workers to jobs maximizing assignments
Stable marriage: Match preferences between two groups
Resource allocation: Assign tasks to resources

Complete Bipartite Graph K_{m,n}:

A complete bipartite graph has every vertex in U connected to every vertex in W. With |U| = m and |W| = n, it has m×n edges. This is the densest possible bipartite graph.

bipartite.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from typing import Dict, List, Set, Optional, Tuple
from collections import deque
 
def is_bipartite(graph: Dict[str, List[str]]) -> Tuple[bool, Optional[Dict[str, int]]]:
    """
    Check if a graph is bipartite using BFS 2-coloring.
    
    Returns:
        (is_bipartite, coloring)
        coloring maps each vertex to 0 or 1 if bipartite, None otherwise
    """
    color: Dict[str, int] = {}
    
    for start in graph:
        if start in color:
            continue
        
        # BFS from uncolored vertex
        queue = deque([start])
        color[start] = 0
        
        while queue:
            vertex = queue.popleft()
            for neighbor in graph.get(vertex, []):
                if neighbor not in color:
                    color[neighbor] = 1 - color[vertex]  # Alternate colors
                    queue.append(neighbor)
                elif color[neighbor] == color[vertex]:
                    return False, None  # Same color = not bipartite
    
    return True, color
 
 
def get_bipartite_sets(graph: Dict[str, List[str]]) -> Tuple[Set[str], Set[str]]:
    """
    Get the two vertex sets of a bipartite graph.
    Raises ValueError if graph is not bipartite.
    """
    is_bipt, coloring = is_bipartite(graph)
    if not is_bipt:
        raise ValueError("Graph is not bipartite")
    
    set_u = {v for v, c in coloring.items() if c == 0}
    set_w = {v for v, c in coloring.items() if c == 1}
    return set_u, set_w
 
 
def maximum_bipartite_matching(
    graph: Dict[str, List[str]],
    left_vertices: Set[str]
) -> Dict[str, str]:
    """
    Find maximum matching in a bipartite graph using augmenting paths.
    
    Args:
        graph: Bipartite graph as adjacency list
        left_vertices: Vertices in the 'left' partition
    
    Returns:
        Matching as dict: {left_vertex: matched_right_vertex}
    """
    match_left: Dict[str, Optional[str]] = {v: None for v in left_vertices}
    match_right: Dict[str, Optional[str]] = {}
    
    def dfs(u: str, visited: Set[str]) -> bool:
        for v in graph.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            
            # If v is unmatched or can be rematched
            if v not in match_right or dfs(match_right[v], visited):
                match_left[u] = v
                match_right[v] = u
                return True
        return False
    
    for u in left_vertices:
        dfs(u, set())
    
    return {u: v for u, v in match_left.items() if v is not None}
 
 
# Example: Student-Course bipartite graph
student_courses = {
    'Alice': ['Math', 'Physics', 'CS'],
    'Bob': ['Math', 'Chemistry'],
    'Carol': ['CS', 'Biology'],
    'Dan': ['Physics', 'Chemistry'],
    'Math': ['Alice', 'Bob'],
    'Physics': ['Alice', 'Dan'],
    'CS': ['Alice', 'Carol'],
    'Chemistry': ['Bob', 'Dan'],
    'Biology': ['Carol']
}
 
is_bipt, coloring = is_bipartite(student_courses)
print(f"Is bipartite: {is_bipt}")
 
if is_bipt:
    students, courses = get_bipartite_sets(student_courses)
    print(f"Students: {students}")
    print(f"Courses: {courses}")
 
# Maximum matching example (job assignment)
workers_jobs = {
    'W1': ['J1', 'J2'],
    'W2': ['J1', 'J3'],
    'W3': ['J2', 'J3'],
    'J1': ['W1', 'W2'],
    'J2': ['W1', 'W3'],
    'J3': ['W2', 'W3']
}
 
matching = maximum_bipartite_matching(workers_jobs, {'W1', 'W2', 'W3'})
print(f"\nMaximum matching: {matching}")
# Output: Each worker assigned to a different job

Directed Acyclic Graphs (DAGs)

We touched on DAGs in the directed graphs page, but they're important enough to warrant deeper exploration. A Directed Acyclic Graph (DAG) is a directed graph with no directed cycles—you can never follow edges in a loop back to where you started.

Key Properties:

Topological Ordering Exists: Vertices can be linearly ordered such that for every edge (u, v), u appears before v
At Least One Source: A DAG always has at least one vertex with in-degree 0 (no incoming edges)
At Least One Sink: A DAG always has at least one vertex with out-degree 0 (no outgoing edges)
Unique Longest/Shortest Paths: Many path problems have efficient solutions on DAGs
No Infinite Loops: Algorithms can always terminate when following edges

Why DAGs Are Special:

DAGs occupy a sweet spot between trees (too restrictive—single path between nodes) and general digraphs (too general—cycles complicate everything). Many real-world relationships are acyclic: time flows forward, dependencies must be resolved, inheritance is typically non-circular.

DAG Applications

•Build Systems: Task dependencies in Make, Gradle, npm scripts. Topological sort gives valid build order.
•Version Control: Git's commit history is a DAG. Commits have parent(s), but cannot be their own ancestor.
•Course Prerequisites: Courses form a DAG of prerequisites. Topological sort gives valid course sequence.
•Spreadsheet Calculation: Cell dependencies form a DAG. Evaluate in topological order.
•Neural Networks: Many architectures (feedforward, transformers) are DAGs of layers/operations.
•Expression Evaluation: Abstract syntax trees (ASTs) and expression DAGs enable efficient evaluation.
•Data Pipelines: ETL processes, Apache Airflow workflows—tasks depend on upstream tasks completing.

DAG Relaxation

Shortest paths in a DAG can be computed in O(V + E) time—better than Dijkstra's O((V+E) log V)! Process vertices in topological order, relaxing outgoing edges. Because there are no cycles, each vertex is processed exactly once.

dag_algorithms.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
from typing import Dict, List, Tuple
from collections import deque
import math
 
def topological_sort_kahn(graph: Dict[str, List[str]]) -> List[str]:
    """
    Topological sort using Kahn's algorithm (BFS-based).
    
    Returns list of vertices in topological order.
    Raises ValueError if graph has a cycle.
    """
    # Compute in-degrees
    in_degree = {v: 0 for v in graph}
    for u, neighbors in graph.items():
        for v in neighbors:
            if v not in in_degree:
                in_degree[v] = 0
            in_degree[v] += 1
    
    # Start with sources (in-degree 0)
    queue = deque([v for v, d in in_degree.items() if d == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) != len(in_degree):
        raise ValueError("Graph contains a cycle - not a DAG")
    
    return result
 
 
def dag_shortest_paths(
    graph: Dict[str, List[Tuple[str, float]]], 
    start: str
) -> Dict[str, float]:
    """
    Find shortest paths from start in a weighted DAG.
    
    Time Complexity: O(V + E) — better than Dijkstra!
    
    Args:
        graph: Weighted adjacency list: vertex -> [(neighbor, weight), ...]
        start: Source vertex
    
    Returns:
        Dict of shortest distances from start
    """
    # Build unweighted graph for topological sort
    unweighted = {v: [u for u, _ in neighbors] for v, neighbors in graph.items()}
    
    try:
        topo_order = topological_sort_kahn(unweighted)
    except ValueError:
        raise ValueError("Graph is not a DAG")
    
    # Initialize distances
    dist = {v: math.inf for v in graph}
    dist[start] = 0
    
    # Process in topological order
    for u in topo_order:
        if dist[u] == math.inf:
            continue  # Unreachable from start
        
        for v, weight in graph.get(u, []):
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    return dist
 
 
def dag_longest_path(
    graph: Dict[str, List[Tuple[str, float]]], 
    start: str
) -> Dict[str, float]:
    """
    Find longest paths from start in a weighted DAG.
    (Impossible in general graphs due to cycles, but easy in DAGs!)
    """
    unweighted = {v: [u for u, _ in neighbors] for v, neighbors in graph.items()}
    topo_order = topological_sort_kahn(unweighted)
    
    dist = {v: -math.inf for v in graph}
    dist[start] = 0
    
    for u in topo_order:
        if dist[u] == -math.inf:
            continue
        
        for v, weight in graph.get(u, []):
            if dist[u] + weight > dist[v]:
                dist[v] = dist[u] + weight
    
    return dist
 
 
# Example: Project task dependencies
tasks = {
    'design': [('implement', 5)],
    'implement': [('test', 3), ('document', 2)],
    'test': [('deploy', 1)],
    'document': [('deploy', 1)],
    'deploy': []
}
 
print("Topological order:", topological_sort_kahn({v: [u for u,_ in n] for v, n in tasks.items()}))
# Output: ['design', 'implement', 'test', 'document', 'deploy'] or similar valid order
 
print("\nShortest paths from 'design':")
shortest = dag_shortest_paths(tasks, 'design')
for v, d in shortest.items():
    print(f"  {v}: {d}")
 
print("\nLongest paths from 'design' (critical path):")
longest = dag_longest_path(tasks, 'design')
for v, d in longest.items():
    if d > -math.inf:
        print(f"  {v}: {d}")

Other Special Graph Types

Several other special graph classifications arise frequently in theory and practice:

Planar Graphs:

A graph that can be drawn on a plane without edge crossings. By Euler's formula: V - E + F = 2 (where F is the number of faces). This implies E ≤ 3V - 6 for simple planar graphs. Examples: road networks (when viewed on a map), circuit board layouts.

Trees and Forests:

A tree is a connected acyclic undirected graph. Has exactly V - 1 edges. Unique path between every pair of vertices. A forest is a disjoint union of trees (acyclic but not necessarily connected).

Complete Graphs (K_n):

Every pair of vertices is connected by an edge. Has n(n-1)/2 edges. Maximum number of edges for a simple graph.

Structural Types

•k-Regular Graph: Every vertex has exactly degree k
•Eulerian Graph: Contains a cycle visiting every edge exactly once
•Hamiltonian Graph: Contains a cycle visiting every vertex exactly once
•Chordal Graph: Every cycle of length ≥ 4 has a chord
•Interval Graph: Intersection graph of intervals on a line

Application-Driven Types

•Flow Networks: Digraphs with edge capacities, source, and sink
•Labeled Graphs: Edges and/or vertices have labels or types
•Temporal Graphs: Edges have time validity (exist only at certain times)
•Signed Graphs: Edges are positive or negative (friend/enemy networks)
•Attributed Graphs: Vertices and edges have feature vectors

Exploiting Special Structure

Recognizing that your graph belongs to a special class can unlock efficient algorithms. NP-hard problems on general graphs often become polynomial-time solvable on trees, planar graphs, or chordal graphs. Always ask: 'Does my graph have special structure I can exploit?'

Sparse vs Dense Graphs:

Though not a structural classification, sparsity significantly impacts algorithm choice:

Sparse: E = O(V) or E = O(V log V). Most real-world graphs. Adjacency list preferred. BFS/DFS are O(V + E) ≈ O(V).
Dense: E = Θ(V²). Approaches complete graph. Adjacency matrix competitive. Some algorithms become O(V²) regardless of representation.

Implicit Graphs:

Sometimes graphs aren't stored explicitly—they're generated on-demand. Puzzle state spaces, combinatorial search spaces, and procedurally generated game worlds use implicit graphs. You define edges via transition functions, not stored adjacency.

Summary: Graph Types Classification

We've completed our comprehensive tour of graph types—from the fundamental directed/undirected/weighted classifications to specialized structures that model specific real-world phenomena. Let's consolidate everything:

Key Takeaways

•Directed graphs have one-way edges; undirected graphs have bidirectional edges; mixed graphs combine both.
•Weighted graphs assign values to edges; algorithm choice depends critically on weight signs (positive vs negative).
•Multigraphs allow multiple edges between same vertices; pseudographs additionally allow self-loops.
•Hypergraphs generalize edges to connect any number of vertices, modeling group relationships.
•Bipartite graphs partition vertices into two sets with edges only between sets—enabling matching algorithms.
•DAGs have no cycles, enabling topological sort and linear-time path algorithms—ubiquitous in dependencies and workflows.
•Special structures like planar, complete, and sparse graphs enable tailored algorithms with better complexity.

Module Complete:

You now have a comprehensive understanding of graph types and classifications. You can:

Recognize what type of graph best models a given problem
Choose appropriate data structures for each graph type
Select algorithms that exploit special graph properties
Understand the trade-offs between different graph representations

This knowledge forms the foundation for the graph algorithms we'll explore in subsequent chapters—BFS, DFS, shortest paths, spanning trees, and more.

Module Complete

Congratulations! You've mastered graph type classification. You understand directed vs undirected, weighted vs unweighted, simple vs multi-edge, and numerous special types like bipartite graphs, DAGs, and hypergraphs. You're now prepared to apply the right graph model to any problem domain.

Mixed and Special Graph Types

Beyond the Basics: Specialized Graph Structures

What You Will Learn

Mixed Graphs

In many real-world networks, some connections are inherently one-way while others are bidirectional. A mixed graph combines directed and undirected edges in a single structure.

Definition:

A mixed graph G is defined as G = (V, E_d, E_u), where:

V is a finite set of vertices
E_d is a set of directed edges (arcs): ordered pairs (u, v)
E_u is a set of undirected edges: unordered pairs {u, v}

Directed and undirected edges coexist, each behaving according to its type.

Real-World Examples:

Road Networks: Most roads are bidirectional (undirected), but one-way streets are directed. A realistic road graph is mixed.
Social Networks: Friendships might be undirected (mutual), while 'follows' are directed (asymmetric). A combined model is mixed.
Academic Citations + Collaboration: Co-authorship is undirected; citations are directed. Combining both creates a mixed graph.

Handling Mixed Graphs

mixed_graph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from typing import Dict, List, Set, Tuple
 
class MixedGraph:
    """
    A graph with both directed and undirected edges.
    
    Internally, we store:
    - directed_out[u] = list of vertices v where (u, v) is a directed edge
    - undirected[u] = list of vertices v where {u, v} is undirected
    """
    def __init__(self):
        self.directed_out: Dict[str, List[str]] = {}
        self.undirected: Dict[str, List[str]] = {}
    
    def add_vertex(self, v: str):
        if v not in self.directed_out:
            self.directed_out[v] = []
        if v not in self.undirected:
            self.undirected[v] = []
    
    def add_directed_edge(self, u: str, v: str):
        """Add a one-way edge from u to v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.directed_out[u].append(v)
    
    def add_undirected_edge(self, u: str, v: str):
        """Add a two-way edge between u and v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.undirected[u].append(v)
        self.undirected[v].append(u)
    
    def get_outgoing_neighbors(self, u: str) -> List[str]:
        """Get all vertices reachable from u in one step."""
        # Directed: outgoing edges
        # Undirected: both directions
        return self.directed_out.get(u, []) + self.undirected.get(u, [])
    
    def get_incoming_neighbors(self, u: str) -> List[str]:
        """Get all vertices that can reach u in one step."""
        incoming = list(self.undirected.get(u, []))  # Undirected edges
        # Check all directed edges pointing to u
        for v, neighbors in self.directed_out.items():
            if u in neighbors:
                incoming.append(v)
        return incoming
    
    def to_pure_directed(self) -> Dict[str, List[str]]:
        """
        Convert to pure directed graph by doubling undirected edges.
        Useful for applying directed-graph algorithms.
        """
        result: Dict[str, List[str]] = {}
        for v in self.directed_out:
            result[v] = list(self.directed_out[v])  # Copy directed edges
            result[v].extend(self.undirected[v])     # Add undirected as directed
        return result
 
 
# Example: Road network with one-way streets
road_network = MixedGraph()
 
# Bidirectional roads
road_network.add_undirected_edge('A', 'B')
road_network.add_undirected_edge('B', 'C')
road_network.add_undirected_edge('C', 'D')
 
# One-way streets
road_network.add_directed_edge('D', 'A')  # D -> A only
road_network.add_directed_edge('B', 'D')  # B -> D only
 
print("From B, can reach:", road_network.get_outgoing_neighbors('B'))
# Output: ['D', 'A', 'C'] — can go to D (directed), A and C (undirected)
 
print("Can reach B from:", road_network.get_incoming_neighbors('B'))
# Output: ['A', 'C'] — A and C via undirected edges only
 
print("Pure directed version:", road_network.to_pure_directed())

Multigraphs and Pseudographs

Standard simple graphs allow at most one edge between any pair of vertices and no edges from a vertex to itself. But real-world scenarios often violate these constraints.

Multigraph:

A multigraph allows multiple edges (also called parallel edges) between the same pair of vertices. Each edge is distinct, potentially with different properties (weights, labels).

Example Applications:

Transportation: Multiple flights between same cities at different times/prices
Communication: Multiple channels or links between same network nodes
Electrical circuits: Multiple resistors in parallel between same junctions

Pseudograph:

A pseudograph allows both multiple edges AND self-loops (edges from a vertex to itself).

Example Applications:

State machines: A state can transition to itself (self-loop)
Network routing: A packet can loop back at certain nodes
Graph coloring with constraints: Self-loops represent additional restrictions

Graph Type Comparison
Graph Type	Multiple Edges	Self-Loops	Example
Simple Graph	❌	❌	Basic graph theory, most algorithms
Multigraph	✅	❌	Multiple flights between cities
Pseudograph	✅	✅	State machines with self-transitions
Simple Pseudograph	❌	✅	Graph with only self-loops allowed

Algorithm Implications

Representation Strategies:

For multigraphs, the standard adjacency list and matrix need modification:

Adjacency List for Multigraph: Store edges as objects with IDs, or maintain a list of (neighbor, edge_id, properties) tuples.

Adjacency Matrix for Multigraph: Instead of boolean values, store edge counts or lists of edge IDs.

Edge List Representation: Often the cleanest for multigraphs—simply list all edges, even duplicates between same vertices. Each edge is a distinct entity.

multigraph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from typing import Dict, List, Tuple, Any
from collections import defaultdict
 
class Multigraph:
    """
    A graph allowing multiple edges between same vertex pairs.
    Each edge has a unique ID and optional properties.
    """
    def __init__(self):
        self.vertices: set = set()
        self.edges: Dict[int, Tuple[str, str, Dict[str, Any]]] = {}
        self.adjacency: Dict[str, List[int]] = defaultdict(list)  # vertex -> edge IDs
        self.next_edge_id = 0
    
    def add_vertex(self, v: str):
        self.vertices.add(v)
        if v not in self.adjacency:
            self.adjacency[v] = []
    
    def add_edge(self, u: str, v: str, **properties) -> int:
        """
        Add an edge from u to v with optional properties.
        Returns the unique edge ID.
        """
        self.add_vertex(u)
        self.add_vertex(v)
        
        edge_id = self.next_edge_id
        self.next_edge_id += 1
        
        self.edges[edge_id] = (u, v, properties)
        self.adjacency[u].append(edge_id)
        if u != v:  # Undirected: add reverse (for directed multigraph, remove this)
            self.adjacency[v].append(edge_id)
        
        return edge_id
    
    def get_edges_between(self, u: str, v: str) -> List[Tuple[int, Dict[str, Any]]]:
        """Get all edges (with IDs and properties) between u and v."""
        result = []
        for edge_id in self.adjacency.get(u, []):
            eu, ev, props = self.edges[edge_id]
            if (eu == u and ev == v) or (eu == v and ev == u):
                result.append((edge_id, props))
        return result
    
    def edge_count_between(self, u: str, v: str) -> int:
        """Count edges between u and v."""
        return len(self.get_edges_between(u, v))
    
    def get_neighbors_with_edges(self, u: str) -> Dict[str, List[int]]:
        """Get neighbors with edge IDs for each connection."""
        neighbors: Dict[str, List[int]] = defaultdict(list)
        for edge_id in self.adjacency.get(u, []):
            eu, ev, _ = self.edges[edge_id]
            neighbor = ev if eu == u else eu
            neighbors[neighbor].append(edge_id)
        return dict(neighbors)
 
 
# Example: Multiple flights between cities
flights = Multigraph()
 
# Multiple flights from NYC to LA
flights.add_edge('NYC', 'LA', airline='United', price=350, time='6:00')
flights.add_edge('NYC', 'LA', airline='Delta', price=380, time='9:30')
flights.add_edge('NYC', 'LA', airline='JetBlue', price=320, time='14:00')
 
# Single flight each way for other routes
flights.add_edge('NYC', 'Chicago', airline='United', price=180, time='8:00')
flights.add_edge('LA', 'Chicago', airline='American', price=200, time='10:00')
 
print(f"Flights from NYC to LA: {flights.edge_count_between('NYC', 'LA')}")
# Output: 3
 
print("NYC to LA options:")
for edge_id, props in flights.get_edges_between('NYC', 'LA'):
    print(f"  Flight {edge_id}: {props}")
 
print(f"\nNeighbors of NYC with edge counts:")
for neighbor, edge_ids in flights.get_neighbors_with_edges('NYC').items():
    print(f"  {neighbor}: {len(edge_ids)} edge(s)")

Hypergraphs

Definition:

A hypergraph H is defined as H = (V, E), where:

V is a finite set of vertices
E is a set of hyperedges, where each hyperedge e ∈ E is a subset of V: e ⊆ V

A hyperedge can contain 1 vertex (singleton), 2 vertices (standard edge), or any number of vertices.

When to Use Hypergraphs:

Hypergraphs are the right model when relationships inherently involve groups, not pairs:

Database relations: A tuple in a relational table connects multiple attribute values
Co-authorship: A paper connects all its authors (3+ can co-author a single paper)
Email threads: An email connects sender and all recipients
Group memberships: A club connects all its members
Chemical reactions: Reactants and products as a single hyperedge

Hypergraphs vs Cliques

Representation:

Incidence Matrix: For a hypergraph with n vertices and m hyperedges, the incidence matrix I is n×m where I[v][e] = 1 if vertex v ∈ hyperedge e.

Adjacency List: For each hyperedge, store the set of vertices it contains. For each vertex, store the set of hyperedges it belongs to.

Algorithms on Hypergraphs:

Many graph algorithms have hypergraph generalizations:

Connectivity: Hypergraph connectivity considers paths through hyperedges
Clustering: Hypergraph partitioning minimizes hyperedge 'cuts' (hyperedges spanning multiple clusters)
Random walks: Transition through hyperedges (pick a hyperedge containing current vertex, then move to another vertex in that hyperedge)

Hypergraph problems are often computationally harder than their graph counterparts.

hypergraph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from typing import Dict, Set, List, FrozenSet
from collections import defaultdict
 
class Hypergraph:
    """
    A hypergraph where hyperedges can connect any number of vertices.
    """
    def __init__(self):
        self.vertices: Set[str] = set()
        self.hyperedges: Dict[int, Set[str]] = {}  # edge_id -> set of vertices
        self.vertex_to_edges: Dict[str, Set[int]] = defaultdict(set)
        self.next_edge_id = 0
    
    def add_vertex(self, v: str):
        self.vertices.add(v)
    
    def add_hyperedge(self, vertices: Set[str], **properties) -> int:
        """
        Add a hyperedge connecting the given vertices.
        Returns the hyperedge ID.
        """
        for v in vertices:
            self.add_vertex(v)
        
        edge_id = self.next_edge_id
        self.next_edge_id += 1
        
        self.hyperedges[edge_id] = vertices
        for v in vertices:
            self.vertex_to_edges[v].add(edge_id)
        
        return edge_id
    
    def get_hyperedges_containing(self, v: str) -> List[int]:
        """Get all hyperedge IDs containing vertex v."""
        return list(self.vertex_to_edges.get(v, set()))
    
    def get_vertices_in_hyperedge(self, edge_id: int) -> Set[str]:
        """Get all vertices in a hyperedge."""
        return self.hyperedges.get(edge_id, set())
    
    def get_neighbors(self, v: str) -> Set[str]:
        """Get all vertices that share at least one hyperedge with v."""
        neighbors = set()
        for edge_id in self.vertex_to_edges.get(v, set()):
            neighbors.update(self.hyperedges[edge_id])
        neighbors.discard(v)  # Remove v itself
        return neighbors
    
    def to_clique_expansion(self) -> Dict[str, Set[str]]:
        """
        Convert to standard graph by replacing each hyperedge
        with a clique connecting all its vertices.
        """
        adjacency: Dict[str, Set[str]] = defaultdict(set)
        for edge_id, vertices in self.hyperedges.items():
            vertex_list = list(vertices)
            for i, u in enumerate(vertex_list):
                for j, v in enumerate(vertex_list):
                    if i != j:
                        adjacency[u].add(v)
        return dict(adjacency)
 
 
# Example: Academic paper co-authorship
papers = Hypergraph()
 
# Paper 1: Three authors
papers.add_hyperedge({'Alice', 'Bob', 'Carol'})
 
# Paper 2: Two authors (standard edge)
papers.add_hyperedge({'Alice', 'Dan'})
 
# Paper 3: Four authors
papers.add_hyperedge({'Bob', 'Carol', 'Eve', 'Frank'})
 
# Paper 4: Solo paper (single-vertex hyperedge)
papers.add_hyperedge({'Alice'})
 
print("Alice's co-authors:", papers.get_neighbors('Alice'))
# Output: {'Bob', 'Carol', 'Dan'}
 
print("Hyperedges containing Bob:", papers.get_hyperedges_containing('Bob'))
 
print("\nClique expansion:")
clique_graph = papers.to_clique_expansion()
for v, neighbors in clique_graph.items():
    print(f"  {v}: {neighbors}")

Bipartite Graphs

Many problems involve two distinct types of entities where relationships only exist between types, never within. Bipartite graphs formalize this structure.

Definition:

Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

Real-World Examples:

Job Matching: Workers (U) and jobs (W); edges connect workers to jobs they're qualified for
Recommendation Systems: Users (U) and items (W); edges represent user-item interactions
Course Enrollment: Students (U) and courses (W); edges represent enrollment
Graph Coloring: Bipartite = 2-colorable (can color vertices with 2 colors such that no adjacent vertices share a color)

Bipartite Check via BFS

Bipartite Matching:

The most important algorithm on bipartite graphs is maximum bipartite matching: find the maximum number of edges such that no vertex appears in more than one selected edge.

Applications:

Job assignment: Assign workers to jobs maximizing assignments
Stable marriage: Match preferences between two groups
Resource allocation: Assign tasks to resources

Complete Bipartite Graph K_{m,n}:

A complete bipartite graph has every vertex in U connected to every vertex in W. With |U| = m and |W| = n, it has m×n edges. This is the densest possible bipartite graph.

bipartite.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from typing import Dict, List, Set, Optional, Tuple
from collections import deque
 
def is_bipartite(graph: Dict[str, List[str]]) -> Tuple[bool, Optional[Dict[str, int]]]:
    """
    Check if a graph is bipartite using BFS 2-coloring.
    
    Returns:
        (is_bipartite, coloring)
        coloring maps each vertex to 0 or 1 if bipartite, None otherwise
    """
    color: Dict[str, int] = {}
    
    for start in graph:
        if start in color:
            continue
        
        # BFS from uncolored vertex
        queue = deque([start])
        color[start] = 0
        
        while queue:
            vertex = queue.popleft()
            for neighbor in graph.get(vertex, []):
                if neighbor not in color:
                    color[neighbor] = 1 - color[vertex]  # Alternate colors
                    queue.append(neighbor)
                elif color[neighbor] == color[vertex]:
                    return False, None  # Same color = not bipartite
    
    return True, color
 
 
def get_bipartite_sets(graph: Dict[str, List[str]]) -> Tuple[Set[str], Set[str]]:
    """
    Get the two vertex sets of a bipartite graph.
    Raises ValueError if graph is not bipartite.
    """
    is_bipt, coloring = is_bipartite(graph)
    if not is_bipt:
        raise ValueError("Graph is not bipartite")
    
    set_u = {v for v, c in coloring.items() if c == 0}
    set_w = {v for v, c in coloring.items() if c == 1}
    return set_u, set_w
 
 
def maximum_bipartite_matching(
    graph: Dict[str, List[str]],
    left_vertices: Set[str]
) -> Dict[str, str]:
    """
    Find maximum matching in a bipartite graph using augmenting paths.
    
    Args:
        graph: Bipartite graph as adjacency list
        left_vertices: Vertices in the 'left' partition
    
    Returns:
        Matching as dict: {left_vertex: matched_right_vertex}
    """
    match_left: Dict[str, Optional[str]] = {v: None for v in left_vertices}
    match_right: Dict[str, Optional[str]] = {}
    
    def dfs(u: str, visited: Set[str]) -> bool:
        for v in graph.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            
            # If v is unmatched or can be rematched
            if v not in match_right or dfs(match_right[v], visited):
                match_left[u] = v
                match_right[v] = u
                return True
        return False
    
    for u in left_vertices:
        dfs(u, set())
    
    return {u: v for u, v in match_left.items() if v is not None}
 
 
# Example: Student-Course bipartite graph
student_courses = {
    'Alice': ['Math', 'Physics', 'CS'],
    'Bob': ['Math', 'Chemistry'],
    'Carol': ['CS', 'Biology'],
    'Dan': ['Physics', 'Chemistry'],
    'Math': ['Alice', 'Bob'],
    'Physics': ['Alice', 'Dan'],
    'CS': ['Alice', 'Carol'],
    'Chemistry': ['Bob', 'Dan'],
    'Biology': ['Carol']
}
 
is_bipt, coloring = is_bipartite(student_courses)
print(f"Is bipartite: {is_bipt}")
 
if is_bipt:
    students, courses = get_bipartite_sets(student_courses)
    print(f"Students: {students}")
    print(f"Courses: {courses}")
 
# Maximum matching example (job assignment)
workers_jobs = {
    'W1': ['J1', 'J2'],
    'W2': ['J1', 'J3'],
    'W3': ['J2', 'J3'],
    'J1': ['W1', 'W2'],
    'J2': ['W1', 'W3'],
    'J3': ['W2', 'W3']
}
 
matching = maximum_bipartite_matching(workers_jobs, {'W1', 'W2', 'W3'})
print(f"\nMaximum matching: {matching}")
# Output: Each worker assigned to a different job

Directed Acyclic Graphs (DAGs)

Key Properties:

Topological Ordering Exists: Vertices can be linearly ordered such that for every edge (u, v), u appears before v
At Least One Source: A DAG always has at least one vertex with in-degree 0 (no incoming edges)
At Least One Sink: A DAG always has at least one vertex with out-degree 0 (no outgoing edges)
Unique Longest/Shortest Paths: Many path problems have efficient solutions on DAGs
No Infinite Loops: Algorithms can always terminate when following edges

Why DAGs Are Special:

DAG Applications

•Build Systems: Task dependencies in Make, Gradle, npm scripts. Topological sort gives valid build order.
•Version Control: Git's commit history is a DAG. Commits have parent(s), but cannot be their own ancestor.
•Course Prerequisites: Courses form a DAG of prerequisites. Topological sort gives valid course sequence.
•Spreadsheet Calculation: Cell dependencies form a DAG. Evaluate in topological order.
•Neural Networks: Many architectures (feedforward, transformers) are DAGs of layers/operations.
•Expression Evaluation: Abstract syntax trees (ASTs) and expression DAGs enable efficient evaluation.
•Data Pipelines: ETL processes, Apache Airflow workflows—tasks depend on upstream tasks completing.

DAG Relaxation

dag_algorithms.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
from typing import Dict, List, Tuple
from collections import deque
import math
 
def topological_sort_kahn(graph: Dict[str, List[str]]) -> List[str]:
    """
    Topological sort using Kahn's algorithm (BFS-based).
    
    Returns list of vertices in topological order.
    Raises ValueError if graph has a cycle.
    """
    # Compute in-degrees
    in_degree = {v: 0 for v in graph}
    for u, neighbors in graph.items():
        for v in neighbors:
            if v not in in_degree:
                in_degree[v] = 0
            in_degree[v] += 1
    
    # Start with sources (in-degree 0)
    queue = deque([v for v, d in in_degree.items() if d == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) != len(in_degree):
        raise ValueError("Graph contains a cycle - not a DAG")
    
    return result
 
 
def dag_shortest_paths(
    graph: Dict[str, List[Tuple[str, float]]], 
    start: str
) -> Dict[str, float]:
    """
    Find shortest paths from start in a weighted DAG.
    
    Time Complexity: O(V + E) — better than Dijkstra!
    
    Args:
        graph: Weighted adjacency list: vertex -> [(neighbor, weight), ...]
        start: Source vertex
    
    Returns:
        Dict of shortest distances from start
    """
    # Build unweighted graph for topological sort
    unweighted = {v: [u for u, _ in neighbors] for v, neighbors in graph.items()}
    
    try:
        topo_order = topological_sort_kahn(unweighted)
    except ValueError:
        raise ValueError("Graph is not a DAG")
    
    # Initialize distances
    dist = {v: math.inf for v in graph}
    dist[start] = 0
    
    # Process in topological order
    for u in topo_order:
        if dist[u] == math.inf:
            continue  # Unreachable from start
        
        for v, weight in graph.get(u, []):
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    return dist
 
 
def dag_longest_path(
    graph: Dict[str, List[Tuple[str, float]]], 
    start: str
) -> Dict[str, float]:
    """
    Find longest paths from start in a weighted DAG.
    (Impossible in general graphs due to cycles, but easy in DAGs!)
    """
    unweighted = {v: [u for u, _ in neighbors] for v, neighbors in graph.items()}
    topo_order = topological_sort_kahn(unweighted)
    
    dist = {v: -math.inf for v in graph}
    dist[start] = 0
    
    for u in topo_order:
        if dist[u] == -math.inf:
            continue
        
        for v, weight in graph.get(u, []):
            if dist[u] + weight > dist[v]:
                dist[v] = dist[u] + weight
    
    return dist
 
 
# Example: Project task dependencies
tasks = {
    'design': [('implement', 5)],
    'implement': [('test', 3), ('document', 2)],
    'test': [('deploy', 1)],
    'document': [('deploy', 1)],
    'deploy': []
}
 
print("Topological order:", topological_sort_kahn({v: [u for u,_ in n] for v, n in tasks.items()}))
# Output: ['design', 'implement', 'test', 'document', 'deploy'] or similar valid order
 
print("\nShortest paths from 'design':")
shortest = dag_shortest_paths(tasks, 'design')
for v, d in shortest.items():
    print(f"  {v}: {d}")
 
print("\nLongest paths from 'design' (critical path):")
longest = dag_longest_path(tasks, 'design')
for v, d in longest.items():
    if d > -math.inf:
        print(f"  {v}: {d}")

Other Special Graph Types

Several other special graph classifications arise frequently in theory and practice:

Planar Graphs:

Trees and Forests:

A tree is a connected acyclic undirected graph. Has exactly V - 1 edges. Unique path between every pair of vertices. A forest is a disjoint union of trees (acyclic but not necessarily connected).

Complete Graphs (K_n):

Every pair of vertices is connected by an edge. Has n(n-1)/2 edges. Maximum number of edges for a simple graph.

Structural Types

•k-Regular Graph: Every vertex has exactly degree k
•Eulerian Graph: Contains a cycle visiting every edge exactly once
•Hamiltonian Graph: Contains a cycle visiting every vertex exactly once
•Chordal Graph: Every cycle of length ≥ 4 has a chord
•Interval Graph: Intersection graph of intervals on a line

Application-Driven Types

•Flow Networks: Digraphs with edge capacities, source, and sink
•Labeled Graphs: Edges and/or vertices have labels or types
•Temporal Graphs: Edges have time validity (exist only at certain times)
•Signed Graphs: Edges are positive or negative (friend/enemy networks)
•Attributed Graphs: Vertices and edges have feature vectors

Exploiting Special Structure

Sparse vs Dense Graphs:

Though not a structural classification, sparsity significantly impacts algorithm choice:

Sparse: E = O(V) or E = O(V log V). Most real-world graphs. Adjacency list preferred. BFS/DFS are O(V + E) ≈ O(V).
Dense: E = Θ(V²). Approaches complete graph. Adjacency matrix competitive. Some algorithms become O(V²) regardless of representation.

Implicit Graphs:

Summary: Graph Types Classification

Key Takeaways

•Directed graphs have one-way edges; undirected graphs have bidirectional edges; mixed graphs combine both.
•Weighted graphs assign values to edges; algorithm choice depends critically on weight signs (positive vs negative).
•Multigraphs allow multiple edges between same vertices; pseudographs additionally allow self-loops.
•Hypergraphs generalize edges to connect any number of vertices, modeling group relationships.
•Bipartite graphs partition vertices into two sets with edges only between sets—enabling matching algorithms.
•DAGs have no cycles, enabling topological sort and linear-time path algorithms—ubiquitous in dependencies and workflows.
•Special structures like planar, complete, and sparse graphs enable tailored algorithms with better complexity.

Module Complete:

You now have a comprehensive understanding of graph types and classifications. You can:

Recognize what type of graph best models a given problem
Choose appropriate data structures for each graph type
Select algorithms that exploit special graph properties
Understand the trade-offs between different graph representations

This knowledge forms the foundation for the graph algorithms we'll explore in subsequent chapters—BFS, DFS, shortest paths, spanning trees, and more.

Module Complete