/* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */

/*

 *  (C) 2018 by Argonne National Laboratory.

 *      See COPYRIGHT in top-level directory.

 *

 */

#include "mpiimpl.h"

#ifdef HAVE_NETLOC

#include "netloc_util.h"

#include "mpl.h"

#define MAX_DISTANCE 65535

typedef struct semicube_edge {

    netloc_node_t **src;

    netloc_node_t **dest;

} semicube_edge;

typedef struct tree {

    netloc_node_t ***vertices;

    int num_nodes;

    semicube_edge **edges;

    int num_edges;

} tree;

#undef FUNCNAME

#define FUNCNAME get_tree_attributes

#undef FCNAME

#define FCNAME MPL_QUOTE(FUNCNAME)

static int get_tree_attributes(netloc_topology_t topology,

                               MPIR_Netloc_network_attributes * network_attr)

{

    int i, j, k, l;

    netloc_node_t **traversal_order = NULL;

    int traversal_start, traversal_end;

    int visited_count;

    int mpi_errno = MPI_SUCCESS;

    int max_depth = 0;

    netloc_dt_lookup_table_t *host_nodes = NULL, *nodes = NULL;

    struct netloc_dt_lookup_table_iterator *hti = NULL, *ti = NULL;

    int start_index = 0, end_index = 0;

    int count_at_level_mismatch = 0;

    int bandwidth_mismatch = 0;

    int out_degree_mismatch = 0;

    int prev_width = 0;

    int edges_go_across_levels = 0;

    int out_degree_mismatch_at_level = 0;

    MPIR_CHKPMEM_DECL(3);

    network_attr->type = MPIR_NETLOC_NETWORK_TYPE__INVALID;

    host_nodes =

        (netloc_dt_lookup_table_t *) MPL_malloc(sizeof(netloc_dt_lookup_table_t), MPL_MEM_OTHER);

    mpi_errno = netloc_get_all_host_nodes(topology, host_nodes);

    if (!mpi_errno) {

        int host_node_at_leaf_level;

        /* Traversal order never exceeds the total number of nodes */

        MPIR_CHKPMEM_MALLOC(traversal_order, netloc_node_t **,

                            sizeof(netloc_node_t *) * topology->num_nodes, mpi_errno,

                            "traversal_order", MPL_MEM_OTHER);

        hti = netloc_dt_lookup_table_iterator_t_construct(*host_nodes);

        host_node_at_leaf_level = 1;

        while (!netloc_lookup_table_iterator_at_end(hti)) {

            netloc_node_t *node = (netloc_node_t *) netloc_lookup_table_iterator_next_entry(hti);

            int num_edges;

            netloc_edge_t **edges;

            if (node == NULL) {

                break;

            }

            netloc_get_all_edges(topology, node, &num_edges, &edges);

            for (i = 0; i < num_edges; i++) {

                /* Check that outgoing edge connects to switches only */

                if (edges[i]->dest_node->node_type != NETLOC_NODE_TYPE_SWITCH) {

                    host_node_at_leaf_level = 0;

                    break;

                }

            }

            if (!host_node_at_leaf_level)

                break;

            MPIR_Assert(end_index < topology->num_nodes);

            traversal_order[end_index++] = node;

        }

        if (!host_node_at_leaf_level) {

            network_attr->type = MPIR_NETLOC_NETWORK_TYPE__INVALID;

            goto fn_exit;

        }

        nodes =

            (netloc_dt_lookup_table_t *) MPL_malloc(sizeof(netloc_dt_lookup_table_t),

                                                    MPL_MEM_OTHER);

        mpi_errno = netloc_get_all_nodes(topology, nodes);

        if (!mpi_errno) {

            /* Traverse the graph in topological order */

            while (start_index < end_index) {

                netloc_node_t *node = traversal_order[start_index++];

                /* Add all neighbors to traversal list */

                netloc_edge_t **edges;

                int num_edges;

                netloc_get_all_edges(topology, node, &num_edges, &edges);

                for (j = 0; j < num_edges; j++) {

                    netloc_node_t *neighbor = edges[j]->dest_node;

                    int parents_visited = 1;

                    ti = netloc_dt_lookup_table_iterator_t_construct(*nodes);

                    while (!netloc_lookup_table_iterator_at_end(ti)) {

                        int num_parents_covered = 0, num_parents = 0;

                        netloc_node_t *parent_node =

                            (netloc_node_t *) netloc_lookup_table_iterator_next_entry(ti);

                        netloc_edge_t **neighbor_edges;

                        int neighbor_num_edges;

                        if (parent_node == NULL) {

                            break;

                        }

                        netloc_get_all_edges(topology, parent_node, &neighbor_num_edges,

                                             &neighbor_edges);

                        for (k = 0; k < neighbor_num_edges; k++) {

                            if (neighbor_edges[k]->dest_node != neighbor) {

                                continue;

                            }

                            num_parents++;

                            for (l = 0; l < start_index; l++) {

                                if (traversal_order[l] == parent_node) {

                                    num_parents_covered++;

                                    break;

                                }

                            }

                        }

                        if (num_parents != num_parents_covered) {

                            parents_visited = 0;

                            break;

                        }

                    }

                    if (parents_visited) {

                        int added_previously = 0;

                        for (k = 0; k < end_index; k++) {

                            if (traversal_order[k] == neighbor) {

                                added_previously = 1;

                                break;

                            }

                        }

                        if (!added_previously) {

                            MPIR_Assert(end_index < topology->num_nodes);

                            traversal_order[end_index++] = neighbor;

                        }

                    }

                }

            }

            if (end_index < topology->num_nodes) {

                /* Cycle in the graph, not a tree or close network */

                network_attr->type = MPIR_NETLOC_NETWORK_TYPE__INVALID;

                goto fn_exit;

            }

            /* Assign depths to nodes of the graph bottom up, in breadth first order */

            /* Indexed by node id, visited_node_list[i] > -1 indicates that the

             * node i has been visited */

            MPIR_CHKPMEM_MALLOC(network_attr->u.tree.node_levels, int *,

                                sizeof(int) * topology->num_nodes, mpi_errno,

                                "network_attr->u.tree.node_levels", MPL_MEM_OTHER);

            for (i = 0; i < topology->num_nodes; i++) {

                network_attr->u.tree.node_levels[i] = -1;

            }

            traversal_end = 0;

            traversal_start = 0;

            visited_count = 0;

            /* Initialize host depths to zero */

            for (i = 0; i < topology->num_nodes; i++) {

                if (topology->nodes[i]->node_type == NETLOC_NODE_TYPE_HOST) {

                    int num_edges;

                    netloc_edge_t **edges;

                    /* Mark the host node as visited */

                    network_attr->u.tree.node_levels[topology->nodes[i]->__uid__] = 0;

                    visited_count++;

                    /* Copy all parents without duplicates to the traversal list */

                    netloc_get_all_edges(topology, topology->nodes[i], &num_edges, &edges);

                    for (j = 0; j < num_edges; j++) {

                        if (network_attr->u.tree.node_levels[edges[j]->dest_node->__uid__] < 0) {

                            traversal_order[traversal_end++] = edges[j]->dest_node;

                            /* Switch levels start from 1 */

                            network_attr->u.tree.node_levels[edges[j]->dest_node->__uid__] = 1;

                            max_depth = 1;

                            visited_count++;

                        }

                    }

                }

            }

            while (visited_count < topology->num_nodes) {

                netloc_node_t *traversed_node = traversal_order[traversal_start++];

                int num_edges;

                netloc_edge_t **edges;

                int depth = network_attr->u.tree.node_levels[traversed_node->__uid__];

                /* Find all nodes not visited with an edge from the current node */

                netloc_get_all_edges(topology, traversed_node, &num_edges, &edges);

                for (j = 0; j < num_edges; j++) {

                    if (edges[j]->dest_node == traversed_node) {

                        continue;

                    }

                    if (network_attr->u.tree.node_levels[edges[j]->dest_node->__uid__] < 0 ||

                        (depth + 1) <

                        network_attr->u.tree.node_levels[edges[j]->dest_node->__uid__]) {

                        traversal_order[traversal_end++] = edges[j]->dest_node;

                        network_attr->u.tree.node_levels[edges[j]->dest_node->__uid__] = depth + 1;

                        if (max_depth < depth + 1) {

                            max_depth = depth + 1;

                        }

                        visited_count++;

                    }

                }

            }

            /* End of depth assignment */

            /* Count the number of nodes and bandwidth at each level */

            for (i = 0; i < max_depth; i++) {

                int width_at_level = 0;

                int num_nodes_at_level = 0;

                int out_degree_at_level = -1;

                for (j = 0; j < topology->num_nodes; j++) {

                    if (network_attr->u.tree.node_levels[topology->nodes[j]->__uid__] == i) {

                        int num_edges;

                        netloc_edge_t **edges;

                        num_nodes_at_level++;

                        int edge_width = 0;

                        int node_out_degree = 0;

                        netloc_get_all_edges(topology, topology->nodes[j], &num_edges, &edges);

                        for (k = 0; k < num_edges; k++) {

                            if (edges[k]->src_node == topology->nodes[j]) {

                                edge_width += edges[k]->bandwidth;

                            }

                            if (edges[k]->src_node == topology->nodes[j] &&

                                network_attr->u.tree.node_levels[edges[k]->dest_node->__uid__] ==

                                i - 1) {

                                node_out_degree++;

                            }

                            if (edges[k]->src_node == topology->nodes[j] &&

                                (network_attr->u.tree.node_levels[edges[k]->dest_node->__uid__] !=

                                 i + 1) &&

                                (network_attr->u.tree.node_levels[edges[k]->dest_node->__uid__] !=

                                 i - 1)) {

                                edges_go_across_levels = 1;

                                break;

                            }

                        }

                        if (i > 0) {

                            if (out_degree_at_level == -1) {

                                out_degree_at_level = node_out_degree;

                            } else if (out_degree_at_level != node_out_degree) {

                                out_degree_mismatch_at_level = i;

                                break;

                            }

                        }

                        if (edges_go_across_levels) {

                            break;

                        }

                        if ((i == max_depth && node_out_degree != 0) ||

                            (i > 0 && node_out_degree != 2)) {

                            out_degree_mismatch = 1;

                        }

                        if (width_at_level == 0) {

                            width_at_level = edge_width;

                        } else if (width_at_level != edge_width) {

                            bandwidth_mismatch = 1;

                        }

                    }

                }

                if (out_degree_mismatch_at_level || edges_go_across_levels) {

                    break;

                }

                if (num_nodes_at_level != ((unsigned) 1 << (max_depth - i))) {

                    count_at_level_mismatch = 1;

                }

                if (i > 0 && width_at_level != 2 * prev_width) {

                    bandwidth_mismatch = 1;

                }

            }

            if (!out_degree_mismatch_at_level && !edges_go_across_levels) {

                network_attr->type = MPIR_NETLOC_NETWORK_TYPE__CLOS_NETWORK;

                if (!count_at_level_mismatch && !bandwidth_mismatch && !out_degree_mismatch) {

                    network_attr->type = MPIR_NETLOC_NETWORK_TYPE__FAT_TREE;

                }

                errno = MPIR_Netloc_get_network_end_point(MPIR_Process.network_attr,

                                                          MPIR_Process.netloc_topology,

                                                          MPIR_Process.hwloc_topology,

                                                          &MPIR_Process.

                                                          network_attr.network_endpoint);

                if (errno != MPI_SUCCESS) {

                    network_attr->type = MPIR_NETLOC_NETWORK_TYPE__INVALID;

                }

            } else {

                network_attr->type = MPIR_NETLOC_NETWORK_TYPE__INVALID;

            }

        }

    }

  fn_exit:

    MPIR_CHKPMEM_COMMIT();

    MPIR_CHKPMEM_REAP();

    if (host_nodes != NULL) {

        MPL_free(host_nodes);

    }

    if (nodes != NULL) {

        MPL_free(nodes);

    }

    return mpi_errno;

  fn_fail:

    goto fn_exit;

}

static unsigned int get_hamming_distance(const unsigned long long src_label,

                                         const unsigned long long dest_label)

{

    unsigned int distance = 0;

    unsigned long long hamming_distance;

    hamming_distance = (unsigned long long) src_label ^ dest_label;

    while (hamming_distance) {

        if (hamming_distance & 1) {

            distance++;

        }

        hamming_distance = hamming_distance >> 1;

    }

  fn_exit:

    return distance;

  fn_fail:

    goto fn_exit;

}

static int get_distance(netloc_node_t ** exposed_vertex, netloc_node_t ** root, tree * subtree)

{

    int distance = 0;

    int i;

    if (exposed_vertex == root) {

        return distance;

    }

    for (i = 0; i < subtree->num_edges; i++) {

        int temp_distance = 0;

        if (subtree->edges[0]->dest == exposed_vertex) {

            temp_distance = get_distance(subtree->edges[0]->src, root, subtree);

            if (temp_distance + 1 > distance) {

                distance = temp_distance + 1;

            }

        }

    }

  fn_exit:

    return distance;

  fn_fail:

    goto fn_exit;

}

static void get_path(netloc_node_t ** src, netloc_node_t ** dest, tree ** forest, int tree_count,

                     semicube_edge *** path, int *path_length)

{

    int i, j;

    for (i = 0; i < tree_count; i++) {

        tree *subtree = forest[i];

        int subtree_edge_count = subtree->num_edges;

        for (j = 0; j < subtree_edge_count; j++) {

            int path_size = -1;

            if (subtree->edges[j]->dest == dest) {

                semicube_edge edge;

                edge.src = src;

                edge.dest = dest;

                *path[*path_length] = &edg;;

                *path_length = *path_length + 1;

            } else if (subtree->edges[j]->src == src) {

                int destination_reached = 0;

                int current_path_length = *path_length;

                get_path(subtree->edges[j]->dest, dest, forest, tree_count, path, path_length);

                if (path_length >= 0) {

                    semicube_edge *edge = (*path)[path_size - 1];

                    if (edge->dest == dest) {

                        destination_reached = 1;

                        break;

                    }

                }

                if (!destination_reached) {

                    *path_length = current_path_length;

                }

            }

        }

    }

  fn_exit:

    return;

  fn_fail:

    goto fn_exit;

}

static void get_root_of_tree(tree * subtree, netloc_node_t *** root)

{

    int i, j;

    for (i = 0; i < subtree->num_nodes; i++) {

        netloc_node_t **vertex = subtree->vertices[i];

        int rootnode = 1;

        for (j = 0; j < subtree->num_edges; j++) {

            if (subtree->edges[j]->dest == vertex) {

                rootnode = 0;

                break;

            }

        }

        if (rootnode) {

            *root = vertex;

            break;

        }

    }

  fn_exit:

    return;

  fn_fail:

    goto fn_exit;

}

static void get_blossom(netloc_node_t *** nodes, int num_nodes,

                        semicube_edge ** edges, int num_edges, netloc_node_t *** unmarked_vertices,

                        int num_unmarked, netloc_node_t **** blossom_nodes, int *num_blossom_nodes,

                        int *stem_index)

{

    int i, j;

    netloc_node_t **exposed_vertex;

    for (j = 0; j < num_unmarked; j++) {

        if (nodes[i] == unmarked_vertices[j]) {

            netloc_node_t ***traversed_nodes =

                (netloc_node_t ***) MPL_calloc(num_nodes, sizeof(netloc_node_t **), MPL_MEM_OTHER);

            int cycle_index = 0;

            int odd_cycle_found = 0;

            exposed_vertex = nodes[i];

            traversed_nodes[cycle_index++] = exposed_vertex;

            /* Find an odd cycle starting from the exposed vertex */

            while (1) {

                /* Find an edge adjacent to the current node */

                for (i = 0; i < num_edges; i++) {

                    if (edges[i]->src == exposed_vertex) {

                        traversed_nodes[cycle_index++] = edges[i]->dest;

                        exposed_vertex = edges[i]->dest;

                        break;

                    }

                }

                for (i = 0; i < cycle_index - 1; i++) {

                    if (traversed_nodes[i] == exposed_vertex && (cycle_index - 1 - i) & 1) {

                        odd_cycle_found = 1;

                        *num_blossom_nodes = cycle_index;

                        *blossom_nodes = traversed_nodes;

                        *stem_index = i;

                        break;

                    }

                }

                if (odd_cycle_found) {

                    break;

                }

            }

            if (odd_cycle_found) {

                break;

            }

        }

    }

  fn_exit:

    return;

  fn_fail:

    goto fn_exit;

}

static void find_augmenting_path(netloc_topology_t topology, netloc_node_t *** nodes, int num_nodes,

                                 semicube_edge ** edges, int num_edges,

                                 semicube_edge *** augmenting_path, int *augmenting_path_length,

                                 semicube_edge ** maximum_matching, int num_matching_edges)

{

    semicube_edge **current_augmenting_path = NULL;

    int path_length;

    int i, j, k, l;

    int unmarked_vertex_insert, unmarked_edge_insert = 0;

    netloc_node_t ***unmarked_vertices = NULL;

    semicube_edge **unmarked_edges = NULL;

    tree **forest;

    int forest_insert_index;

    /* Unmark all vertices and edges in the semicube graph, mark all edges of the matching */

    unmarked_vertex_insert = 0;

    unmarked_vertices =

        (netloc_node_t ***) MPL_calloc(num_nodes, sizeof(netloc_node_t **), MPL_MEM_OTHER);

    for (i = 0; i < num_nodes; i++) {

        netloc_node_t **semicube_vertex = nodes[i];

        int exposed_vertex = 1;

        for (j = 0; j < num_matching_edges; j++) {

            semicube_edge *edge = maximum_matching[j];

            if (edge->src == semicube_vertex || edge->dest == semicube_vertex) {

                exposed_vertex = 0;

                break;

            }

        }

        if (exposed_vertex) {

            unmarked_vertices[unmarked_vertex_insert++] = semicube_vertex;

        }

    }

    unmarked_edge_insert = 0;

    unmarked_edges =

        (semicube_edge **) MPL_calloc(num_edges, sizeof(semicube_edge *), MPL_MEM_OTHER);

    /* Unmark all vertices and edges in the semicube graph, mark all edges of the matching */

    for (i = 0; i < num_edges; i++) {

        int marked_edge = 0;

        semicube_edge *edge = edges[i];

        for (j = 0; j < num_matching_edges; j++) {

            semicube_edge *local_edge = maximum_matching[j];

            if (local_edge->src == edge->src && local_edge->dest == edge->dest) {

                marked_edge = 1;

                break;

            }

        }

        if (!marked_edge) {

            unmarked_edges[unmarked_edge_insert++] = edge;

        }

    }

    forest = (tree **) MPL_calloc(unmarked_vertex_insert, sizeof(tree *), MPL_MEM_OTHER);

    forest_insert_index = 0;

    /* Create a forest with each exposed vertex as a singleton set */

    for (i = 0; i < unmarked_vertex_insert; i++) {

        tree *singleton_tree = (tree *) MPL_malloc(sizeof(tree), MPL_MEM_OTHER);

        singleton_tree->vertices =

            (netloc_node_t ***) MPL_malloc(sizeof(netloc_node_t **), MPL_MEM_OTHER);

        singleton_tree->edges =

            (semicube_edge **) MPL_malloc(sizeof(semicube_edge *), MPL_MEM_OTHER);

        singleton_tree->vertices[0] = unmarked_vertices[i];

        singleton_tree->num_nodes = 1;

        singleton_tree->num_edges = 0;

        forest[forest_insert_index++] = singleton_tree;

    }

    while (1) {

        int exposed_vertex = 0;

        netloc_node_t **vertex;

        netloc_node_t **root;

        int distance_from_root;

        int unmarked_vertex_index = -1;

        int unmarked_edge_index = -1;

        tree *subtree;

        exposed_vertex = 0;

        for (i = 0; i < forest_insert_index; i++) {

            subtree = forest[i];

            /* Check if the marked vertex is at an even distance from the

             * root node in its tree */

            for (j = 0; j < subtree->num_nodes; j++) {

                vertex = subtree->vertices[j];

                for (l = 0; l < unmarked_vertex_insert; l++) {

                    if (unmarked_vertices[l] == vertex) {

                        exposed_vertex = 1;

                        unmarked_vertex_index = l;

                        break;

                    }

                }

                if (exposed_vertex) {

                    break;

                }

            }

            if (exposed_vertex) {

                break;

            }

        }

        if (!exposed_vertex) {

            break;

        }

        get_root_of_tree(subtree, &root);

        distance_from_root = get_distance(vertex, root, subtree);

        if (!(distance_from_root & 1)) {

            /* Find an unmarked edge from exposed_vertex */

            int unmarked_edge = 0;

            semicube_edge *edge;

            netloc_node_t **dest;

            for (j = 0; j < unmarked_edge_insert; j++) {

                if (unmarked_edges[j]->src == vertex || unmarked_edges[j]->dest == vertex) {

                    unmarked_edge = 1;

                    unmarked_edge_index = j;

                    edge = unmarked_edges[j];

                    dest = unmarked_edges[j]->dest;

                    break;

                }

            }

            if (unmarked_edge) {

                /* Check if the destination is not in the forest */

                int dest_in_forest = 0;

                tree *dest_subtree;

                netloc_node_t **dest_root;

                for (j = 0; j < forest_insert_index; j++) {

                    tree *tempsubtree = forest[j];

                    for (k = 0; k < tempsubtree->num_nodes; k++) {

                        if (tempsubtree->vertices[k] == dest) {

                            dest_in_forest = 1;

                            dest_subtree = tempsubtree;

                            break;

                        }

                    }

                    if (dest_in_forest) {

                        break;

                    }

                }

                get_root_of_tree(dest_subtree, &dest_root);

                if (!dest_in_forest) {

                    int vertex_insert_position;

                    int edge_insert_position = 0;

                    /* The destination node is in matching graph */

                    semicube_edge *matching_edge = NULL;

                    for (j = 0; j < num_matching_edges; j++) {

                        semicube_edge *temp_matching_edge = maximum_matching[j];

                        if (temp_matching_edge->src == dest || temp_matching_edge->dest == dest) {

                            matching_edge = temp_matching_edge;

                            break;

                        }

                    }

                    MPIR_Assert(matching_edge != NULL);

                    /* Add edge to subtree */

                    vertex_insert_position = subtree->num_nodes + 1;

                    subtree->vertices =

                        (netloc_node_t ***) MPL_realloc(subtree->vertices,

                                                        (vertex_insert_position + 1) *

                                                        sizeof(netloc_node_t **), MPL_MEM_OTHER);

                    subtree->vertices[vertex_insert_position] = dest;

                    subtree->num_nodes++;

                    subtree->edges =

                        (semicube_edge **) MPL_realloc(subtree->edges,

                                                       (edge_insert_position + 3) *

                                                       sizeof(subtree->edges[0]), MPL_MEM_OTHER);

                    for (j = 0; j < unmarked_edge_index; j++) {

                        semicube_edge *temp_matching_edge = unmarked_edges[j];

                        if (temp_matching_edge->src == vertex && temp_matching_edge->dest == dest) {

                            subtree->edges[edge_insert_position++] = temp_matching_edge;

                            break;

                        }

                    }

                    subtree->edges[edge_insert_position++] = matching_edge;

                    subtree->num_edges += 2;

                } else if (get_distance(dest, dest_root, dest_subtree) & 1) {

                    /* Do nothing */

                } else {

                    if (root != dest_root) {

                        /* Found an augmenting path */

                        semicube_edge **first_path, **second_path;

                        int insert_index = 0;

                        int first_length = 0, second_length = 0;

                        get_path(root, vertex, forest, forest_insert_index, &first_path,

                                 &first_length);

                        get_path(dest_root, dest, forest, forest_insert_index, &second_path,

                                 &second_length);

                        current_augmenting_path =

                            MPL_calloc(current_augmenting_path, (first_length + second_length + 1) *

                                       sizeof(semicube_edge *), MPL_MEM_OTHER);

                        for (j = 0; j < first_length; j++) {

                            current_augmenting_path[insert_index++] = first_path[j];

                        }

                        current_augmenting_path[insert_index++] = edge;

                        for (j = 0; j < second_length; j++) {

                            current_augmenting_path[insert_index++] = second_path[j];

                        }

                        path_length = first_length + second_length + 1;

                        goto fn_exit;

                    } else {

                        netloc_node_t ***blossom_edges;

                        int num_blossom_nodes, stem_index, m, n;

                        get_blossom(nodes, num_nodes, edges, num_edges, unmarked_vertices,

                                    unmarked_vertex_insert, &blossom_edges,

                                    &num_blossom_nodes, &stem_index);

                        /* Contract a blossom in G and look for the path in the contracted graph */

                        for (j = stem_index + 1; j < num_blossom_nodes; j++) {

                            netloc_node_t **blossom_node = blossom_edges[j];

                            for (k = 0; k < num_nodes; k++) {

                                if (nodes[k] == blossom_node) {

                                    for (l = k; l < num_nodes - 1; l++) {

                                        nodes[l] = nodes[l + 1];

                                    }

                                    num_nodes--;

                                    k--;

                                }

                            }

                            if (j < num_blossom_nodes - 1) {

                                netloc_node_t **adj_blossom_node = blossom_edges[j];

                                for (k = 0; k < num_edges; k++) {

                                    if (edges[k]->src == blossom_node &&

                                        edges[k]->dest == adj_blossom_node) {

                                        for (l = k; l < num_edges - 1; l++) {

                                            edges[l] = edges[l + 1];

                                        }

                                        num_edges--;

                                        k--;

                                    }

                                }

                            }

                        }

                        find_augmenting_path(topology, nodes, num_nodes, edges, num_edges,

                                             &current_augmenting_path, &path_length,

                                             maximum_matching, num_matching_edges);

                        /* Find the node that connects to the stem */

                        for (j = 0; j < path_length; j++) {

                            if (current_augmenting_path[j]->src == blossom_edges[stem_index]) {

                                break;

                            }

                        }

                        for (k = stem_index + 1; k < num_blossom_nodes; k++) {

                            if (current_augmenting_path[j]->dest == blossom_edges[k]) {

                                break;

                            }

                        }

                        current_augmenting_path =

                            (semicube_edge **) MPL_realloc(current_augmenting_path,

                                                           sizeof(semicube_edge *) * (k -

                                                                                      stem_index

                                                                                      - 1),

                                                           MPL_MEM_OTHER);

                        current_augmenting_path[j]->dest =

                            current_augmenting_path[j + 1]->src = blossom_edges[stem_index + 1];

                        /* Shift edges to make room to lift blossom edges */

                        for (l = j + 1; l < path_length; l++) {

                            current_augmenting_path[l] =

                                current_augmenting_path[l + k - stem_index - 1];

                        }

                        for (l = j; l < (j + k - stem_index - 2); l++) {

                            semicube_edge edge;

                            edge.src = blossom_edges[l];

                            edge.dest = blossom_edges[l + 1];

                            current_augmenting_path[l] = &edg;;

                        }

                        MPL_free(blossom_edges);

                        goto fn_exit;

                    }

                }

            }

            /* Mark edge */

            if (unmarked_edge) {

                for (j = unmarked_edge_index; j < unmarked_edge_insert - 1; j++) {

                    unmarked_edges[j] = unmarked_edges[j + 1];

                }

                unmarked_edge_insert--;

            }

        }

        if (exposed_vertex) {

            /* Mark vertex */

            for (j = unmarked_vertex_index; j < unmarked_vertex_insert - 1; j++) {

                unmarked_vertices[j] = unmarked_vertices[j + 1];

            }

            unmarked_vertex_insert--;

        }

    }

  fn_exit:

    if (forest != NULL) {

        MPL_free(forest);

    }

    if (unmarked_vertices != NULL) {

        MPL_free(unmarked_vertices);

    }

    if (unmarked_edges != NULL) {

        MPL_free(unmarked_edges);

    }

    *augmenting_path = current_augmenting_path;

    *augmenting_path_length = path_length;

    return;

  fn_fail:

    goto fn_exit;

}

static void find_maximum_matching(netloc_topology_t topology, netloc_node_t *** nodes,

                                  int num_nodes, semicube_edge ** edges, int num_edges,

                                  semicube_edge *** maximum_matching, int *num_matching_edges)

{

    int i, j;

    semicube_edge **augmenting_path =

        (semicube_edge **) MPL_malloc(sizeof(semicube_edge *), MPL_MEM_OTHER);

    int path_length;

    int insert_location = 0;

    find_augmenting_path(topology, nodes, num_nodes, edges, num_edges, &augmenting_path,

                         &path_length, *maximum_matching, *num_matching_edges);

    if (augmenting_path != NULL && path_length > 0) {

        semicube_edge **matching =

            (semicube_edge **) MPL_malloc(sizeof(semicube_edge *), MPL_MEM_OTHER);

        /* Update the maximum matching */

        for (i = 0; i < *num_matching_edges; i++) {

            semicube_edge *edge = (*maximum_matching)[i];

            int edge_in_both_sets = 0;

            for (j = 0; j < path_length; j++) {

                semicube_edge *augmenting_path_edge = augmenting_path[j];

                if (edge->src == augmenting_path_edge->src &&

                    edge->dest == augmenting_path_edge->dest) {

                    edge_in_both_sets = 1;

                    break;

                }

            }

            if (!edge_in_both_sets) {

                matching =

                    (semicube_edge **) MPL_realloc(matching,

                                                   sizeof(semicube_edge *) * (insert_location + 1),

                                                   MPL_MEM_OTHER);

                matching[insert_location++] = edge;

            }

        }

        for (i = 0; i < path_length; i++) {

            semicube_edge *edge = augmenting_path[i];

            int edge_in_both_sets = 0;

            for (j = 0; j < *num_matching_edges; j++) {

                semicube_edge *augmenting_path_edge = (*maximum_matching)[i];

                if (edge->src == augmenting_path_edge->src &&

                    edge->dest == augmenting_path_edge->dest) {

                    edge_in_both_sets = 1;

                    break;

                }

            }

            if (!edge_in_both_sets) {

                matching =

                    (semicube_edge **) MPL_realloc(matching,

                                                   sizeof(semicube_edge *) * (insert_location + 1),

                                                   MPL_MEM_OTHER);

                matching[insert_location++] = edge;

            }

        }

        find_maximum_matching(topology, nodes, num_nodes, edges, num_edges, &matching,

                              &insert_location);

        *maximum_matching = matching;

        *num_matching_edges = insert_location;

    }

  fn_exit:

    if (augmenting_path != NULL) {

        MPL_free(augmenting_path);

    }

    return;

}

static int get_torus_attributes(netloc_topology_t topology,

                                MPIR_Netloc_network_attributes * network_attr)

{

    netloc_dt_lookup_table_t *nodes;

    struct netloc_dt_lookup_table_iterator *hti = NULL;

    netloc_node_t *start_node = NULL;

    int mpi_errno = MPI_SUCCESS;

    int num_edges = -1;

    if (network_attr->type == MPIR_NETLOC_NETWORK_TYPE__INVALID) {

        network_attr->type = MPIR_NETLOC_NETWORK_TYPE__TORUS;

        /* Check necessary condition for a torus i.e., outdegree of each node is the same */

        int node_count = 0;

        nodes =

            (netloc_dt_lookup_table_t *) MPL_malloc(sizeof(netloc_dt_lookup_table_t),

                                                    MPL_MEM_OTHER);

        mpi_errno = netloc_get_all_nodes(topology, nodes);

        hti = netloc_dt_lookup_table_iterator_t_construct(*nodes);

        while (!netloc_lookup_table_iterator_at_end(hti)) {

            netloc_node_t *node = (netloc_node_t *) netloc_lookup_table_iterator_next_entry(hti);