weighted_graph is a simple Ruby library for working on graphs with weighted edges.
# Add directed edge (source, destination) to the graph with given weight
add_edge(source, destination, weight)
# Add undirected edge (vertex_a, vertex_b) to the graph with given weight
add_undirected_edge(vertex_a, vertex_b, weight)
# Remove directed edge (source, destination) from the graph
remove_edge(source, destination)
# Remove undirected edge (vertex_a, vertex_b) from the graph
remove_undirected_edge(vertex_a, vertex_b)
# Return true iff the graph contains directed edge (source, destination)
contains_edge?(source, destination)
# Returns the weight of directed edge (source, destination),
# or returns Float::INFINITY if no such edge exists
get_edge_weight(source, destination)
# Returns the set of vertices v_i where edge (source, v_i) is in the graph
get_adjacent_vertices(source)
# Returns a list of nodes of the graph
nodes()WeightedGraph::PositiveWeightedGraph extends WeightedGraph::Graph and shares its behaviour, with the following differences:
# Add directed edge (source, destination) to the graph with given weight
# Requires that weight is a positive number
add_edge(source, destination, weight)
# Add undirected edge (vertex_a, vertex_b) to the graph with given weight
# Requires that weight is a positive number
add_undirected_edge(vertex_a, vertex_b, weight)Add this line to your application's Gemfile:
gem 'weighted_graph'require 'weighted_graph'
graph = WeightedGraph::Graph.new
graph.add_undirected_edge('Burnaby', 'Vancouver', 10)
graph.add_edge('Burnaby', 'Port Coquitlam', 23)
graph.add_edge('Vancouver', 'Langley', 37)
graph.add_undirected_edge('Langley', 'Port Coquitlam', 35)
adj_cities_to_van = graph.get_adjacent_vertices('Vancouver')
# => #<Set: { 'Burnaby', 'Langley' }>
graph.contains_edge?('Vancouver', 'Port Coquitlam')
# => false
graph.get_edge_weight('Vancouver', 'Port Coquitlam')
# => Infinity
graph.get_edge_weight('Vancouver', 'Burnaby')
# => 10After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.
Bug reports and pull requests are welcome on GitHub at https://github.com/msayson/weighted_graph.
The weighted_graph library is open source and available under the terms of the MIT License.