class RGL::PrimAlgorithm
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
Initializes Prim's algorithm for a graph with provided edges weights map.
# File lib/rgl/prim.rb 17 def initialize(graph, edge_weights_map, visitor) 18 @graph = graph 19 @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?) 20 @visitor = visitor 21 @dijkstra = DijkstraAlgorithm.new(@graph, @edge_weights_map, @visitor, DISTANCE_COMBINATOR) 22 end
Public Instance Methods
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 28 def minimum_spanning_tree(start_vertex = nil) 29 @dijkstra.find_shortest_paths(start_vertex || @graph.vertices.first) 30 AdjacencyGraph[*@visitor.parents_map.to_a.flatten] 31 end