shub-niggurath/kruskal.c

#include <igraph.h>
#include <time.h>
#include "io.h"
#include "kruskal.h"

void shuffle_edges(igraph_t *g, igraph_vector_t *eids) {
    long int ecount = igraph_ecount(g);
    igraph_vector_t pairs;
    igraph_vector_init(&pairs, 2*ecount);
    int e;
    for (e = 0; e < ecount; ++e) {
        VECTOR(pairs)[2*e] = IGRAPH_FROM(g, e);
        VECTOR(pairs)[2*e+1] = IGRAPH_TO(g, e);
    }
    igraph_vector_init(eids, ecount);
    igraph_get_eids(g, eids, &pairs, 0, 0, 1);
    igraph_vector_destroy(&pairs);
    igraph_vector_shuffle(eids);
}

void build_tree(igraph_t *dest_tree, igraph_t *src_graph, igraph_vector_t *src_eids) {
    // Transfer edges from the complete graph to the tree whenever this preserves acyclicity.
    // Cycles can be detected by seeing whether two vertices already have a path between them.
    igraph_integer_t edge, from, to;
    igraph_matrix_t paths;
    igraph_matrix_init(&paths, 1, 1);
    long int tree_size = igraph_vcount(src_graph) - 1;
    while((long int)igraph_ecount(dest_tree) < tree_size && (long int)igraph_vector_size(src_eids) > 0) {
        edge = igraph_vector_pop_back(src_eids);
        igraph_edge(src_graph, edge, &from, &to);
        MATRIX(paths, 0, 0) = IGRAPH_INFINITY;
        igraph_shortest_paths(dest_tree, &paths, igraph_vss_1(from), igraph_vss_1(to), IGRAPH_ALL);
        if(MATRIX(paths, 0, 0) == IGRAPH_INFINITY) {
            igraph_add_edge(dest_tree, from, to);
        }
    }
    igraph_matrix_destroy(&paths);
}