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



622
623
624
625
626
627
628
629
630
631
632
633
 
# File 'lib/philiprehberger/graph/graph.rb', line 622

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



209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/philiprehberger/graph/graph.rb', line 209

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) 


525
526
527
 
# File 'lib/philiprehberger/graph/graph.rb', line 525

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



532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
 
# File 'lib/philiprehberger/graph/graph.rb', line 532

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



515
516
517
518
519
520
 
# File 'lib/philiprehberger/graph/graph.rb', line 515

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)



498
499
500
501
502
503
504
505
506
507
508
509
510
 
# File 'lib/philiprehberger/graph/graph.rb', line 498

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



423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
 
# File 'lib/philiprehberger/graph/graph.rb', line 423

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



444
445
446
447
448
449
450
451
452
453
454
455
456
457
 
# File 'lib/philiprehberger/graph/graph.rb', line 444

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) 


328
329
330
331
332
333
334
 
# File 'lib/philiprehberger/graph/graph.rb', line 328

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



409
410
411
412
413
414
415
416
 
# File 'lib/philiprehberger/graph/graph.rb', line 409

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



234
235
236
237
238
239
240
241
 
# File 'lib/philiprehberger/graph/graph.rb', line 234

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>) 


190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/philiprehberger/graph/graph.rb', line 190

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) 


183
184
185
 
# File 'lib/philiprehberger/graph/graph.rb', line 183

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



486
487
488
489
490
491
492
493
 
# File 'lib/philiprehberger/graph/graph.rb', line 486

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



465
466
467
468
469
470
471
472
473
474
475
476
477
 
# File 'lib/philiprehberger/graph/graph.rb', line 465

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) 


341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
 
# File 'lib/philiprehberger/graph/graph.rb', line 341

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



248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/philiprehberger/graph/graph.rb', line 248

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



282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
 
# File 'lib/philiprehberger/graph/graph.rb', line 282

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



571
572
573
574
575
 
# File 'lib/philiprehberger/graph/graph.rb', line 571

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



367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
 
# File 'lib/philiprehberger/graph/graph.rb', line 367

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



580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
 
# File 'lib/philiprehberger/graph/graph.rb', line 580

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



608
609
610
611
612
613
614
615
616
 
# File 'lib/philiprehberger/graph/graph.rb', line 608

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



311
312
313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/philiprehberger/graph/graph.rb', line 311

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

#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



392
393
394
395
396
397
398
399
400
401
402
403
 
# File 'lib/philiprehberger/graph/graph.rb', line 392

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