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 */ |
Detailed Description
Functions for computing matchings during graph coarsening.
- Date
- Started 7/23/97
- Version
$Id: coarsen.c 13936 2013-03-30 03:59:09Z karypis $
Definition in file coarsen.c.
Macro Definition Documentation
| #define UNMATCHEDFOR2HOP 0.10 /* The fraction of unmatched vertices that triggers 2-hop */ |
Function Documentation
| 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.