philiprehberger-graph
Directed and undirected graph data structure with traversal, shortest path, MST, max flow, coloring, and serialization
Requirements
- Ruby >= 3.1
Installation
Add to your Gemfile:
gem "philiprehberger-graph"
Or install directly:
gem install philiprehberger-graph
Usage
require "philiprehberger/graph"
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:a, :b, weight: 4)
g.add_edge(:a, :c, weight: 2)
g.add_edge(:c, :b, weight: 1)
g.shortest_path(:a, :b) # => [:a, :c, :b]
Traversal
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:a, :c)
g.add_edge(:b, :d)
g.bfs(:a) # => [:a, :b, :c, :d]
g.dfs(:a) # => [:a, :b, :d, :c]
Topological Sort
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:build, :test)
g.add_edge(:test, :deploy)
g.topological_sort # => [:build, :test, :deploy]
Cycle Detection
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:a, :b)
g.add_edge(:b, :a)
g.cycle? # => true
Connected Components
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:c, :d)
g.connected_components # => [[:a, :b], [:c, :d]]
Minimum Spanning Tree
g = Philiprehberger::Graph.new
g.add_edge(:a, :b, weight: 4)
g.add_edge(:a, :c, weight: 2)
g.add_edge(:b, :c, weight: 1)
g.add_edge(:b, :d, weight: 5)
g.minimum_spanning_tree(algorithm: :kruskal)
# => [{from: :b, to: :c, weight: 1}, {from: :a, to: :c, weight: 2}, {from: :b, to: :d, weight: 5}]
g.minimum_spanning_tree(algorithm: :prim)
Maximum Flow
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:s, :a, weight: 10)
g.add_edge(:s, :b, weight: 5)
g.add_edge(:a, :t, weight: 5)
g.add_edge(:b, :t, weight: 10)
g.add_edge(:a, :b, weight: 15)
g.max_flow(:s, :t) # => 15
Graph Coloring
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:b, :c)
g.add_edge(:c, :a)
g.coloring # => {:a=>0, :b=>1, :c=>2}
g.chromatic_number_estimate # => 3
Bipartiteness
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:b, :c)
g.bipartite? # => true
g.bipartite_sets # => [#<Set: {:a, :c}>, #<Set: {:b}>]
Strongly Connected Components
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:a, :b)
g.add_edge(:b, :a)
g.add_edge(:b, :c)
g.add_edge(:c, :d)
g.add_edge(:d, :c)
g.strongly_connected_components # => [[:d, :c], [:b, :a]]
Iteration
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:a, :c)
g.each_node { |id| puts id }
g.each_edge { |e| puts "#{e[:from]} -> #{e[:to]}" }
# Enumerator chaining
high_degree = g.each_node.select { |id| g.degree(id) > 1 }
heavy_edges = g.each_edge.select { |e| e[:weight] > 5 }
Shortest Path Distance
g = Philiprehberger::Graph.new
g.add_edge(:a, :b, weight: 1)
g.add_edge(:b, :c, weight: 2)
g.add_edge(:a, :c, weight: 10)
g.shortest_path_distance(:a, :c) # => 3
Graph Complement
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:b, :c)
c = g.complement
c.edge?(:a, :c) # => true
c.edge?(:a, :b) # => false
Query Methods
g = Philiprehberger::Graph.new
g.add_edge(:a, :b, weight: 3)
g.add_edge(:b, :c)
g.add_node(:d)
g.node?(:a) # => true
g.edge?(:a, :b) # => true
g.weight(:a, :b) # => 3
g.node_count # => 4
g.edge_count # => 2
g.empty? # => false
g.path?(:a, :c) # => true
g.path?(:a, :d) # => false
g.density # => 0.333...
Directed Degree
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:a, :b)
g.add_edge(:a, :c)
g.add_edge(:b, :c)
g.in_degree(:c) # => 2
g.out_degree(:a) # => 2
Subgraph
g = Philiprehberger::Graph.new
g.add_edge(:a, :b)
g.add_edge(:b, :c)
g.add_edge(:c, :d)
sg = g.subgraph([:a, :b, :c])
sg.nodes # => [:a, :b, :c]
sg.edge?(:a, :b) # => true
sg.node?(:d) # => false
Transpose
g = Philiprehberger::Graph.new(directed: true)
g.add_edge(:a, :b)
g.add_edge(:b, :c)
t = g.transpose
t.edge?(:b, :a) # => true
t.edge?(:c, :b) # => true
Serialization
g = Philiprehberger::Graph.new
g.add_edge(:a, :b, weight: 3)
g.to_dot
# => "graph G {\n a;\n b;\n a -- b [weight=3];\n}"
g.to_json
# => '{"directed":false,"nodes":["a","b"],"edges":[{"from":"a","to":"b","weight":3}]}'
g2 = Philiprehberger::Graph::Graph.from_json(g.to_json)
API
| Method | Description |
|---|---|
.new(directed:) |
Create a new graph |
#add_node(id) |
Add a node |
#add_edge(from, to, weight:) |
Add a weighted edge |
#remove_node(id) |
Remove a node and its edges |
#remove_edge(from, to) |
Remove an edge |
#node?(id) |
Check if a node exists |
#edge?(from, to) |
Check if an edge exists |
#weight(from, to) |
Get edge weight (nil if none) |
#neighbors(node) |
Get neighbor node ids |
#degree(node) |
Number of edges on a node |
#in_degree(node) |
Incoming edges (directed) |
#out_degree(node) |
Outgoing edges (directed) |
#nodes |
All node ids |
#edges |
All edges as hashes |
#node_count |
Number of nodes |
#edge_count |
Number of edges |
#empty? |
Whether the graph has no nodes |
#each_node |
Iterate nodes (yields or returns Enumerator) |
#each_edge |
Iterate edges (yields or returns Enumerator) |
#path?(from, to) |
Check if a path exists |
#bfs(start) |
Breadth-first search |
#dfs(start) |
Depth-first search |
#shortest_path(from, to) |
Dijkstra's shortest path |
#shortest_path_distance(from, to) |
Shortest distance (numeric) |
#topological_sort |
Topological ordering (DAG only) |
#cycle? |
Check for cycles |
#connected_components |
Find connected components |
#minimum_spanning_tree(algorithm:) |
Kruskal's or Prim's MST |
#max_flow(source, sink) |
Edmonds-Karp maximum flow |
#coloring |
Greedy graph coloring |
#chromatic_number_estimate |
Estimated chromatic number |
#bipartite? |
Check if graph is bipartite |
#bipartite_sets |
Get bipartite partition sets |
#strongly_connected_components |
Tarjan's SCC algorithm |
#subgraph(nodes) |
Extract a subgraph |
#transpose |
Reverse all edges (directed) |
#density |
Graph density (0.0 to 1.0) |
#complement |
Graph complement (missing edges) |
#to_dot |
Serialize to DOT format |
#to_json |
Serialize to JSON |
.from_json(str) |
Deserialize from JSON |
Development
bundle install
bundle exec rspec
bundle exec rubocop
Support
If you find this project useful: