Directed and Undirected Graphs

Overview

Graphs consist of vertices (nodes) connected by edges (links), forming a mathematical structure that models pairwise relationships between objects. The distinction between directed and undirected graphs determines whether edges have directionality. In directed graphs (digraphs), each edge has a specific source and destination vertex, representing asymmetric relationships. In undirected graphs, edges connect vertices bidirectionally, representing symmetric relationships.

Graphs appear throughout software development: social networks map connections between users, file systems represent directory hierarchies, compilers analyze code dependencies, routing algorithms find optimal paths through networks, and schedulers manage task execution order. The choice between directed and undirected graphs depends on whether relationships have inherent direction.

A directed graph G = (V, E) contains a set of vertices V and a set of ordered pairs E, where each edge (u, v) goes from vertex u to vertex v but not necessarily from v to u. An undirected graph treats each edge as an unordered pair, where (u, v) and (v, u) represent the same connection.

# Simple directed graph representation
directed = {
  'A' => ['B', 'C'],  # A points to B and C
  'B' => ['D'],        # B points to D
  'C' => ['D'],        # C points to D
  'D' => []            # D points to nothing
}

# Simple undirected graph representation
undirected = {
  'A' => ['B', 'C'],   # A connects to B and C
  'B' => ['A', 'D'],   # B connects to A and D
  'C' => ['A', 'D'],   # C connects to A and D
  'D' => ['B', 'C']    # D connects to B and C
}

Graph density describes the ratio of actual edges to possible edges. Dense graphs have many edges relative to vertices, while sparse graphs have few edges. This characteristic affects implementation choices, as different representations optimize for different density levels.

Weighted graphs assign values to edges, representing costs, distances, capacities, or other metrics. Unweighted graphs treat all edges equally. Many algorithms operate on both types, with unweighted graphs treated as weighted graphs where all edges have weight 1.

Key Principles

Graphs model relationships through two fundamental components: vertices represent entities, and edges represent connections between those entities. Each vertex typically contains data or an identifier, while edges may contain weights or labels describing the relationship strength or type.

Directed edges create asymmetric relationships where traversal follows a specific direction. In a web page link graph, an edge from page A to page B indicates A links to B, but B might not link back to A. In dependency graphs, an edge from module X to module Y means X depends on Y, establishing a one-way relationship that affects build order and module loading.

Undirected edges create symmetric relationships where traversal works in both directions. In a friendship network, if person A is friends with person B, then person B is friends with person A. In a road network where roads allow bidirectional travel, an edge between city X and city Y allows travel in either direction.

Graph connectivity describes whether paths exist between vertices. A connected undirected graph contains paths between all vertex pairs. A directed graph has two connectivity types: strongly connected graphs contain directed paths between all vertex pairs, while weakly connected graphs become connected when treating all edges as undirected.

# Checking connectivity in an undirected graph
def connected?(graph, start, target, visited = Set.new)
  return true if start == target
  return false if visited.include?(start)
  
  visited.add(start)
  
  graph[start].any? { |neighbor| connected?(graph, neighbor, target, visited) }
end

graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D'],
  'C' => ['A'],
  'D' => ['B']
}

connected?(graph, 'A', 'D')
# => true

Cycles occur when a path exists from a vertex back to itself. Directed acyclic graphs (DAGs) contain no cycles and support topological ordering, making them useful for dependency resolution, task scheduling, and version control histories. Undirected graphs containing cycles indicate alternative paths between vertices, affecting routing and redundancy strategies.

The degree of a vertex measures its connectivity. In undirected graphs, degree counts incident edges. In directed graphs, in-degree counts incoming edges while out-degree counts outgoing edges. Vertices with high degrees represent hubs or central nodes in the network structure.

Subgraphs form when selecting a subset of vertices and their connecting edges from a larger graph. Trees represent connected acyclic undirected graphs, forming a special subgraph class. Spanning trees include all vertices from the original graph while maintaining the tree property, with minimum spanning trees minimizing total edge weight.

Path properties define graph traversal characteristics. Path length measures the number of edges traversed. Shortest paths minimize edge count in unweighted graphs or total weight in weighted graphs. Multiple paths between vertices offer redundancy but increase complexity for algorithms that must consider all possibilities.

Implementation Approaches

Graph representation choices affect memory usage, operation performance, and implementation complexity. Three primary approaches trade off between space efficiency and operation speed: adjacency lists, adjacency matrices, and edge lists.

Adjacency lists store each vertex with a list of its neighbors. For vertex v, the adjacency list contains all vertices u where edge (v, u) exists. This representation works well for sparse graphs where the number of edges remains much smaller than the square of vertices. Adding edges requires appending to a list, while checking edge existence requires scanning the neighbor list.

For graph with edges: (A,B), (A,C), (B,D), (C,D)

Adjacency list representation:
A: [B, C]
B: [D]
C: [D]
D: []

Adjacency matrices use a two-dimensional array where entry [i][j] indicates whether an edge exists from vertex i to vertex j. For weighted graphs, the entry stores the edge weight, with a sentinel value representing no edge. This representation excels at dense graphs and provides constant-time edge existence checks but consumes quadratic space regardless of actual edge count.

For the same graph:

Adjacency matrix (1 = edge exists, 0 = no edge):
    A  B  C  D
A   0  1  1  0
B   0  0  0  1
C   0  0  0  1
D   0  0  0  0

Edge lists store graphs as collections of edge pairs, with each entry containing source and destination vertices plus optional weight. This representation minimizes space for very sparse graphs and simplifies iteration over all edges. However, checking whether a specific edge exists requires scanning the entire list, and finding a vertex's neighbors requires filtering all edges.

For undirected graphs, implementation approaches must handle bidirectionality. Adjacency lists typically store each edge twice, once in each vertex's neighbor list. Adjacency matrices ensure symmetry by setting both [i][j] and [j][i] when adding edges. Edge lists may store each undirected edge once or twice depending on whether algorithms need explicit bidirectional entries.

Directed graphs avoid the duplication requirement since edges have explicit direction. Adjacency lists store neighbors only for outgoing edges. Accessing incoming edges requires either maintaining a separate reverse adjacency list or scanning all vertices to find edges pointing to a target vertex.

Hybrid approaches combine representations for different operation patterns. Storing both forward and reverse adjacency lists doubles space usage but provides fast access to both outgoing and incoming edges. Some implementations maintain an adjacency list for the primary structure with a hash table for fast edge existence checks.

Ruby Implementation

Ruby implements graphs through custom classes built on native data structures. Hash objects serve as adjacency lists, arrays store neighbor collections, and Set objects eliminate duplicate edges while providing fast membership testing.

class DirectedGraph
  def initialize
    @adjacency_list = Hash.new { |hash, key| hash[key] = [] }
  end
  
  def add_vertex(vertex)
    @adjacency_list[vertex] ||= []
  end
  
  def add_edge(source, destination)
    @adjacency_list[source] << destination
  end
  
  def neighbors(vertex)
    @adjacency_list[vertex]
  end
  
  def vertices
    @adjacency_list.keys
  end
  
  def edges
    @adjacency_list.flat_map { |source, destinations|
      destinations.map { |dest| [source, dest] }
    }
  end
end

graph = DirectedGraph.new
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.neighbors('A')
# => ["B", "C"]

Undirected graphs require adding edges bidirectionally to maintain symmetry. Using Set objects for neighbor collections prevents duplicate edges when the same edge gets added from both directions.

require 'set'

class UndirectedGraph
  def initialize
    @adjacency_list = Hash.new { |hash, key| hash[key] = Set.new }
  end
  
  def add_vertex(vertex)
    @adjacency_list[vertex] ||= Set.new
  end
  
  def add_edge(vertex1, vertex2)
    @adjacency_list[vertex1].add(vertex2)
    @adjacency_list[vertex2].add(vertex1)
  end
  
  def remove_edge(vertex1, vertex2)
    @adjacency_list[vertex1].delete(vertex2)
    @adjacency_list[vertex2].delete(vertex1)
  end
  
  def neighbors(vertex)
    @adjacency_list[vertex].to_a
  end
  
  def degree(vertex)
    @adjacency_list[vertex].size
  end
end

graph = UndirectedGraph.new
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.degree('B')
# => 2

Weighted graphs extend basic implementations by storing neighbor information as hashes mapping destination vertices to weights rather than simple lists of neighbors.

class WeightedDirectedGraph
  def initialize
    @adjacency_list = Hash.new { |hash, key| hash[key] = {} }
  end
  
  def add_edge(source, destination, weight)
    @adjacency_list[source][destination] = weight
  end
  
  def weight(source, destination)
    @adjacency_list[source][destination]
  end
  
  def neighbors(vertex)
    @adjacency_list[vertex].keys
  end
  
  def neighbors_with_weights(vertex)
    @adjacency_list[vertex]
  end
end

graph = WeightedDirectedGraph.new
graph.add_edge('A', 'B', 5)
graph.add_edge('A', 'C', 3)
graph.neighbors_with_weights('A')
# => {"B"=>5, "C"=>3}

Matrix representations use nested arrays with numeric indices for vertices. This approach suits dense graphs and algorithms requiring frequent edge existence checks.

class GraphMatrix
  attr_reader :vertices
  
  def initialize(vertices)
    @vertices = vertices
    @vertex_indices = vertices.each_with_index.to_h
    @matrix = Array.new(vertices.size) { Array.new(vertices.size, 0) }
  end
  
  def add_edge(source, destination, weight = 1)
    source_idx = @vertex_indices[source]
    dest_idx = @vertex_indices[destination]
    @matrix[source_idx][dest_idx] = weight
  end
  
  def edge?(source, destination)
    source_idx = @vertex_indices[source]
    dest_idx = @vertex_indices[destination]
    @matrix[source_idx][dest_idx] != 0
  end
  
  def weight(source, destination)
    source_idx = @vertex_indices[source]
    dest_idx = @vertex_indices[destination]
    @matrix[source_idx][dest_idx]
  end
end

graph = GraphMatrix.new(['A', 'B', 'C'])
graph.add_edge('A', 'B', 5)
graph.edge?('A', 'B')
# => true

Traversal algorithms form the foundation for graph analysis. Depth-first search explores as far as possible along each branch before backtracking, while breadth-first search explores all neighbors before moving to the next level.

def depth_first_search(graph, start, visited = Set.new, &block)
  return if visited.include?(start)
  
  visited.add(start)
  yield start if block_given?
  
  graph.neighbors(start).each do |neighbor|
    depth_first_search(graph, neighbor, visited, &block)
  end
end

def breadth_first_search(graph, start)
  visited = Set.new([start])
  queue = [start]
  
  while !queue.empty?
    vertex = queue.shift
    yield vertex if block_given?
    
    graph.neighbors(vertex).each do |neighbor|
      unless visited.include?(neighbor)
        visited.add(neighbor)
        queue.push(neighbor)
      end
    end
  end
end

# Usage
graph = DirectedGraph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')

depth_first_search(graph, 'A') { |v| puts v }
# Prints: A, B, D, C (one possible order)

Practical Examples

Social networks model relationships between users as graphs. Directed graphs represent asymmetric relationships like following on platforms where users can follow others without reciprocation. Undirected graphs represent symmetric relationships like friendship where connections work both ways.

class SocialNetwork
  def initialize
    @followers = Hash.new { |h, k| h[k] = Set.new }
  end
  
  def follow(follower, followee)
    @followers[followee].add(follower)
  end
  
  def followers(user)
    @followers[user].to_a
  end
  
  def following(user)
    @followers.select { |followee, followers| 
      followers.include?(user) 
    }.keys
  end
  
  def mutual_followers(user1, user2)
    followers(user1) & followers(user2)
  end
  
  def friend_recommendations(user)
    # Find friends of friends who aren't already followed
    following(user).flat_map { |friend| 
      following(friend) 
    }.uniq - following(user) - [user]
  end
end

network = SocialNetwork.new
network.follow('Alice', 'Bob')
network.follow('Charlie', 'Bob')
network.follow('Alice', 'Charlie')
network.mutual_followers('Bob', 'Charlie')
# => ["Alice"]

Dependency resolution uses directed acyclic graphs to determine execution order for tasks with prerequisites. Topological sorting produces a valid ordering where all dependencies appear before dependent items.

class DependencyGraph
  def initialize
    @dependencies = Hash.new { |h, k| h[k] = Set.new }
    @dependents = Hash.new { |h, k| h[k] = Set.new }
  end
  
  def add_dependency(task, dependency)
    @dependencies[task].add(dependency)
    @dependents[dependency].add(task)
  end
  
  def topological_sort
    in_degree = Hash.new(0)
    @dependencies.each { |task, deps| in_degree[task] = deps.size }
    
    queue = @dependencies.keys.select { |task| in_degree[task] == 0 }
    result = []
    
    while !queue.empty?
      task = queue.shift
      result << task
      
      @dependents[task].each do |dependent|
        in_degree[dependent] -= 1
        queue << dependent if in_degree[dependent] == 0
      end
    end
    
    result.size == @dependencies.size ? result : nil
  end
end

deps = DependencyGraph.new
deps.add_dependency('deploy', 'test')
deps.add_dependency('test', 'build')
deps.add_dependency('build', 'compile')
deps.topological_sort
# => ["compile", "build", "test", "deploy"]

Navigation systems use weighted graphs where vertices represent locations and edges represent paths with distances or travel times. Shortest path algorithms find optimal routes between locations.

require 'set'

class NavigationGraph
  def initialize
    @edges = Hash.new { |h, k| h[k] = {} }
  end
  
  def add_road(location1, location2, distance)
    @edges[location1][location2] = distance
    @edges[location2][location1] = distance
  end
  
  def dijkstra(start, finish)
    distances = Hash.new(Float::INFINITY)
    distances[start] = 0
    previous = {}
    unvisited = Set.new(@edges.keys)
    
    while !unvisited.empty?
      current = unvisited.min_by { |vertex| distances[vertex] }
      break if current == finish || distances[current] == Float::INFINITY
      
      unvisited.delete(current)
      
      @edges[current].each do |neighbor, weight|
        next unless unvisited.include?(neighbor)
        
        alt_distance = distances[current] + weight
        if alt_distance < distances[neighbor]
          distances[neighbor] = alt_distance
          previous[neighbor] = current
        end
      end
    end
    
    path = []
    current = finish
    while current
      path.unshift(current)
      current = previous[current]
    end
    
    { distance: distances[finish], path: path }
  end
end

map = NavigationGraph.new
map.add_road('A', 'B', 5)
map.add_road('A', 'C', 2)
map.add_road('B', 'D', 1)
map.add_road('C', 'D', 6)
map.dijkstra('A', 'D')
# => {:distance=>6, :path=>["A", "B", "D"]}

State machines model system behavior as directed graphs where vertices represent states and edges represent transitions. Each edge may have conditions determining whether the transition fires.

class StateMachine
  def initialize(initial_state)
    @current_state = initial_state
    @transitions = Hash.new { |h, k| h[k] = {} }
  end
  
  def add_transition(from_state, to_state, event)
    @transitions[from_state][event] = to_state
  end
  
  def trigger(event)
    next_state = @transitions[@current_state][event]
    if next_state
      @current_state = next_state
      true
    else
      false
    end
  end
  
  def state
    @current_state
  end
end

order_flow = StateMachine.new(:pending)
order_flow.add_transition(:pending, :processing, :pay)
order_flow.add_transition(:processing, :shipped, :ship)
order_flow.add_transition(:shipped, :delivered, :deliver)
order_flow.trigger(:pay)
order_flow.state
# => :processing

Common Patterns

Graph traversal patterns determine the order for visiting vertices during exploration. Depth-first search follows edges as deeply as possible before backtracking, creating a path that explores one branch completely before moving to siblings. This pattern suits cycle detection, topological sorting, and path finding in mazes.

def find_path_dfs(graph, start, target, path = [], visited = Set.new)
  return nil if visited.include?(start)
  
  path = path + [start]
  return path if start == target
  
  visited.add(start)
  
  graph.neighbors(start).each do |neighbor|
    result = find_path_dfs(graph, neighbor, target, path, visited)
    return result if result
  end
  
  nil
end

Breadth-first search explores all vertices at distance k before visiting vertices at distance k+1, expanding outward in levels from the starting vertex. This pattern finds shortest paths in unweighted graphs and determines connectivity within a specific distance.

def shortest_path_bfs(graph, start, target)
  return [start] if start == target
  
  visited = Set.new([start])
  queue = [[start, [start]]]
  
  until queue.empty?
    vertex, path = queue.shift
    
    graph.neighbors(vertex).each do |neighbor|
      next if visited.include?(neighbor)
      
      new_path = path + [neighbor]
      return new_path if neighbor == target
      
      visited.add(neighbor)
      queue.push([neighbor, new_path])
    end
  end
  
  nil
end

Cycle detection identifies whether a graph contains loops. In directed graphs, tracking the current recursion stack during depth-first search detects back edges that close cycles. In undirected graphs, finding an edge to a visited vertex other than the parent indicates a cycle.

def has_cycle_directed?(graph)
  visited = Set.new
  rec_stack = Set.new
  
  detect_cycle = lambda do |vertex|
    visited.add(vertex)
    rec_stack.add(vertex)
    
    graph.neighbors(vertex).each do |neighbor|
      return true if rec_stack.include?(neighbor)
      return true if !visited.include?(neighbor) && detect_cycle.call(neighbor)
    end
    
    rec_stack.delete(vertex)
    false
  end
  
  graph.vertices.any? { |v| !visited.include?(v) && detect_cycle.call(v) }
end

def has_cycle_undirected?(graph)
  visited = Set.new
  
  detect_cycle = lambda do |vertex, parent|
    visited.add(vertex)
    
    graph.neighbors(vertex).each do |neighbor|
      next if neighbor == parent
      return true if visited.include?(neighbor)
      return true if detect_cycle.call(neighbor, vertex)
    end
    
    false
  end
  
  graph.vertices.any? { |v| !visited.include?(v) && detect_cycle.call(v, nil) }
end

Connected components identify groups of vertices where paths exist between any pair within the group but not between groups. Running depth-first or breadth-first search from unvisited vertices partitions the graph into components.

def connected_components(graph)
  visited = Set.new
  components = []
  
  graph.vertices.each do |vertex|
    next if visited.include?(vertex)
    
    component = []
    queue = [vertex]
    visited.add(vertex)
    
    until queue.empty?
      current = queue.shift
      component << current
      
      graph.neighbors(current).each do |neighbor|
        unless visited.include?(neighbor)
          visited.add(neighbor)
          queue.push(neighbor)
        end
      end
    end
    
    components << component
  end
  
  components
end

Minimum spanning trees connect all vertices in a weighted undirected graph while minimizing total edge weight. Prim's algorithm grows a single tree by repeatedly adding the minimum weight edge connecting a tree vertex to a non-tree vertex.

def prims_mst(graph)
  vertices = graph.vertices
  start = vertices.first
  in_tree = Set.new([start])
  edges = []
  
  while in_tree.size < vertices.size
    min_edge = nil
    min_weight = Float::INFINITY
    
    in_tree.each do |vertex|
      graph.neighbors_with_weights(vertex).each do |neighbor, weight|
        next if in_tree.include?(neighbor)
        
        if weight < min_weight
          min_weight = weight
          min_edge = [vertex, neighbor, weight]
        end
      end
    end
    
    break unless min_edge
    
    edges << min_edge
    in_tree.add(min_edge[1])
  end
  
  edges
end

Performance Considerations

Operation complexity varies significantly based on graph representation. Adjacency lists provide O(1) edge addition but O(degree) edge existence checks, where degree represents the number of neighbors for a vertex. Adjacency matrices offer O(1) edge checks but consume O(V²) space regardless of edge count, where V represents vertex count.

# Adjacency list performance
def adjacency_list_operations(vertices, edges)
  list = Hash.new { |h, k| h[k] = [] }
  
  # Edge addition: O(1)
  edges.each { |u, v| list[u] << v }
  
  # Edge check: O(degree of u)
  edge_exists = list['u'].include?('v')
  
  # Get neighbors: O(1) - returns reference
  neighbors = list['u']
  
  # Space: O(V + E)
end

# Adjacency matrix performance
def adjacency_matrix_operations(vertices)
  size = vertices.size
  matrix = Array.new(size) { Array.new(size, 0) }
  
  # Edge addition: O(1)
  matrix[0][1] = 1
  
  # Edge check: O(1)
  edge_exists = matrix[0][1] == 1
  
  # Get neighbors: O(V) - must scan row
  neighbors = []
  matrix[0].each_with_index { |val, i| neighbors << i if val == 1 }
  
  # Space: O(V²)
end

Graph traversal algorithms have distinct complexity profiles. Depth-first search visits each vertex once and explores each edge once, resulting in O(V + E) time complexity. Breadth-first search exhibits identical asymptotic complexity but maintains a queue that grows up to O(V) in space.

Shortest path algorithms scale differently based on graph properties. Dijkstra's algorithm requires O((V + E) log V) time using a binary heap priority queue. Graphs with negative edge weights need Bellman-Ford at O(VE) time. Dense graphs where E approaches V² make Floyd-Warshall's O(V³) all-pairs approach competitive.

Sparse graphs benefit from adjacency list representations where E remains much smaller than V². Social networks typically exhibit sparsity since users connect to a tiny fraction of total users. Web graphs also show sparsity as pages link to relatively few other pages compared to total page count.

Dense graphs approach E ≈ V² edges, making matrix representations more efficient despite quadratic space cost. Complete graphs where every vertex connects to every other vertex, and some proximity graphs in geometric problems, exhibit density that favors matrices.

require 'benchmark'

def benchmark_representations(vertex_count, edge_density)
  vertices = (0...vertex_count).to_a
  edge_count = (vertex_count * (vertex_count - 1) * edge_density / 2).to_i
  
  # Generate random edges
  edges = edge_count.times.map {
    [rand(vertex_count), rand(vertex_count)]
  }.uniq
  
  # Adjacency list
  list_time = Benchmark.measure {
    list = Hash.new { |h, k| h[k] = [] }
    edges.each { |u, v| list[u] << v }
    1000.times { list[rand(vertex_count)].include?(rand(vertex_count)) }
  }
  
  # Adjacency matrix
  matrix_time = Benchmark.measure {
    matrix = Array.new(vertex_count) { Array.new(vertex_count, 0) }
    edges.each { |u, v| matrix[u][v] = 1 }
    1000.times { matrix[rand(vertex_count)][rand(vertex_count)] == 1 }
  }
  
  { list: list_time.real, matrix: matrix_time.real }
end

# Sparse graph (10% density)
benchmark_representations(100, 0.1)
# List faster for edge checks due to small neighbor lists

# Dense graph (90% density)
benchmark_representations(100, 0.9)
# Matrix faster for edge checks despite larger space

Cache performance affects graph algorithm efficiency in practice despite identical big-O complexity. Adjacency lists with random access patterns cause more cache misses than matrix representations with sequential access patterns. However, memory consumption often dominates since matrices exceed cache size for large graphs.

Parallel graph algorithms partition vertices across processors to exploit multiple cores. Degree distribution affects load balancing since high-degree vertices require more work than low-degree vertices. Dynamic work stealing mitigates imbalance by redistributing work from busy processors to idle ones.

Reference

Graph Terminology

Representation Comparison

Common Algorithms

Implementation Patterns

Traversal Patterns

Edge Classification (DFS)

Graph Properties