class RGL::PrimAlgorithm

Implements {en.wikipedia.org/wiki/Prim%27s_algorithm Prim’s algorithm}. @see Graph#prim_minimum_spanning_tree

Constants

DISTANCE_COMBINATOR

Replacement for default distance combinator that is used in Dijkstra’s algorithm. While building a minimum spanning tree (MST) we’re interested not in the distance from the source (the vertex that is added first to the MST) to a vertex, but rather in the distance between already completed part of the MST (that includes all examined vertices) and the vertex. Therefore, when we examine an edge (u, v), where u is already in the MST and v is not, the distance from the MST to the vertex v is the weight of the edge (u, v).

Public Class Methods

new(graph, edge_weights_map, visitor) click to toggle source

Initializes Prim’s algorithm for a graph with provided edges weights map.

   # File lib/rgl/prim.rb
19 def initialize(graph, edge_weights_map, visitor)
20   @graph            = graph
21   @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?)
22   @visitor          = visitor
23   @dijkstra         = DijkstraAlgorithm.new(@graph, @edge_weights_map, @visitor, DISTANCE_COMBINATOR)
24 end

Public Instance Methods

minimum_spanning_tree(start_vertex = nil) click to toggle source

Returns minimum spanning tree for the graph. If the graph is disconnected, Prim’s algorithm will find the minimum spanning tree only for one of the connectivity components. If start_vertex is given, Dijkstra’s search will be started in this vertex and the algorithm will return the minimum spanning tree for the component it belongs to.

   # File lib/rgl/prim.rb
30 def minimum_spanning_tree(start_vertex = nil)
31   @dijkstra.find_shortest_paths(start_vertex || @graph.vertices.first)
32   AdjacencyGraph[*@visitor.parents_map.to_a.flatten]
33 end