Macros | Functions
coarsen.c File Reference

Functions for computing matchings during graph coarsening. More...

#include "metislib.h"
Include dependency graph for coarsen.c:

Go to the source code of this file.

Macros

#define UNMATCHEDFOR2HOP   0.10 /* The fraction of unmatched vertices that triggers 2-hop */
 

Functions

graph_tCoarsenGraph (ctrl_t *ctrl, graph_t *graph)
 
graph_tCoarsenGraphNlevels (ctrl_t *ctrl, graph_t *graph, idx_t nlevels)
 
void CreateCoarseGraph (ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match)
 
void CreateCoarseGraphNoMask (ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match)
 
void CreateCoarseGraphPerm (ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match, idx_t *perm)
 
idx_t Match_2Hop (ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t nunmatched)
 
idx_t Match_2HopAll (ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
 
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)
 
idx_t Match_RM (ctrl_t *ctrl, graph_t *graph)
 
idx_t Match_SHEM (ctrl_t *ctrl, graph_t *graph)
 
void PrintCGraphStats (ctrl_t *ctrl, graph_t *graph)
 
void ReAdjustMemory (ctrl_t *ctrl, graph_t *graph, graph_t *cgraph)
 
graph_tSetupCoarseGraph (graph_t *graph, idx_t cnvtxs, idx_t dovsize)
 

Detailed Description

Functions for computing matchings during graph coarsening.

Date
Started 7/23/97
Author
George
Copyright 1997-2011, Regents of the University of Minnesota
Version
$Id: coarsen.c 13936 2013-03-30 03:59:09Z karypis $ 

Definition in file coarsen.c.

Macro Definition Documentation

◆ UNMATCHEDFOR2HOP

#define UNMATCHEDFOR2HOP   0.10 /* The fraction of unmatched vertices that triggers 2-hop */

Definition at line 14 of file coarsen.c.

Function Documentation

◆ CoarsenGraph()

graph_t* CoarsenGraph ( ctrl_t ctrl,
graph_t graph 
)

This function takes a graph and creates a sequence of coarser graphs. It implements the coarsening phase of the multilevel paradigm.

Definition at line 22 of file coarsen.c.

◆ CoarsenGraphNlevels()

graph_t* CoarsenGraphNlevels ( ctrl_t ctrl,
graph_t graph,
idx_t  nlevels 
)

This function takes a graph and creates a sequence of nlevels coarser graphs, where nlevels is an input parameter.

Definition at line 85 of file coarsen.c.

◆ CreateCoarseGraph()

void CreateCoarseGraph ( ctrl_t ctrl,
graph_t graph,
idx_t  cnvtxs,
idx_t match 
)

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.

Definition at line 621 of file coarsen.c.

◆ CreateCoarseGraphNoMask()

void CreateCoarseGraphNoMask ( ctrl_t ctrl,
graph_t graph,
idx_t  cnvtxs,
idx_t match 
)

This function creates the coarser graph. It uses a full-size array (htable) for identifying the adjacent vertices that get collapsed to the same node.

Definition at line 800 of file coarsen.c.

◆ CreateCoarseGraphPerm()

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.

Definition at line 932 of file coarsen.c.

◆ Match_2Hop()

idx_t Match_2Hop ( ctrl_t ctrl,
graph_t graph,
idx_t perm,
idx_t match,
idx_t  cnvtxs,
size_t  nunmatched 
)

This function matches the unmatched vertices using a 2-hop matching that involves vertices that are two hops away from each other.

Definition at line 415 of file coarsen.c.

◆ Match_2HopAll()

idx_t Match_2HopAll ( 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 that of identical adjacency lists.

Definition at line 516 of file coarsen.c.

◆ Match_2HopAny()

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.

Definition at line 437 of file coarsen.c.

◆ Match_RM()

idx_t Match_RM ( ctrl_t ctrl,
graph_t graph 
)

This function finds a matching by randomly selecting one of the unmatched adjacent vertices.

Definition at line 149 of file coarsen.c.

◆ Match_SHEM()

idx_t Match_SHEM ( ctrl_t ctrl,
graph_t graph 
)

This function finds a matching using the HEM heuristic. The vertices are visited based on increasing degree to ensure that all vertices are given a chance to match with something.

Definition at line 276 of file coarsen.c.

◆ PrintCGraphStats()

void PrintCGraphStats ( ctrl_t ctrl,
graph_t graph 
)

This function prints various stats for each graph during coarsening

Definition at line 601 of file coarsen.c.

◆ ReAdjustMemory()

void ReAdjustMemory ( ctrl_t ctrl,
graph_t graph,
graph_t cgraph 
)

This function re-adjusts the amount of memory that was allocated if it will lead to significant savings

Definition at line 1126 of file coarsen.c.

◆ SetupCoarseGraph()

graph_t* SetupCoarseGraph ( graph_t graph,
idx_t  cnvtxs,
idx_t  dovsize 
)

Setup the various arrays for the coarse graph

Definition at line 1093 of file coarsen.c.



gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:40:48