Graph Definition Terminology - Learning Module

Loading content...

0/279

Self-Loops and Multi-Edges

When Graphs Get Complicated

So far, we've implicitly assumed graphs with "well-behaved" edges: each edge connects two different vertices, and at most one edge exists between any pair. But reality is messier.

What if a webpage links to itself? What if there are multiple flights between two cities on the same day? What if a state machine can loop back to its current state?

These scenarios require us to extend our graph vocabulary to include self-loops (edges from a vertex to itself) and multi-edges (multiple edges between the same pair of vertices). Understanding when and how to use these structures—and when to avoid them—is essential for accurate graph modeling.

What You Will Learn

By the end of this page, you will understand self-loops and their applications, recognize when multi-edges are necessary for accurate modeling, distinguish between simple graphs, multigraphs, and pseudographs, and know how self-loops affect degree calculations and graph algorithms.

What Are Self-Loops?

A self-loop (also called a loop) is an edge that connects a vertex to itself. If we denote this edge in directed notation, it's (v, v); in undirected notation, it's {v, v} (which simplifies to just {v}).

Formal Definition:

In a graph G = (V, E), an edge e ∈ E is a self-loop if both endpoints are the same vertex:

Directed: e = (v, v) for some v ∈ V
Undirected: e = {v} (a singleton set)

Visual Representation:

Self-loops are typically drawn as small circles emanating from a vertex and returning to it—like a vertex with an earring or loop attached.

Converting Mermaid diagram...

In the diagram above, vertex A has a self-loop (A → A) and vertex C has a self-loop (C → C).

Degree Counting with Self-Loops:

A subtle but important detail: a self-loop contributes 2 to the degree of its vertex (in undirected graphs). Why? Because degree counts edge endpoints incident to the vertex, and a self-loop has both endpoints at the same vertex.

This convention preserves the Handshaking Lemma: $$\sum_{v \in V} \deg(v) = 2|E|$$

If a self-loop counted as 1, the sum would be odd when |E| is odd, breaking the lemma.

Self-Loops in Directed Graphs

In directed graphs, a self-loop (v, v) contributes 1 to both in-degree AND out-degree of v. This is different from undirected where it adds 2 to deg(v). The directed handshaking lemma Σdeg⁺ = Σdeg⁻ = |E| still holds because the self-loop adds 1 to each sum.

Real-World Self-Loop Examples

Self-loops arise naturally in many domains. Recognizing them helps you model systems accurately:

State Machines:

In finite automata and state diagrams, self-loops represent state transitions that don't change the state. For example, in a vending machine state diagram, inserting more coins while in the "collecting money" state might loop back to the same state (increasing the balance).

Markov Chains:

Probability transitions where a system can stay in its current state with some probability are self-loops. A weather model might have a 70% chance of "sunny" remaining "sunny" the next day.

Web Graphs:

A webpage linking to itself (same URL) creates a self-loop. While unusual, this can happen through navigation elements or anchor links.

Dependency Graphs:

A module that references itself (perhaps through conditional imports or plugins) creates a self-loop—often indicating a design smell.

Self-Loops in Different Domains
Domain	Self-Loop Meaning	Example
State Machine	Action that stays in same state	Retry button in error state
Markov Chain	Probability of staying in state	70% chance rain continues
Call Graph	Recursive function call	fibonacci(n) calls fibonacci(n-1)
Web Graph	Page links to itself	Anchor link to same page
Game Graph	Pass or skip turn	Chess: repetition, skip move
Network	Loopback address	127.0.0.1 → same machine

Self-Loops and Cycles

A self-loop is the simplest possible cycle—a cycle of length 1. If you're detecting cycles in a graph, remember that a single self-loop edge creates a cycle. Many cycle detection algorithms handle self-loops as a special case.

What Are Multi-Edges?

Multi-edges (also called parallel edges or multiple edges) occur when two or more distinct edges connect the same pair of vertices.

Formal Definition:

In a graph G = (V, E), multi-edges exist when E contains multiple copies of the same edge:

Undirected: Multiple edges {u, v}
Directed: Multiple edges (u, v) in the same direction

Since sets cannot contain duplicates, we need a modified definition. We can either:

Use a multiset for E (allowing duplicates)
Use an edge set with unique edge IDs: E = {(u, v, id₁), (u, v, id₂), ...}

When Multi-Edges Matter:

Multi-edges are necessary when you need to distinguish between different connections with the same endpoints—such as multiple flights, parallel roads, or different types of relationships.

Converting Mermaid diagram...

In the diagram above, there are three distinct edges from NYC to LAX, representing three different flights. These are multi-edges—multiple edges with the same endpoints but different identities.

Contrast with Simple Graphs:

In a simple graph, at most one edge exists between any pair of vertices. This simplifies many algorithms because you only need to track "connected or not," not "how many connections." However, simple graphs lose information when the number of connections matters.

Multi-Edges vs. Edge Weights

Multi-edges and weighted edges solve related but different problems. A weighted edge (u, v, weight=3) says 'this connection has magnitude 3.' Three multi-edges between u and v say 'there are three distinct connections.' Choose based on your domain: do you need to track individual connections, or just aggregate magnitude?

Real-World Multi-Edge Examples

Multi-edges appear whenever multiple distinct relationships exist between the same entities:

Transportation Networks:

Between two cities, there might be multiple flights (with different airlines, times, or prices), multiple train routes (express vs. local), or multiple roads (highway vs. local streets). Each is a distinct edge.

Communication Networks:

Two servers might have multiple network links for redundancy. Each link is a separate edge with its own capacity, latency, and failure characteristics.

Social Networks (Multi-Relational):

Two people might be connected through multiple relationship types: friends on Facebook, colleagues on LinkedIn, and co-authors on papers. These are logically distinct edges.

Knowledge Graphs:

Entities can have multiple relationships. (Einstein, Germany) might have edges labeled "birthplace," "citizenship," and "fled from"—three distinct connections.

Multi-Edges in Different Domains
Domain	Multi-Edge Meaning	Why Not Use Weights?
Airline Routes	Different flights (times, airlines)	Each flight has its own properties (time, price)
Redundant Links	Parallel network connections	Each link can fail independently
Social Relations	Friend AND colleague AND family	Different relationship types, not quantities
Knowledge Graph	Multiple relationship types	Each edge has different semantics
Circuit Design	Parallel wires	Each wire has its own properties

Modeling Decision

When deciding between multi-edges and weighted edges, ask: 'Do I need to reason about individual connections, or just their aggregate effect?' For flow networks, weights often suffice. For scheduling, routing, or relationship analysis, multi-edges may be necessary.

Graph Types: Simple, Multi, Pseudo

Graph theory classifies graphs based on whether they allow self-loops and multi-edges:

Simple Graph:

No self-loops
No multi-edges
At most one edge between any pair of distinct vertices
Most commonly studied in introductory graph theory

Multigraph:

No self-loops
Multi-edges allowed
Multiple edges can connect the same pair of vertices

Pseudograph:

Self-loops allowed
Multi-edges allowed
Most general form of undirected graph

Simple Digraph:

Directed, no self-loops, no multi-edges
At most one edge (u, v) and one edge (v, u)

Multidigraph:

Directed, allows multi-edges, may or may not allow self-loops

Graph Type Classification
Graph Type	Self-Loops	Multi-Edges	Example Use Case
Simple Graph	No	No	Social network (friend/not friend)
Multigraph	No	Yes	Transportation network (multiple routes)
Pseudograph	Yes	Yes	General modeling, state machines
Simple Digraph	No	No	Dependency graph (A depends on B)
Multidigraph	Optional	Yes	Multi-relational knowledge graph

Default Assumption

In most algorithm contexts, 'graph' means 'simple graph' unless otherwise specified. Algorithms for multigraphs or pseudographs may require modifications. Always clarify assumptions when self-loops or multi-edges might be present.

Algorithm Implications

Self-loops and multi-edges affect how algorithms behave. Here are key considerations:

Cycle Detection:

Self-loops are cycles of length 1—check for them explicitly
Multi-edges don't create additional cycles (same endpoints)

Connectivity:

Self-loops don't affect connectivity (vertex already connected to itself)
Multi-edges don't change connectivity (if one edge connects, more don't add connectivity)

Shortest Path:

Self-loops with positive weight: never useful for shortest path (adds distance to stay in place)
Self-loops with zero weight: harmless but waste computation
Self-loops with negative weight: can create negative cycles
Multi-edges: only the minimum-weight edge matters for shortest path

Minimum Spanning Tree:

Self-loops: never included (don't connect new vertices)
Multi-edges: only minimum-weight edge between any pair can be in MST

self-loop-handling
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
from typing import List, Tuple, Set, Dict
from collections import deque
 
def has_cycle_with_self_loops(n: int, 
                               edges: List[Tuple[int, int]]) -> bool:
    """
    Detect if a directed graph has a cycle, including self-loops.
    Returns True if any cycle exists (including self-loops).
    """
    # Check for self-loops first (trivial cycles)
    for u, v in edges:
        if u == v:
            return True  # Self-loop found!
    
    # Build adjacency list (ignoring multi-edges for cycle detection)
    adj: Dict[int, Set[int]] = {i: set() for i in range(n)}
    for u, v in edges:
        adj[u].add(v)
    
    # Standard DFS cycle detection with colors
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    
    def dfs(node: int) -> bool:
        color[node] = GRAY  # Currently visiting
        for neighbor in adj[node]:
            if color[neighbor] == GRAY:
                return True  # Back edge → cycle
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK  # Finished
        return False
    
    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
    
    return False
 
 
def minimum_edge_for_multi_edges(edges: List[Tuple[int, int, float]]) 
                                  -> Dict[Tuple[int, int], float]:
    """
    Given edges with weights (possibly multi-edges), return
    the minimum weight edge for each pair.
    
    Useful for shortest path and MST preprocessing.
    """
    min_edge: Dict[Tuple[int, int], float] = {}
    
    for u, v, weight in edges:
        key = (u, v)
        if key not in min_edge or weight < min_edge[key]:
            min_edge[key] = weight
    
    return min_edge
 
 
# Example: Graph with self-loop
edges_with_self_loop = [(0, 1), (1, 2), (2, 2)]  # 2→2 is self-loop
print(f"Has cycle (with self-loop): {has_cycle_with_self_loops(3, edges_with_self_loop)}")
# True (because of self-loop at vertex 2)
 
# Example: Multi-edges - keep minimum
multi_edges = [
    (0, 1, 5.0),   # NYC → LA, $500
    (0, 1, 3.0),   # NYC → LA, $300 (cheaper!)
    (0, 1, 7.0),   # NYC → LA, $700
    (1, 2, 2.0),   # LA → SF, $200
]
print("Minimum edges:", minimum_edge_for_multi_edges(multi_edges))
# {(0, 1): 3.0, (1, 2): 2.0}

Always Handle Edge Cases

When implementing graph algorithms, explicitly decide how to handle self-loops and multi-edges. Either filter them out in preprocessing, or ensure your algorithm handles them correctly. Silent bugs often arise from unexpected self-loops in input data.

Implementation Considerations

How you represent graphs affects how naturally self-loops and multi-edges are handled:

Adjacency Matrix:

Self-loops: matrix[v][v] = true (or weight for weighted graphs)
Multi-edges: Can only store one edge per pair (or sum weights)
Good for: Simple graphs; bad for multigraphs

Adjacency List (Set-based):

Self-loops: Natural—just add v to its own adjacency set
Multi-edges: Sets don't allow duplicates; loses multi-edge information
Good for: Simple graphs with possible self-loops

Adjacency List (List-based):

Self-loops: Add v to its own list
Multi-edges: Lists allow duplicates; naturally supports multi-edges
Good for: Multigraphs and pseudographs

Edge List:

Self-loops: (v, v) stored like any other edge
Multi-edges: Naturally supports duplicates
Good for: All graph types; explicit edge enumeration

representation-comparison
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
from typing import List, Tuple, Dict, Set
from collections import defaultdict
 
class SimpleGraphMatrix:
    """Adjacency matrix - supports self-loops, NOT multi-edges."""
    
    def __init__(self, n: int):
        self.n = n
        self.matrix = [[False] * n for _ in range(n)]
    
    def add_edge(self, u: int, v: int):
        self.matrix[u][v] = True
        self.matrix[v][u] = True  # Undirected
    
    def add_self_loop(self, v: int):
        self.matrix[v][v] = True  # Works naturally
    
    def edge_count(self, u: int, v: int) -> int:
        # Can only return 0 or 1 - no multi-edge support
        return 1 if self.matrix[u][v] else 0
 
 
class MultiGraphAdjList:
    """Adjacency list (list-based) - supports self-loops AND multi-edges."""
    
    def __init__(self):
        self.adj: Dict[int, List[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
        if u != v:  # Don't double-add for self-loops
            self.adj[v].append(u)
    
    def edge_count(self, u: int, v: int) -> int:
        """Count edges between u and v (including multi-edges)."""
        if u == v:
            # Self-loops appear once in adjacency list
            return self.adj[u].count(v)
        else:
            # For undirected, count in one direction
            return self.adj[u].count(v)
    
    def neighbors(self, v: int) -> List[int]:
        return self.adj[v]  # May include v itself (self-loop)
 
 
class EdgeListGraph:
    """Edge list - most flexible, supports everything."""
    
    def __init__(self):
        self.edges: List[Tuple[int, int]] = []
        self.vertices: Set[int] = set()
    
    def add_edge(self, u: int, v: int):
        self.edges.append((u, v))
        self.vertices.add(u)
        self.vertices.add(v)
    
    def has_self_loop(self, v: int) -> bool:
        return any(u == v and w == v for u, w in self.edges)
    
    def count_multi_edges(self, u: int, v: int) -> int:
        """Count all edges between u and v (both directions for undirected)."""
        count = 0
        for a, b in self.edges:
            if (a == u and b == v) or (a == v and b == u):
                count += 1
        return count
 
 
# Demonstration
print("=== Simple Graph (Matrix) ===")
sg = SimpleGraphMatrix(3)
sg.add_edge(0, 1)
sg.add_edge(0, 1)  # Second edge ignored!
sg.add_self_loop(2)
print(f"Edge count 0-1: {sg.edge_count(0, 1)}")  # 1 (ignores multi)
print(f"Self-loop at 2: {sg.matrix[2][2]}")     # True
 
print("
=== Multigraph (List) ===")
mg = MultiGraphAdjList()
mg.add_edge(0, 1)
mg.add_edge(0, 1)  # Second edge stored!
mg.add_edge(0, 1)  # Third edge stored!
mg.add_edge(2, 2)  # Self-loop
print(f"Edge count 0-1: {mg.edge_count(0, 1)}")  # 3 (counts multi)
print(f"Neighbors of 0: {mg.neighbors(0)}")      # [1, 1, 1]
print(f"Neighbors of 2: {mg.neighbors(2)}")      # [2] (self-loop)

Choose Representation Wisely

If your problem might have multi-edges, use list-based adjacency or edge lists. If you want to prevent multi-edges, use set-based adjacency or matrices. The representation enforces constraints automatically.

When to Avoid vs. Embrace

Should you allow self-loops and multi-edges in your graph model? The answer depends on your problem:

Embrace Self-Loops When:

Modeling state machines where staying in a state is valid
Representing probabilities (Markov chains) with self-transitions
Working with reflexive relations (every element relates to itself)
Your domain genuinely has self-relationships

Avoid Self-Loops When:

They don't make semantic sense (e.g., "person is friend of themselves")
They complicate algorithms without adding value
Working with standard graph problems (MST, shortest path on simple graphs)

Embrace Multi-Edges When:

Different connections between same nodes have different properties
You need to count or enumerate individual connections
Modeling redundancy, parallel paths, or multiple relationship types

Avoid Multi-Edges When:

Only the existence (not quantity) of connections matters
Weights can aggregate the effect of multiple edges
Standard graph algorithms are sufficient

Use Self-Loops / Multi-Edges

•State machines with self-transitions
•Markov chains with stay probabilities
•Flight schedules with multiple daily flights
•Redundant network links
•Multi-relational knowledge graphs

Use Simple Graphs

•Social networks (friend/not friend)
•Basic dependency graphs
•Connectivity problems
•Standard shortest path queries
•Most interview/competitive programming

Default to Simple

When in doubt, start with a simple graph. You can always extend to multigraphs if needed, but unnecessary complexity makes algorithms harder to implement and debug. Most graph algorithm resources assume simple graphs.

Summary: Beyond Simple Graphs

We've explored the special cases that extend simple graphs. Let's consolidate:

Key Takeaways

•Self-loops connect a vertex to itself; they contribute 2 to degree (undirected) or 1 each to in/out-degree (directed).
•Multi-edges are multiple distinct edges between the same vertex pair; they're needed when individual connections have separate identities.
•Simple graphs have no self-loops or multi-edges; multigraphs allow multi-edges; pseudographs allow both.
•Self-loops are natural in state machines and Markov chains; multi-edges appear in transportation and multi-relational graphs.
•Algorithm implications: Self-loops are trivial cycles; multi-edges often mean taking the minimum weight for optimization problems.
•Implementation: Matrices and set-based lists don't naturally support multi-edges; list-based structures and edge lists do.
•Default to simple graphs unless your domain requires otherwise.

Module Complete:

Congratulations! You've completed the foundational vocabulary of graph theory. You now understand:

What vertices and edges are
The formal definition G = (V, E)
Adjacency, neighbors, and degree concepts
Self-loops and multi-edges as extensions

With this vocabulary, you're ready to explore graph types (directed, undirected, weighted), graph representations (adjacency matrix, adjacency list), and eventually graph algorithms (BFS, DFS, shortest paths, and more).

Module Complete

You've mastered the fundamental vocabulary of graph theory. From vertices and edges to formal definitions, adjacency relationships, and special edge types, you now speak the language of graphs fluently. This foundation will support every graph algorithm and application you encounter.

Self-Loops and Multi-Edges

When Graphs Get Complicated

So far, we've implicitly assumed graphs with "well-behaved" edges: each edge connects two different vertices, and at most one edge exists between any pair. But reality is messier.

What if a webpage links to itself? What if there are multiple flights between two cities on the same day? What if a state machine can loop back to its current state?

What You Will Learn

What Are Self-Loops?

Formal Definition:

In a graph G = (V, E), an edge e ∈ E is a self-loop if both endpoints are the same vertex:

Directed: e = (v, v) for some v ∈ V
Undirected: e = {v} (a singleton set)

Visual Representation:

Self-loops are typically drawn as small circles emanating from a vertex and returning to it—like a vertex with an earring or loop attached.

Converting Mermaid diagram...

In the diagram above, vertex A has a self-loop (A → A) and vertex C has a self-loop (C → C).

Degree Counting with Self-Loops:

This convention preserves the Handshaking Lemma: $$\sum_{v \in V} \deg(v) = 2|E|$$

If a self-loop counted as 1, the sum would be odd when |E| is odd, breaking the lemma.

Self-Loops in Directed Graphs

Real-World Self-Loop Examples

Self-loops arise naturally in many domains. Recognizing them helps you model systems accurately:

State Machines:

Markov Chains:

Probability transitions where a system can stay in its current state with some probability are self-loops. A weather model might have a 70% chance of "sunny" remaining "sunny" the next day.

Web Graphs:

A webpage linking to itself (same URL) creates a self-loop. While unusual, this can happen through navigation elements or anchor links.

Dependency Graphs:

A module that references itself (perhaps through conditional imports or plugins) creates a self-loop—often indicating a design smell.

Self-Loops in Different Domains
Domain	Self-Loop Meaning	Example
State Machine	Action that stays in same state	Retry button in error state
Markov Chain	Probability of staying in state	70% chance rain continues
Call Graph	Recursive function call	fibonacci(n) calls fibonacci(n-1)
Web Graph	Page links to itself	Anchor link to same page
Game Graph	Pass or skip turn	Chess: repetition, skip move
Network	Loopback address	127.0.0.1 → same machine

Self-Loops and Cycles

What Are Multi-Edges?

Multi-edges (also called parallel edges or multiple edges) occur when two or more distinct edges connect the same pair of vertices.

Formal Definition:

In a graph G = (V, E), multi-edges exist when E contains multiple copies of the same edge:

Undirected: Multiple edges {u, v}
Directed: Multiple edges (u, v) in the same direction

Since sets cannot contain duplicates, we need a modified definition. We can either:

Use a multiset for E (allowing duplicates)
Use an edge set with unique edge IDs: E = {(u, v, id₁), (u, v, id₂), ...}

When Multi-Edges Matter:

Multi-edges are necessary when you need to distinguish between different connections with the same endpoints—such as multiple flights, parallel roads, or different types of relationships.

Converting Mermaid diagram...

In the diagram above, there are three distinct edges from NYC to LAX, representing three different flights. These are multi-edges—multiple edges with the same endpoints but different identities.

Contrast with Simple Graphs:

Multi-Edges vs. Edge Weights

Real-World Multi-Edge Examples

Multi-edges appear whenever multiple distinct relationships exist between the same entities:

Transportation Networks:

Communication Networks:

Two servers might have multiple network links for redundancy. Each link is a separate edge with its own capacity, latency, and failure characteristics.

Social Networks (Multi-Relational):

Two people might be connected through multiple relationship types: friends on Facebook, colleagues on LinkedIn, and co-authors on papers. These are logically distinct edges.

Knowledge Graphs:

Entities can have multiple relationships. (Einstein, Germany) might have edges labeled "birthplace," "citizenship," and "fled from"—three distinct connections.

Multi-Edges in Different Domains
Domain	Multi-Edge Meaning	Why Not Use Weights?
Airline Routes	Different flights (times, airlines)	Each flight has its own properties (time, price)
Redundant Links	Parallel network connections	Each link can fail independently
Social Relations	Friend AND colleague AND family	Different relationship types, not quantities
Knowledge Graph	Multiple relationship types	Each edge has different semantics
Circuit Design	Parallel wires	Each wire has its own properties

Modeling Decision

Graph Types: Simple, Multi, Pseudo

Graph theory classifies graphs based on whether they allow self-loops and multi-edges:

Simple Graph:

No self-loops
No multi-edges
At most one edge between any pair of distinct vertices
Most commonly studied in introductory graph theory

Multigraph:

No self-loops
Multi-edges allowed
Multiple edges can connect the same pair of vertices

Pseudograph:

Self-loops allowed
Multi-edges allowed
Most general form of undirected graph

Simple Digraph:

Directed, no self-loops, no multi-edges
At most one edge (u, v) and one edge (v, u)

Multidigraph:

Directed, allows multi-edges, may or may not allow self-loops

Graph Type Classification
Graph Type	Self-Loops	Multi-Edges	Example Use Case
Simple Graph	No	No	Social network (friend/not friend)
Multigraph	No	Yes	Transportation network (multiple routes)
Pseudograph	Yes	Yes	General modeling, state machines
Simple Digraph	No	No	Dependency graph (A depends on B)
Multidigraph	Optional	Yes	Multi-relational knowledge graph

Default Assumption

Algorithm Implications

Self-loops and multi-edges affect how algorithms behave. Here are key considerations:

Cycle Detection:

Self-loops are cycles of length 1—check for them explicitly
Multi-edges don't create additional cycles (same endpoints)

Connectivity:

Self-loops don't affect connectivity (vertex already connected to itself)
Multi-edges don't change connectivity (if one edge connects, more don't add connectivity)

Shortest Path:

Self-loops with positive weight: never useful for shortest path (adds distance to stay in place)
Self-loops with zero weight: harmless but waste computation
Self-loops with negative weight: can create negative cycles
Multi-edges: only the minimum-weight edge matters for shortest path

Minimum Spanning Tree:

Self-loops: never included (don't connect new vertices)
Multi-edges: only minimum-weight edge between any pair can be in MST

self-loop-handling
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
from typing import List, Tuple, Set, Dict
from collections import deque
 
def has_cycle_with_self_loops(n: int, 
                               edges: List[Tuple[int, int]]) -> bool:
    """
    Detect if a directed graph has a cycle, including self-loops.
    Returns True if any cycle exists (including self-loops).
    """
    # Check for self-loops first (trivial cycles)
    for u, v in edges:
        if u == v:
            return True  # Self-loop found!
    
    # Build adjacency list (ignoring multi-edges for cycle detection)
    adj: Dict[int, Set[int]] = {i: set() for i in range(n)}
    for u, v in edges:
        adj[u].add(v)
    
    # Standard DFS cycle detection with colors
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    
    def dfs(node: int) -> bool:
        color[node] = GRAY  # Currently visiting
        for neighbor in adj[node]:
            if color[neighbor] == GRAY:
                return True  # Back edge → cycle
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK  # Finished
        return False
    
    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
    
    return False
 
 
def minimum_edge_for_multi_edges(edges: List[Tuple[int, int, float]]) 
                                  -> Dict[Tuple[int, int], float]:
    """
    Given edges with weights (possibly multi-edges), return
    the minimum weight edge for each pair.
    
    Useful for shortest path and MST preprocessing.
    """
    min_edge: Dict[Tuple[int, int], float] = {}
    
    for u, v, weight in edges:
        key = (u, v)
        if key not in min_edge or weight < min_edge[key]:
            min_edge[key] = weight
    
    return min_edge
 
 
# Example: Graph with self-loop
edges_with_self_loop = [(0, 1), (1, 2), (2, 2)]  # 2→2 is self-loop
print(f"Has cycle (with self-loop): {has_cycle_with_self_loops(3, edges_with_self_loop)}")
# True (because of self-loop at vertex 2)
 
# Example: Multi-edges - keep minimum
multi_edges = [
    (0, 1, 5.0),   # NYC → LA, $500
    (0, 1, 3.0),   # NYC → LA, $300 (cheaper!)
    (0, 1, 7.0),   # NYC → LA, $700
    (1, 2, 2.0),   # LA → SF, $200
]
print("Minimum edges:", minimum_edge_for_multi_edges(multi_edges))
# {(0, 1): 3.0, (1, 2): 2.0}

Always Handle Edge Cases

Implementation Considerations

How you represent graphs affects how naturally self-loops and multi-edges are handled:

Adjacency Matrix:

Self-loops: matrix[v][v] = true (or weight for weighted graphs)
Multi-edges: Can only store one edge per pair (or sum weights)
Good for: Simple graphs; bad for multigraphs

Adjacency List (Set-based):

Self-loops: Natural—just add v to its own adjacency set
Multi-edges: Sets don't allow duplicates; loses multi-edge information
Good for: Simple graphs with possible self-loops

Adjacency List (List-based):

Self-loops: Add v to its own list
Multi-edges: Lists allow duplicates; naturally supports multi-edges
Good for: Multigraphs and pseudographs

Edge List:

Self-loops: (v, v) stored like any other edge
Multi-edges: Naturally supports duplicates
Good for: All graph types; explicit edge enumeration

representation-comparison
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
from typing import List, Tuple, Dict, Set
from collections import defaultdict
 
class SimpleGraphMatrix:
    """Adjacency matrix - supports self-loops, NOT multi-edges."""
    
    def __init__(self, n: int):
        self.n = n
        self.matrix = [[False] * n for _ in range(n)]
    
    def add_edge(self, u: int, v: int):
        self.matrix[u][v] = True
        self.matrix[v][u] = True  # Undirected
    
    def add_self_loop(self, v: int):
        self.matrix[v][v] = True  # Works naturally
    
    def edge_count(self, u: int, v: int) -> int:
        # Can only return 0 or 1 - no multi-edge support
        return 1 if self.matrix[u][v] else 0
 
 
class MultiGraphAdjList:
    """Adjacency list (list-based) - supports self-loops AND multi-edges."""
    
    def __init__(self):
        self.adj: Dict[int, List[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
        if u != v:  # Don't double-add for self-loops
            self.adj[v].append(u)
    
    def edge_count(self, u: int, v: int) -> int:
        """Count edges between u and v (including multi-edges)."""
        if u == v:
            # Self-loops appear once in adjacency list
            return self.adj[u].count(v)
        else:
            # For undirected, count in one direction
            return self.adj[u].count(v)
    
    def neighbors(self, v: int) -> List[int]:
        return self.adj[v]  # May include v itself (self-loop)
 
 
class EdgeListGraph:
    """Edge list - most flexible, supports everything."""
    
    def __init__(self):
        self.edges: List[Tuple[int, int]] = []
        self.vertices: Set[int] = set()
    
    def add_edge(self, u: int, v: int):
        self.edges.append((u, v))
        self.vertices.add(u)
        self.vertices.add(v)
    
    def has_self_loop(self, v: int) -> bool:
        return any(u == v and w == v for u, w in self.edges)
    
    def count_multi_edges(self, u: int, v: int) -> int:
        """Count all edges between u and v (both directions for undirected)."""
        count = 0
        for a, b in self.edges:
            if (a == u and b == v) or (a == v and b == u):
                count += 1
        return count
 
 
# Demonstration
print("=== Simple Graph (Matrix) ===")
sg = SimpleGraphMatrix(3)
sg.add_edge(0, 1)
sg.add_edge(0, 1)  # Second edge ignored!
sg.add_self_loop(2)
print(f"Edge count 0-1: {sg.edge_count(0, 1)}")  # 1 (ignores multi)
print(f"Self-loop at 2: {sg.matrix[2][2]}")     # True
 
print("
=== Multigraph (List) ===")
mg = MultiGraphAdjList()
mg.add_edge(0, 1)
mg.add_edge(0, 1)  # Second edge stored!
mg.add_edge(0, 1)  # Third edge stored!
mg.add_edge(2, 2)  # Self-loop
print(f"Edge count 0-1: {mg.edge_count(0, 1)}")  # 3 (counts multi)
print(f"Neighbors of 0: {mg.neighbors(0)}")      # [1, 1, 1]
print(f"Neighbors of 2: {mg.neighbors(2)}")      # [2] (self-loop)

Choose Representation Wisely

When to Avoid vs. Embrace

Should you allow self-loops and multi-edges in your graph model? The answer depends on your problem:

Embrace Self-Loops When:

Modeling state machines where staying in a state is valid
Representing probabilities (Markov chains) with self-transitions
Working with reflexive relations (every element relates to itself)
Your domain genuinely has self-relationships

Avoid Self-Loops When:

They don't make semantic sense (e.g., "person is friend of themselves")
They complicate algorithms without adding value
Working with standard graph problems (MST, shortest path on simple graphs)

Embrace Multi-Edges When:

Different connections between same nodes have different properties
You need to count or enumerate individual connections
Modeling redundancy, parallel paths, or multiple relationship types

Avoid Multi-Edges When:

Only the existence (not quantity) of connections matters
Weights can aggregate the effect of multiple edges
Standard graph algorithms are sufficient

Use Self-Loops / Multi-Edges

•State machines with self-transitions
•Markov chains with stay probabilities
•Flight schedules with multiple daily flights
•Redundant network links
•Multi-relational knowledge graphs

Use Simple Graphs

•Social networks (friend/not friend)
•Basic dependency graphs
•Connectivity problems
•Standard shortest path queries
•Most interview/competitive programming

Default to Simple

Summary: Beyond Simple Graphs

We've explored the special cases that extend simple graphs. Let's consolidate:

Key Takeaways

•Self-loops connect a vertex to itself; they contribute 2 to degree (undirected) or 1 each to in/out-degree (directed).
•Multi-edges are multiple distinct edges between the same vertex pair; they're needed when individual connections have separate identities.
•Simple graphs have no self-loops or multi-edges; multigraphs allow multi-edges; pseudographs allow both.
•Self-loops are natural in state machines and Markov chains; multi-edges appear in transportation and multi-relational graphs.
•Algorithm implications: Self-loops are trivial cycles; multi-edges often mean taking the minimum weight for optimization problems.
•Implementation: Matrices and set-based lists don't naturally support multi-edges; list-based structures and edge lists do.
•Default to simple graphs unless your domain requires otherwise.

Module Complete:

Congratulations! You've completed the foundational vocabulary of graph theory. You now understand:

What vertices and edges are
The formal definition G = (V, E)
Adjacency, neighbors, and degree concepts
Self-loops and multi-edges as extensions

Module Complete