components.daph

#-------------------------------------------------------------
#
# 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.
#
# Modifications Copyright 2022 The DAPHNE Consortium
#
#-------------------------------------------------------------

# Computes the connected components of a graph and returns a
# vector indicating the assignment of vertices to components,
# where each component is identified by the maximum vertex ID
# (i.e., row/column position of the input graph) 

maxi = 0; # unlimited
verbose = true;

# read sparse graph 
# G = readMatrix($G);
n = $n;
e = $e;
UT = upperTri(rand(n, n, 1.0, 1.0, 2.0*e/n^2.0, -1), false, false);
G = UT + t(UT);

# best effort check for symmetry (not exact but fast)
if( sum(sum(G,0) != t(sum(G,1))) > 0.0 ) {
    print("Connected Components: input graph needs to be "
        + "symmetric but rowSums and colSums don't match up.");
}

# initialize state with vertex ids
c = seq(1.0, nrow(G), 1.0);
diff = as.f64(nrow(G));
iter = 1;

# iterative computation of connected components
while( as.si64(diff > 0.0) && (maxi==0 || iter<=maxi) ) {
    u = max(aggMax(G * t(c), 0), c);
    diff = sum(u != c);
    c = u; # update assignment
    if( verbose ) {
        print("Connected components: iter = ",0,0); print(iter+", #diff = "+diff);
    }
    iter = iter + 1;
}

# write vertex assignment
writeMatrix(c, $C);