Class: RGL::PrimAlgorithm

Inherits:
Object
  • Object
show all
Defined in:
lib/rgl/prim.rb

Overview

Implements Prim’s algorithm.

See Also:

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

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