Class: Philiprehberger::Graph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/philiprehberger/graph/graph.rb

Overview

A directed or undirected graph with adjacency list storage.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(directed: false) ⇒ Graph

Returns a new instance of Graph.

Parameters:

  • directed (Boolean) (defaults to: false) —

    whether the graph is directed



8
9
10
11
 
# File 'lib/philiprehberger/graph/graph.rb', line 8

def initialize(directed: false)
  @directed = directed
  @adjacency = {}
end

Class Method Details

.from_json(json_str) ⇒ Graph

Deserialize a graph from JSON.

Parameters:

  • json_str (String) —

    JSON string

Returns:

  • (Graph) —

    a new graph instance



633
634
635
636
637
638
639
640
641
642
643
644
 
# File 'lib/philiprehberger/graph/graph.rb', line 633

def self.from_json(json_str)
  require 'json'
  data = JSON.parse(json_str, symbolize_names: true)
  graph = new(directed: data[:directed])
  (data[:nodes] || []).each { |n| graph.add_node(n.is_a?(String) ? n.to_sym : n) }
  (data[:edges] || []).each do |e|
    from = e[:from].is_a?(String) ? e[:from].to_sym : e[:from]
    to = e[:to].is_a?(String) ? e[:to].to_sym : e[:to]
    graph.add_edge(from, to, weight: e[:weight] || 1)
  end
  graph
end

Instance Method Details

#add_edge(from, to, weight: 1) ⇒ self

Add an edge between two nodes.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

  • weight (Numeric) (defaults to: 1) —

    edge weight

Returns:

  • (self) 


55
56
57
58
59
60
61
 
# File 'lib/philiprehberger/graph/graph.rb', line 55

def add_edge(from, to, weight: 1)
  add_node(from)
  add_node(to)
  @adjacency[from] << { node: to, weight: weight }
  @adjacency[to] << { node: from, weight: weight } unless @directed
  self
end

#add_node(id) ⇒ self

Add a node to the graph.

Parameters:

  • id (Object) —

    the node identifier

Returns:

  • (self) 


44
45
46
47
 
# File 'lib/philiprehberger/graph/graph.rb', line 44

def add_node(id)
  @adjacency[id] ||= []
  self
end

#bfs(start) ⇒ Array<Object>

Breadth-first search starting from a node.

Parameters:

  • start (Object) —

    the starting node

Returns:

  • (Array<Object>) —

    nodes in BFS order



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
 
# File 'lib/philiprehberger/graph/graph.rb', line 220

def bfs(start)
  return [] unless @adjacency.key?(start)

  visited = { start => true }
  queue = [start]
  result = []

  until queue.empty?
    node = queue.shift
    result << node
    neighbors(node).each do |neighbor|
      unless visited[neighbor]
        visited[neighbor] = true
        queue << neighbor
      end
    end
  end

  result
end

#bipartite? ⇒ Boolean

Check whether the graph is bipartite.

Returns:

  • (Boolean) 


536
537
538
 
# File 'lib/philiprehberger/graph/graph.rb', line 536

def bipartite?
  !bipartite_sets.nil?
end

#bipartite_sets ⇒ Array<Set, Set>?

Find bipartite partition sets using BFS 2-coloring.

Returns:

  • (Array<Set, Set>, nil) —

    two sets of nodes, or nil if not bipartite



543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
 
# File 'lib/philiprehberger/graph/graph.rb', line 543

def bipartite_sets
  color = {}
  set_a = Set.new
  set_b = Set.new

  @adjacency.each_key do |start|
    next if color.key?(start)

    color[start] = 0
    set_a << start
    queue = [start]

    until queue.empty?
      node = queue.shift
      all_neighbors = bipartite_neighbors(node)
      all_neighbors.each do |neighbor|
        if color.key?(neighbor)
          return nil if color[neighbor] == color[node]
        else
          color[neighbor] = 1 - color[node]
          if color[neighbor].zero?
            set_a << neighbor
          else
            set_b << neighbor
          end
          queue << neighbor
        end
      end
    end
  end

  [set_a, set_b]
end

#chromatic_number_estimate ⇒ Integer

Estimate the chromatic number using greedy coloring.

Returns:

  • (Integer) —

    estimated chromatic number



526
527
528
529
530
531
 
# File 'lib/philiprehberger/graph/graph.rb', line 526

def chromatic_number_estimate
  return 0 if @adjacency.empty?

  colors = coloring
  (colors.values.max || 0) + 1
end

#coloring ⇒ Hash

Greedy graph coloring. Assigns the smallest available color (integer) to each node.

Returns:

  • (Hash) —

    mapping of node => color (integer starting from 0)



509
510
511
512
513
514
515
516
517
518
519
520
521
 
# File 'lib/philiprehberger/graph/graph.rb', line 509

def coloring
  result = {}
  @adjacency.each_key do |node|
    used_colors = Set.new
    neighbors(node).each do |neighbor|
      used_colors << result[neighbor] if result.key?(neighbor)
    end
    color = 0
    color += 1 while used_colors.include?(color)
    result[node] = color
  end
  result
end

#complement ⇒ Graph

Return the complement graph. The complement contains edges between all pairs of nodes that are NOT connected in the original graph.

Returns:

  • (Graph) —

    a new graph with complementary edges



434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
 
# File 'lib/philiprehberger/graph/graph.rb', line 434

def complement
  g = self.class.new(directed: @directed)
  @adjacency.each_key { |id| g.add_node(id) }

  node_list = @adjacency.keys
  node_list.each_with_index do |a, i|
    targets = @directed ? node_list : node_list[(i + 1)..]
    targets.each do |b|
      next if a == b
      next if edge?(a, b)

      g.add_edge(a, b)
    end
  end

  g
end

#connected_components ⇒ Array<Array<Object>>

Find connected components (undirected) or weakly connected components (directed).

Returns:

  • (Array<Array<Object>>) —

    arrays of node ids per component



455
456
457
458
459
460
461
462
463
464
465
466
467
468
 
# File 'lib/philiprehberger/graph/graph.rb', line 455

def connected_components
  visited = {}
  components = []

  @adjacency.each_key do |node|
    next if visited[node]

    component = []
    cc_visit(node, visited, component)
    components << component
  end

  components
end

#cycle? ⇒ Boolean

Check if the graph contains a cycle.

Returns:

  • (Boolean) 


339
340
341
342
343
344
345
 
# File 'lib/philiprehberger/graph/graph.rb', line 339

def cycle?
  if @directed
    directed_cycle?
  else
    undirected_cycle?
  end
end

#degree(node) ⇒ Integer

Return the degree of a node (number of edges).

Parameters:

  • node (Object) —

    the node

Returns:

  • (Integer) 


98
99
100
 
# File 'lib/philiprehberger/graph/graph.rb', line 98

def degree(node)
  (@adjacency[node] || []).length
end

#density ⇒ Float

Calculate the density of the graph. Density is the ratio of actual edges to possible edges.

Returns:

  • (Float) —

    density between 0.0 and 1.0



420
421
422
423
424
425
426
427
 
# File 'lib/philiprehberger/graph/graph.rb', line 420

def density
  n = @adjacency.length
  return 0.0 if n < 2

  m = edge_count.to_f
  max_edges = @directed ? n * (n - 1) : n * (n - 1) / 2.0
  m / max_edges
end

#dfs(start) ⇒ Array<Object>

Depth-first search starting from a node.

Parameters:

  • start (Object) —

    the starting node

Returns:

  • (Array<Object>) —

    nodes in DFS order



245
246
247
248
249
250
251
252
 
# File 'lib/philiprehberger/graph/graph.rb', line 245

def dfs(start)
  return [] unless @adjacency.key?(start)

  visited = {}
  result = []
  dfs_visit(start, visited, result)
  result
end

#directed? ⇒ Boolean

Whether the graph is directed.

Returns:

  • (Boolean) 


16
17
18
 
# File 'lib/philiprehberger/graph/graph.rb', line 16

def directed?
  @directed
end

#each_edge {|Hash| ... } ⇒ Enumerator

Iterate over all edges as to:, weight: hashes.

Yields:

  • (Hash) —

    each edge

Returns:

  • (Enumerator) —

    if no block given



34
35
36
37
38
 
# File 'lib/philiprehberger/graph/graph.rb', line 34

def each_edge(&)
  return enum_for(:each_edge) unless block_given?

  edges.each(&)
end

#each_node {|Object| ... } ⇒ Enumerator

Iterate over all node ids.

Yields:

  • (Object) —

    each node id

Returns:

  • (Enumerator) —

    if no block given



24
25
26
27
28
 
# File 'lib/philiprehberger/graph/graph.rb', line 24

def each_node(&)
  return enum_for(:each_node) unless block_given?

  @adjacency.each_key(&)
end

#edge?(from, to) ⇒ Boolean

Check if an edge exists between two nodes.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (Boolean) 


141
142
143
144
145
 
# File 'lib/philiprehberger/graph/graph.rb', line 141

def edge?(from, to)
  return false unless @adjacency.key?(from)

  @adjacency[from].any? { |e| e[:node] == to }
end

#edge_count ⇒ Integer

Return the number of edges.

Returns:

  • (Integer) 


176
177
178
 
# File 'lib/philiprehberger/graph/graph.rb', line 176

def edge_count
  edges.length
end

#edges ⇒ Array<Hash>

Return all edges as [from, to, weight] tuples.

Returns:

  • (Array<Hash>) 


201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
# File 'lib/philiprehberger/graph/graph.rb', line 201

def edges
  result = []
  seen = {}
  @adjacency.each do |from, edges_list|
    edges_list.each do |edge|
      key = @directed ? [from, edge[:node]] : [from, edge[:node]].sort
      unless seen[key]
        result << { from: from, to: edge[:node], weight: edge[:weight] }
        seen[key] = true
      end
    end
  end
  result
end

#empty? ⇒ Boolean

Whether the graph has no nodes.

Returns:

  • (Boolean) 


194
195
196
 
# File 'lib/philiprehberger/graph/graph.rb', line 194

def empty?
  @adjacency.empty?
end

#in_degree(node) ⇒ Integer

Return the in-degree of a node (directed graphs). For undirected graphs, returns the same as degree.

Parameters:

  • node (Object) —

    the node

Returns:

  • (Integer) 


107
108
109
110
111
112
113
114
115
 
# File 'lib/philiprehberger/graph/graph.rb', line 107

def in_degree(node)
  return degree(node) unless @directed

  count = 0
  @adjacency.each_value do |edges_list|
    edges_list.each { |e| count += 1 if e[:node] == node }
  end
  count
end

#max_flow(source, sink) ⇒ Numeric

Compute the maximum flow from source to sink using Edmonds-Karp (BFS-based Ford-Fulkerson). Only works on directed graphs.

Parameters:

  • source (Object) —

    source node

  • sink (Object) —

    sink node

Returns:

  • (Numeric) —

    the maximum flow value

Raises:

  • (Error) —

    if the graph is not directed or nodes don’t exist



497
498
499
500
501
502
503
504
 
# File 'lib/philiprehberger/graph/graph.rb', line 497

def max_flow(source, sink)
  raise Error, 'max_flow requires a directed graph' unless @directed
  raise Error, 'source node not found' unless @adjacency.key?(source)
  raise Error, 'sink node not found' unless @adjacency.key?(sink)
  return 0 if source == sink

  edmonds_karp(source, sink)
end

#minimum_spanning_tree(algorithm: :kruskal) ⇒ Array<Hash>

Find the minimum spanning tree using Kruskal’s or Prim’s algorithm. Only works on undirected graphs.

Parameters:

  • algorithm (Symbol) (defaults to: :kruskal) —

    :kruskal or :prim

Returns:

  • (Array<Hash>) —

    edges in the MST as to:, weight: hashes

Raises:

  • (Error) —

    if the graph is directed or disconnected



476
477
478
479
480
481
482
483
484
485
486
487
488
 
# File 'lib/philiprehberger/graph/graph.rb', line 476

def minimum_spanning_tree(algorithm: :kruskal)
  raise Error, 'minimum spanning tree requires an undirected graph' if @directed
  raise Error, 'graph is empty' if @adjacency.empty?

  components = connected_components
  raise Error, 'graph is disconnected' if components.length > 1

  case algorithm
  when :kruskal then kruskal_mst
  when :prim then prim_mst
  else raise Error, "unknown algorithm: #{algorithm}"
  end
end

#neighbors(node) ⇒ Array<Object>

Return neighbor node ids for a given node.

Parameters:

  • node (Object) —

    the node

Returns:

  • (Array<Object>) —

    neighbor ids



90
91
92
 
# File 'lib/philiprehberger/graph/graph.rb', line 90

def neighbors(node)
  (@adjacency[node] || []).map { |e| e[:node] }
end

#node?(id) ⇒ Boolean

Check if a node exists.

Parameters:

  • id (Object) —

    the node identifier

Returns:

  • (Boolean) 


132
133
134
 
# File 'lib/philiprehberger/graph/graph.rb', line 132

def node?(id)
  @adjacency.key?(id)
end

#node_count ⇒ Integer

Return the number of nodes.

Returns:

  • (Integer) 


169
170
171
 
# File 'lib/philiprehberger/graph/graph.rb', line 169

def node_count
  @adjacency.length
end

#nodes ⇒ Array<Object>

Return all node ids.

Returns:

  • (Array<Object>) 


162
163
164
 
# File 'lib/philiprehberger/graph/graph.rb', line 162

def nodes
  @adjacency.keys
end

#out_degree(node) ⇒ Integer

Return the out-degree of a node (directed graphs). For undirected graphs, returns the same as degree.

Parameters:

  • node (Object) —

    the node

Returns:

  • (Integer) 


122
123
124
125
126
 
# File 'lib/philiprehberger/graph/graph.rb', line 122

def out_degree(node)
  return degree(node) unless @directed

  (@adjacency[node] || []).length
end

#path?(from, to) ⇒ Boolean

Check if a path exists between two nodes using BFS.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (Boolean) 


352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
 
# File 'lib/philiprehberger/graph/graph.rb', line 352

def path?(from, to)
  return false unless @adjacency.key?(from) && @adjacency.key?(to)
  return true if from == to

  visited = { from => true }
  queue = [from]

  until queue.empty?
    node = queue.shift
    neighbors(node).each do |neighbor|
      return true if neighbor == to

      unless visited[neighbor]
        visited[neighbor] = true
        queue << neighbor
      end
    end
  end

  false
end

#remove_edge(from, to) ⇒ self

Remove an edge between two nodes.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (self) 


80
81
82
83
84
 
# File 'lib/philiprehberger/graph/graph.rb', line 80

def remove_edge(from, to)
  @adjacency[from]&.reject! { |e| e[:node] == to }
  @adjacency[to]&.reject! { |e| e[:node] == from } unless @directed
  self
end

#remove_node(id) ⇒ self

Remove a node and all its edges.

Parameters:

  • id (Object) —

    the node to remove

Returns:

  • (self) 


67
68
69
70
71
72
73
 
# File 'lib/philiprehberger/graph/graph.rb', line 67

def remove_node(id)
  @adjacency.delete(id)
  @adjacency.each_value do |edges|
    edges.reject! { |e| e[:node] == id }
  end
  self
end

#shortest_path(from, to) ⇒ Array<Object>?

Find the shortest path between two nodes using Dijkstra’s algorithm.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (Array<Object>, nil) —

    the path as an array of nodes, or nil if no path exists



259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
 
# File 'lib/philiprehberger/graph/graph.rb', line 259

def shortest_path(from, to)
  return nil unless @adjacency.key?(from) && @adjacency.key?(to)
  return [from] if from == to

  distances = Hash.new(Float::INFINITY)
  distances[from] = 0
  previous = {}
  unvisited = @adjacency.keys.dup

  until unvisited.empty?
    current = unvisited.min_by { |n| distances[n] }
    break if distances[current] == Float::INFINITY

    unvisited.delete(current)

    return build_path(previous, from, to) if current == to

    (@adjacency[current] || []).each do |edge|
      alt = distances[current] + edge[:weight]
      if alt < distances[edge[:node]]
        distances[edge[:node]] = alt
        previous[edge[:node]] = current
      end
    end
  end

  nil
end

#shortest_path_distance(from, to) ⇒ Numeric?

Find the shortest distance between two nodes using Dijkstra’s algorithm.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (Numeric, nil) —

    the shortest distance, or nil if no path exists



293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
# File 'lib/philiprehberger/graph/graph.rb', line 293

def shortest_path_distance(from, to)
  return nil unless @adjacency.key?(from) && @adjacency.key?(to)
  return 0 if from == to

  distances = Hash.new(Float::INFINITY)
  distances[from] = 0
  unvisited = @adjacency.keys.dup

  until unvisited.empty?
    current = unvisited.min_by { |n| distances[n] }
    break if distances[current] == Float::INFINITY

    unvisited.delete(current)

    return distances[to] if current == to

    (@adjacency[current] || []).each do |edge|
      alt = distances[current] + edge[:weight]
      distances[edge[:node]] = alt if alt < distances[edge[:node]]
    end
  end

  nil
end

#strongly_connected_components ⇒ Array<Array<Object>>

Find strongly connected components using Tarjan’s algorithm. Only works on directed graphs.

Returns:

  • (Array<Array<Object>>) —

    arrays of node ids per SCC

Raises:

  • (Error) —

    if the graph is not directed



582
583
584
585
586
 
# File 'lib/philiprehberger/graph/graph.rb', line 582

def strongly_connected_components
  raise Error, 'strongly_connected_components requires a directed graph' unless @directed

  tarjan_scc
end

#subgraph(node_ids) ⇒ Graph

Extract a subgraph containing only the specified nodes and edges between them.

Parameters:

  • node_ids (Array<Object>) —

    the nodes to include

Returns:

  • (Graph) —

    a new graph



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
 
# File 'lib/philiprehberger/graph/graph.rb', line 378

def subgraph(node_ids)
  node_set = node_ids.is_a?(Set) ? node_ids : Set.new(node_ids)
  g = self.class.new(directed: @directed)

  node_set.each { |id| g.add_node(id) if @adjacency.key?(id) }

  @adjacency.each do |from, edges_list|
    next unless node_set.include?(from)

    edges_list.each do |edge|
      next unless node_set.include?(edge[:node])
      next if !@directed && from.to_s > edge[:node].to_s

      g.add_edge(from, edge[:node], weight: edge[:weight])
    end
  end

  g
end

#to_dot ⇒ String

Serialize the graph to DOT format.

Returns:

  • (String) —

    DOT format string



591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
 
# File 'lib/philiprehberger/graph/graph.rb', line 591

def to_dot
  type = @directed ? 'digraph' : 'graph'
  connector = @directed ? '->' : '--'
  lines = ["#{type} G {"]

  @adjacency.each_key do |node|
    lines << "  #{dot_escape(node)};"
  end

  seen = {}
  @adjacency.each do |from, edges_list|
    edges_list.each do |edge|
      key = @directed ? [from, edge[:node]] : [from, edge[:node]].sort
      next if seen[key]

      seen[key] = true
      attrs = edge[:weight] == 1 ? '' : " [weight=#{edge[:weight]}]"
      lines << "  #{dot_escape(from)} #{connector} #{dot_escape(edge[:node])}#{attrs};"
    end
  end

  lines << '}'
  lines.join("\n")
end

#to_json(*_args) ⇒ String

Serialize the graph to JSON.

Returns:

  • (String) —

    JSON string



619
620
621
622
623
624
625
626
627
 
# File 'lib/philiprehberger/graph/graph.rb', line 619

def to_json(*_args)
  require 'json'
  data = {
    directed: @directed,
    nodes: @adjacency.keys,
    edges: edges.map { |e| { from: e[:from], to: e[:to], weight: e[:weight] } }
  }
  JSON.generate(data)
end

#topological_sort ⇒ Array<Object>

Topological sort (directed acyclic graphs only).

Returns:

  • (Array<Object>) —

    nodes in topological order

Raises:

  • (Error) —

    if the graph contains a cycle or is not directed



322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/philiprehberger/graph/graph.rb', line 322

def topological_sort
  raise Error, 'topological sort requires a directed graph' unless @directed
  raise Error, 'graph contains a cycle' if cycle?

  visited = {}
  result = []

  @adjacency.each_key do |node|
    topo_visit(node, visited, result) unless visited[node]
  end

  result.reverse
end

#total_weight ⇒ Numeric

Sum of weights across all edges. Returns 0 for an empty or edgeless graph.

For undirected graphs each edge is counted once.

Returns:

  • (Numeric) 


185
186
187
188
189
 
# File 'lib/philiprehberger/graph/graph.rb', line 185

def total_weight
  total = 0
  each_edge { |edge| total += edge[:weight] }
  total
end

#transpose ⇒ Graph

Return a new graph with all edges reversed. Only works on directed graphs.

Returns:

  • (Graph) —

    a new graph with reversed edges

Raises:

  • (Error) —

    if the graph is not directed



403
404
405
406
407
408
409
410
411
412
413
414
 
# File 'lib/philiprehberger/graph/graph.rb', line 403

def transpose
  raise Error, 'transpose requires a directed graph' unless @directed

  g = self.class.new(directed: true)
  @adjacency.each_key { |id| g.add_node(id) }
  @adjacency.each do |from, edges_list|
    edges_list.each do |edge|
      g.add_edge(edge[:node], from, weight: edge[:weight])
    end
  end
  g
end

#weight(from, to) ⇒ Numeric?

Get the weight of an edge.

Parameters:

  • from (Object) —

    source node

  • to (Object) —

    destination node

Returns:

  • (Numeric, nil) —

    the edge weight, or nil if no edge exists



152
153
154
155
156
157
 
# File 'lib/philiprehberger/graph/graph.rb', line 152

def weight(from, to)
  return nil unless @adjacency.key?(from)

  edge = @adjacency[from].find { |e| e[:node] == to }
  edge&.dig(:weight)
end