# Class: RGL::PrimAlgorithm

Inherits:
Object
• Object
show all
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

• constructor

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

• 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```