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
Source
# 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
Initializes Prim’s algorithm for a graph with provided edges weights map.
Public Instance Methods
Source
# 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
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.