PGX 21.1.1
Documentation

## Prim's Algorithm

##### Categoryclassic graph algorithmsAlgorithm IDpgx_builtin_a1_primTime ComplexityO(E + V log V) with V = number of vertices, E = number of edgesSpace RequirementO(2 * E + V) with V = number of vertices, E = number of edgesJavadocAnalyst#prim(PgxGraph graph, EdgeProperty weight) Analyst#prim(PgxGraph graph, EdgeProperty weight, EdgeProperty mst)

This implementation of Prim's algorithm works on undirected graphs that are connected and have no multi-edges (i.e. more than one edge connecting the same pair of vertices). The algorithm computes the minimum spanning tree (MST) of the graph using the weights associated to each edge. A minimum spanning tree is a subset of the edges that connects all the vertices in the graph such that it minimizes the total weight assiciated to the edges.

## Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the weight of each edge in the graph.
Output Argument Type Comment
in_mst edgeProp edge property holding the edges belonging to the minimum spanning tree of the graph (i.e. all the edges with in_mst=true).
Return Value Type Comment
double the total weight associated to the MST.

## Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class Prim {
public double mst(PgxGraph g, EdgeProperty<Double> weight, @Out EdgeProperty<Boolean> inMst) {
if (g.getNumVertices() == 0) {
return 0.0;
}

PgxMap<PgxEdge, Double> q = PgxMap.create();
PgxVertex root = g.getRandomVertex();

root.getNeighbors().filter(n -> n != root).forSequential(n -> {
PgxEdge e = n.edge();
q.set(e, weight.get(e));
});

VertexProperty<Boolean> processed = VertexProperty.create();
processed.setAll(false);
processed.set(root, true);
inMst.setAll(false);

int numNodes = 1;
double totalWeight = 0.0;

while (numNodes < g.getNumVertices() && q.size() > 0) {
PgxEdge newEdge = q.getKeyForMinValue();
PgxVertex u = newEdge.sourceVertex();
PgxVertex v = newEdge.destinationVertex();

if (processed.get(v)) {
PgxVertex tmp = v;
v = u;
u = tmp;
}

q.remove(newEdge);

if (processed.get(v) != processed.get(u)) {
inMst.set(newEdge, true);
processed.set(v, true);
totalWeight += weight.get(newEdge);

v.getNeighbors().forEach(n -> {
PgxEdge e = n.edge();
if (processed.get(n)) {
q.remove(e);
} else {
q.set(e, weight.get(e));
}
});
numNodes++;
}
}

}
}
```
```/*
*/
procedure mst(graph G, edgeProp<double> weight; edgeProp<bool> in_mst) : double {

if (G.numNodes() == 0) {
return 0.0;
}

map<edge, double> Q;
node root = G.pickRandom();

for (n: root.nbrs) (n != root) {
edge e = n.edge();
Q[e] = e.weight;
}

vertexProp<bool> processed;
G.processed = false;
root.processed = true;
G.in_mst = false;

int num_nodes = 1;
double total_weight = 0.0;

while (num_nodes < G.numNodes() && Q.size() > 0) {
edge new_edge = Q.getMinKey();
node u = new_edge.fromNode();
node v = new_edge.toNode();

if (v.processed) {
node tmp = v;
v = u;
u = tmp;
}

Q.remove(new_edge);

if (v.processed != u.processed) {
new_edge.in_mst = true;
v.processed = true;
total_weight += new_edge.weight;

foreach (n: v.nbrs) {
edge e = n.edge();
if (n.processed) {
Q.remove(e);
} else {
Q[e] = e.weight;
}
}
num_nodes++;
}
}