Functions
contig.c File Reference

Functions that deal with eliminating disconnected partitions. More...

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

Go to the source code of this file.

Functions

void ComputeBFSOrdering (ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
 
void EliminateComponents (ctrl_t *ctrl, graph_t *graph)
 
idx_t FindPartitionInducedComponents (graph_t *graph, idx_t *where, idx_t *cptr, idx_t *cind)
 
idx_t FindSepInducedComponents (ctrl_t *ctrl, graph_t *graph, idx_t *cptr, idx_t *cind)
 
idx_t IsConnected (graph_t *graph, idx_t report)
 
idx_t IsConnectedSubdomain (ctrl_t *ctrl, graph_t *graph, idx_t pid, idx_t report)
 
void MoveGroupContigForCut (ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind)
 
void MoveGroupContigForVol (ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
 

Detailed Description

Functions that deal with eliminating disconnected partitions.

Date
Started 7/15/98
Author
George
Copyright 1997-2009, Regents of the University of Minnesota
Version
Id
contig.c 10513 2011-07-07 22:06:03Z karypis

Definition in file contig.c.

Function Documentation

◆ ComputeBFSOrdering()

void ComputeBFSOrdering ( ctrl_t ctrl,
graph_t graph,
idx_t bfsperm 
)

This function computes a permutation of the vertices based on a breadth-first-traversal. It can be used for re-ordering the graph to reduce its bandwidth for better cache locality.

Parameters
ctrlis the control structure
graphis the graph structure
permis the array that upon completion, perm[i] will store the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Definition at line 115 of file contig.c.

◆ EliminateComponents()

void EliminateComponents ( ctrl_t ctrl,
graph_t graph 
)

This function finds all the connected components induced by the partitioning vector in graph->where and tries to push them around to remove some of them.

Definition at line 336 of file contig.c.

◆ FindPartitionInducedComponents()

idx_t FindPartitionInducedComponents ( graph_t graph,
idx_t where,
idx_t cptr,
idx_t cind 
)

This function finds the connected components induced by the partitioning vector.

Parameters
graphis the graph structure
whereis the partitioning vector. If this is NULL, then the entire graph is treated to belong into a single partition.
cptris the ptr structure of the CSR representation of the components. The length of this vector must be graph->nvtxs+1.
cindis the indices structure of the CSR representation of the components. The length of this vector must be graph->nvtxs.
Returns
the number of components that it found.
Note
The cptr and cind parameters can be NULL, in which case only the number of connected components is returned.

Definition at line 32 of file contig.c.

◆ FindSepInducedComponents()

idx_t FindSepInducedComponents ( ctrl_t ctrl,
graph_t graph,
idx_t cptr,
idx_t cind 
)

This function identifies the number of connected components in a graph that result after removing the vertices that belong to the vertex separator (i.e., graph->where[i] == 2). The connected component memberships are returned in the CSR-style pair of arrays cptr, cind.

Definition at line 267 of file contig.c.

◆ IsConnected()

idx_t IsConnected ( graph_t graph,
idx_t  report 
)

This function checks whether a graph is contiguous or not.

Definition at line 167 of file contig.c.

◆ IsConnectedSubdomain()

idx_t IsConnectedSubdomain ( ctrl_t ctrl,
graph_t graph,
idx_t  pid,
idx_t  report 
)

This function checks whether or not partition pid is contigous

Definition at line 184 of file contig.c.

◆ MoveGroupContigForCut()

void MoveGroupContigForCut ( ctrl_t ctrl,
graph_t graph,
idx_t  to,
idx_t  gid,
idx_t ptr,
idx_t ind 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 531 of file contig.c.

◆ MoveGroupContigForVol()

void MoveGroupContigForVol ( ctrl_t ctrl,
graph_t graph,
idx_t  to,
idx_t  gid,
idx_t ptr,
idx_t ind,
idx_t vmarker,
idx_t pmarker,
idx_t modind 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 601 of file contig.c.



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