Class: RGL::PrimAlgorithm
 Inherits:

Object
 Object
 RGL::PrimAlgorithm
 Defined in:
 lib/rgl/prim.rb
Overview
Implements Prim’s algorithm.
Constant Summary collapse
 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).
lambda { _, edge_weight edge_weight }
Instance Method Summary collapse

#initialize(graph, edge_weights_map, visitor) ⇒ PrimAlgorithm
constructor
Initializes Prim’s algorithm for a graph with provided edges weights map.

#minimum_spanning_tree(start_vertex = nil) ⇒ Object
Returns minimum spanning tree for the graph.
Constructor Details
#initialize(graph, edge_weights_map, visitor) ⇒ PrimAlgorithm
Initializes Prim’s algorithm for a graph with provided edges weights map.
19 20 21 22 23 24 
# File 'lib/rgl/prim.rb', line 19 def initialize(graph, edge_weights_map, visitor) @graph = graph @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?) @visitor = visitor @dijkstra = DijkstraAlgorithm.new(@graph, @edge_weights_map, @visitor, DISTANCE_COMBINATOR) end 
Instance Method Details
#minimum_spanning_tree(start_vertex = nil) ⇒ Object
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.
30 31 32 33 
# File 'lib/rgl/prim.rb', line 30 def minimum_spanning_tree(start_vertex = nil) @dijkstra.find_shortest_paths(start_vertex  @graph.vertices.first) AdjacencyGraph[*@visitor.parents_map.to_a.flatten] end 