Functions for computing matchings during graph coarsening. More...
#include "metislib.h"
Go to the source code of this file.
Macros | |
#define | UNMATCHEDFOR2HOP 0.10 /* The fraction of unmatched vertices that triggers 2-hop */ |
Functions for computing matchings during graph coarsening.
$Id: coarsen.c 13936 2013-03-30 03:59:09Z karypis $
Definition in file coarsen.c.
#define UNMATCHEDFOR2HOP 0.10 /* The fraction of unmatched vertices that triggers 2-hop */ |
void CreateCoarseGraphPerm | ( | ctrl_t * | ctrl, |
graph_t * | graph, | ||
idx_t | cnvtxs, | ||
idx_t * | match, | ||
idx_t * | perm | ||
) |
This function creates the coarser graph. It uses a simple hash-table for identifying the adjacent vertices that get collapsed to the same node. The hash-table can have conflicts, which are handled via a linear scan. It relies on the perm[] array to visit the vertices in increasing cnvtxs order.
idx_t Match_2HopAny | ( | ctrl_t * | ctrl, |
graph_t * | graph, | ||
idx_t * | perm, | ||
idx_t * | match, | ||
idx_t | cnvtxs, | ||
size_t * | r_nunmatched, | ||
size_t | maxdegree | ||
) |
This function matches the unmatched vertices whose degree is less than maxdegree using a 2-hop matching that involves vertices that are two hops away from each other. The requirement of the 2-hop matching is a simple non-empty overlap between the adjancency lists of the vertices.