scripts/builtin/shortestPath.dml

#-------------------------------------------------------------
#
# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.
#
#-------------------------------------------------------------
#
# Computes the minimum distances (shortest-path) between a single 
# source vertex and every other vertex in the graph.
# 
# Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bilk, 
# James C. Dehnert, Ikkan Horn, Naty Leiser and Grzegorz Czajkowski:
# Pregel: A System for Large-Scale Graph Processing
#
#------------------------------------------------------------------------------
# NAME       TYPE      MEANING
# G          MATRIX    adjacency matrix of the labeled graph: Such graph can be directed 
#                      (G is symmetric) or undirected (G is not symmetric).
#                      The values of G can be 0/1 (just specifying whether the nodes
#                      are connected or not) or integer values (representing the weight
#                      of the edges or the distances between nodes, 0 if not connected).
#
# maxi       Integer   Integer max number of iterations accepted (0 for FALSE, i.e. 
#                      max number of iterations not defined)
#
# sourceNode Integer   node index to calculate the shortest paths to all other nodes.
#
# verbose    Boolean   flag for verbose debug output
#------------------------------------------------------------------------------
# C          Matrix    Output matrix (double) of minimum distances (shortest-path) between 
#                      vertices: The value of the ith row and the jth column of the output
#                      matrix is the minimum distance shortest-path from vertex i to vertex j.
#                      When the value of the minimum distance is infinity, the two nodes are 
#                      not connected.
#------------------------------------------------------------------------------

m_shortestPath = function(Matrix[Double] G, Integer maxi = 0, Integer sourceNode, Boolean verbose = FALSE) 
  return (Matrix[Double] C) 
{
  if(verbose) {
    print("SHORTEST PATH CALCULATION");
  }

  if(min(G) < 0){
    stop("All values in G must be positive")
  }

  if(ncol(G) != nrow(G)){
    stop("Not correct matrix dimensions")
  }

  matrixSize = nrow(G)

  G = replace(target=G, pattern=0, replacement=Inf)

  # initialize the matrix of minimum distances with "infinity" values:
  minDistVector = matrix(Inf,rows=matrixSize,cols=1)

  # update minimum distance from the sourceNode to itself to 0:
  minDistVector[sourceNode,1] = 0

  iter = 1
  diff = Inf;
  while( diff > 0 & (maxi==0 | iter<=maxi) ) {
    w = t(colMins(G + minDistVector))
    u = min(w, minDistVector);
    diff = sum(u != minDistVector)
    minDistVector = u; # update assignment
    if( verbose ){
      print("Shortest Path: iter = "+iter+", #diff = "+diff);
    }
    iter = iter + 1;
  }

  C=minDistVector
  if(verbose) {
    print("SHORTEST PATH CALCULATION FINISHED, CHECK OUTPUT MATRIX OF MINIMUM DISTANCES:");
    print(toString(C))
  }
}