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.
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. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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++; } } return totalWeight; } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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++; } } return total_weight; }