graph.h File Reference

Types and functions for distributed graph objects. More...

#include "base.h"
#include "ctrl.h"

Go to the source code of this file.

Classes
struct	graphdist_type
struct	graph_type

Macros
#define	graph_create   MTMETIS_graph_create
#define	graph_setup   MTMETIS_graph_setup
#define	graph_distribute   MTMETIS_graph_distribute
#define	graph_gather   MTMETIS_graph_gather
#define	graph_setup_coarse   MTMETIS_graph_setup_coarse
#define	graph_setup_twgts   MTMETIS_graph_setup_twgts
#define	graph_alloc_partmemory   MTMETIS_graph_alloc_partmemory
#define	graph_free   MTMETIS_graph_free
#define	graph_free_rdata   MTMETIS_graph_free_rdata
#define	graph_imbalance   MTMETIS_graph_imbalance
#define	graph_imbalance_diff   MTMETIS_graph_imbalance_diff
#define	graph_cut   MTMETIS_graph_cut
#define	graph_isbalanced   MTMETIS_graph_isbalanced
#define	graph_readjust_memory   MTMETIS_graph_readjust_memory
#define	graph_extract_halves   MTMETIS_graph_extract_halves
#define	graph_size   MTMETIS_graph_size
#define	graph_calc_dist   MTMETIS_graph_calc_dist
#define	par_graph_create   MTMETIS_par_graph_create
#define	par_graph_setup   MTMETIS_par_graph_setup
#define	par_graph_gather   MTMETIS_par_graph_gather
#define	par_graph_shuffle   MTMETIS_par_graph_shuffle
#define	par_graph_setup_coarse   MTMETIS_par_graph_setup_coarse
#define	par_graph_setup_twgts   MTMETIS_par_graph_setup_twgts
#define	par_graph_alloc_partmemory   MTMETIS_par_graph_alloc_partmemory
#define	par_graph_free   MTMETIS_par_graph_free
#define	par_graph_free_rdata   MTMETIS_par_graph_free_rdata
#define	par_graph_readjust_memory   MTMETIS_par_graph_readjust_memory
#define	par_graph_extract_halves   MTMETIS_par_graph_extract_halves
#define	par_graph_extract_boundary   MTMETIS_par_graph_extract_boundary
#define	par_graph_extract_separator   MTMETIS_par_graph_extract_separator
#define	par_graph_extract_aseparator   MTMETIS_par_graph_extract_aseparator
#define	par_graph_build_radj   MTMETIS_par_graph_build_radj
#define	par_graph_contract   MTMETIS_par_graph_contract
#define	par_graph_intext_vtx   MTMETIS_par_graph_intext_vtx
#define	par_graph_cut   MTMETIS_par_graph_cut
#define	par_graph_removeislands   MTMETIS_par_graph_removeislands
#define	par_graph_restoreislands   MTMETIS_par_graph_restoreislands
#define	par_graph_extract_parts   MTMETIS_par_graph_extract_parts
#define	par_graph_distribute   MTMETIS_par_graph_distribute

Typedefs
typedef struct graphdist_type	graphdist_type
typedef struct graph_type	graph_type

Functions
graph_type *	graph_create (tid_type nthreads)
	Allocate and initialize a graph structure. More...
graph_type *	graph_setup (vtx_type *nvtxs, adj_type **xadj, vtx_type **adjncy, wgt_type **adjwgt, wgt_type **vwgt, tid_type nthreads)
	Setup a graph structure given this threads parts of the graph. More...
graph_type *	graph_distribute (int dist, vtx_type nvtxs, adj_type const *xadj, vtx_type const *adjncy, wgt_type const *vwgt, wgt_type const *adjwgt, tid_type nthreads)
	Distribute a csr based graph among threads. More...
void	graph_gather (graph_type const *graph, adj_type **r_xadj, vtx_type **r_adjncy, wgt_type **r_vwgt, wgt_type **r_adjwgt, vtx_type **r_voff)
	Gather a copy of the graph to each thread. Alias is private to each thread where the other three arrays are not. More...
graph_type *	graph_setup_coarse (graph_type *graph, vtx_type *cnvtxs)
	Setup a coarse graph given the fine graph and the number of coarse vertices. More...
void	graph_setup_twgts (graph_type *graph)
	Calculate and save the tvwgts of a new graph. More...
void	graph_alloc_partmemory (ctrl_type *ctrl, graph_type *graph)
	Allocate memory for partition informatin. More...
void	graph_free (graph_type *graph)
	Free a graph structure and its associated memory. More...
void	graph_free_rdata (graph_type *graph)
	Free partition/refinement data associated with a graph. More...
double	graph_imbalance (graph_type const *graph, pid_type nparts, real_type const *pijbm)
	Compute the load imbalance of a partitioning. More...
double	graph_imbalance_diff (graph_type const *const graph, pid_type const nparts, real_type const *const pijbm, real_type const ubfactor)
	Compute the amount the load imbalance of the graph violates the constraint. More...
wgt_type	graph_cut (graph_type const *graph, pid_type const *const *where)
	Compute the edgecut of a partitioning. More...
int	graph_isbalanced (ctrl_type const *ctrl, graph_type const *graph, real_type ffactor)
	Check if a partitioning of a graph is balanced within the given constraint. More...
void	graph_readjust_memory (graph_type *const graph, adj_type adjsize)
	Re-adjust the memory used the by edge arrays of a graph. More...
void	graph_extract_halves (graph_type *graph, pid_type const *const *where, graph_type **halves)
	Pull out partition 0 and partition 1 from a vertex separated graph or edge bisected graph. Vertices with high partition labels than 1 are dropped. This sets the label[][] array of the new graphs to be global vertex numbers in the original graph, and sets the rename[][] array in the original graph to be global vertex numbers in the new graph. More...
size_t	graph_size (graph_type const *graph)
	Determine the amount of memory required to store the graph. More...
void	graph_calc_dist (vtx_type maxnvtxs, tid_type nthreads, graphdist_type *dist)
	Configure the distribution structure. More...
graph_type *	par_graph_create (dlthread_comm_t comm)
	Allocate and initialize a graph structure. More...
graph_type *	par_graph_setup (vtx_type nvtxs, adj_type *xadj, vtx_type *adjncy, wgt_type *adjwgt, wgt_type *vwgt, dlthread_comm_t comm)
	Setup a graph structure given this threads parts of the graph. More...
void	par_graph_gather (graph_type const *graph, adj_type **r_xadj, vtx_type **r_adjncy, wgt_type **r_vwgt, wgt_type **r_adjwgt, vtx_type *r_voff)
	Gather a copy of the graph to each thread. Alias is private to each thread where the other three arrays are not. More...
void	par_graph_shuffle (ctrl_type *ctrl, graph_type *graph, pid_type const *const *where, int wgts)
	Shuffle the vertices in a graph such that the partition matches the owning thread. More...
graph_type *	par_graph_setup_coarse (graph_type *const graph, vtx_type cnvtxs)
	Setup a coarse graph given the fine graph and the number of coarse vertices. More...
void	par_graph_setup_twgts (graph_type *graph)
	Calculate and save the twgts of a new graph. More...
void	par_graph_alloc_partmemory (ctrl_type *ctrl, graph_type *graph)
	Allocate memory for partition informatin. More...
void	par_graph_free (graph_type *graph)
	Free a graph structure and its associated memory. More...
void	par_graph_free_rdata (graph_type *graph)
	Free partition/refinement data associated with a graph. More...
void	par_graph_readjust_memory (graph_type *const graph, adj_type adjsize)
	Re-adjust the memory used the by edge arrays of a graph. More...
tid_type	par_graph_extract_halves (graph_type *graph, pid_type const *const *where, graph_type **halves)
	Pull out partition 0 and partition 1 from a vertex separated graph or edge bisected graph. Vertices with high partition labels than 1 are dropped. This sets the label[][] array of the new graphs to be global vertex numbers in the original graph, and sets the rename[][] array in the original graph to be global vertex numbers in the new graph. More...
graph_type *	par_graph_extract_boundary (ctrl_type const *ctrl, graph_type const *graph, vtx_iset_t const *bnd)
	Extract a subgraph exposing the boundary of a bisection, where the size of the boundary is determined by the maximum imbalanced allowed in the partitioning parameters. More...
graph_type *	par_graph_extract_separator (ctrl_type const *ctrl, graph_type const *graph, vtx_iset_t const *bnd)
	Extract a subgraph consisting only the current separator and two super vertices representing each half. More...
graph_type *	par_graph_extract_aseparator (ctrl_type const *ctrl, graph_type const *graph, vtx_iset_t const *bnd)
	Extract a subgraph consisting only the current separator and two super vertices representing each half. More...
adj_type *	par_graph_build_radj (graph_type const *graph)
	Build a reverse adjacency index and store it in graph->radj. More...
void	par_graph_contract (ctrl_type *ctrl, graph_type *graph, vtx_type const cnvtxs, vtx_type const *const *gmatch, vtx_type const *fcmap)
	Create a coarse graph given a matching using hash table to identify edges to be merged. More...
void	par_graph_intext_vtx (graph_type const *const graph, vtx_type *const r_nint, vtx_type *const r_next)
	Count the number of internal and external (interface) vertices owned by this thread. More...
wgt_type	par_graph_cut (graph_type const *graph, pid_type const *const *where)
	Compute the edgecut of a partitioning in parallel. More...
void	par_graph_removeislands (ctrl_type *ctrl, graph_type *graph)
	Remove island vertices from a graph and adjust parameters. More...
void	par_graph_restoreislands (ctrl_type *ctrl, graph_type *graph, pid_type *const *gwhere)
	Restore island vertices and parameters to a graph. More...
void	par_graph_extract_parts (graph_type *const graph, pid_type const *const *const gwhere, pid_type const nparts, graph_type **const parts)
	Extract the partitions from a graph. If called with more threads than partitions, the number of threads should be a multiple of number of partitions. The supplied 'nparts' can be lower than the actual number of partitions, an donly partitions with IDs lower than 'nparts' will be extracted. More...
graph_type *	par_graph_distribute (int distribution, vtx_type nvtxs, adj_type const *xadj, vtx_type const *adjncy, wgt_type const *vwgt, wgt_type const *adjwgt, dlthread_comm_t comm)
	Distribute a csr based graph among a set of active threads. More...

Detailed Description

Types and functions for distributed graph objects.

Author

Dominique LaSalle lasal.nosp@m.le@c.nosp@m.s.umn.nosp@m..edu Copyright 2014, Regents of the University of Minnesota

Version

1

Date

2014-09-16

Function Documentation

void graph_alloc_partmemory	(	ctrl_type *	ctrl,
		graph_type *	graph
	)

Allocate memory for partition informatin.

Parameters

ctrl	The control structure containing nparts.
graph	The graph.

void graph_calc_dist	(	vtx_type	maxnvtxs,
		tid_type	nthreads,
		graphdist_type *	dist
	)

Configure the distribution structure.

Parameters

maxnvtxs	The maximum number of vertices owned by a thread.
nthreads	The number of threads.
dist	The distribution structure to configure.

graph_type* graph_create

(

tid_type

nthreads

)

Allocate and initialize a graph structure.

Parameters

nthreads

The number of threads the graph will be used by.

Returns

The allocated and initialized graph.

wgt_type graph_cut	(	graph_type const *	graph,
		pid_type const *const *	where
	)

Compute the edgecut of a partitioning.

Parameters

graph	The graph structure.
where	The partition labels.

Returns

The total weight of cut edges.

graph_type* graph_distribute	(	int	dist,
		vtx_type	nvtxs,
		adj_type const *	xadj,
		vtx_type const *	adjncy,
		wgt_type const *	vwgt,
		wgt_type const *	adjwgt,
		tid_type	nthreads
	)

Distribute a csr based graph among threads.

Parameters

dist	The type of distribution to use.
nvtxs	The number of vertices in the graph.
xadj	The adjacency list poitner.
adjncy	The adjacecny list.
vwgt	The vertex weights.
adjwgt	The edge weights.
nthreads	The number of threads to distribute the graph between.

Returns

The distributed graph.

void graph_extract_halves	(	graph_type *	graph,
		pid_type const *const *	where,
		graph_type **	halves
	)

Pull out partition 0 and partition 1 from a vertex separated graph or edge bisected graph. Vertices with high partition labels than 1 are dropped. This sets the label[][] array of the new graphs to be global vertex numbers in the original graph, and sets the rename[][] array in the original graph to be global vertex numbers in the new graph.

Parameters

graph	The graph to extract subgraphs from.
where	The partition ID's of each vertex.
halves	The two extracted subgraphs (output).

void graph_free

(

graph_type *

graph

)

Free a graph structure and its associated memory.

Parameters

graph

The graph to free.

void graph_free_rdata

(

graph_type *

graph

)

Free partition/refinement data associated with a graph.

Parameters

graph

The graph to free the associated partition/refinement data of.

void graph_gather	(	graph_type const *	graph,
		adj_type **	r_xadj,
		vtx_type **	r_adjncy,
		wgt_type **	r_vwgt,
		wgt_type **	r_adjwgt,
		vtx_type **	r_voff
	)

Gather a copy of the graph to each thread. Alias is private to each thread where the other three arrays are not.

Parameters

graph	The distributed graph to gather.
r_xadj	A refernce to the adjacency list pointer.
r_adjncy	A reference to the adjacency list.
r_vwgt	A reference to the vertex weight.
r_adjwgt	A reference to the edge weight.
r_voff	A reference to the offset of the vertices for this thread.

double graph_imbalance	(	graph_type const *	graph,
		pid_type	nparts,
		real_type const *	pijbm
	)

Compute the load imbalance of a partitioning.

Parameters

graph	The graph.
nparts	The number of partitions.
pijbm	The inverted average partition weight.

Returns

The imbalance of the partitioning.

double graph_imbalance_diff	(	graph_type const *const	graph,
		pid_type const	nparts,
		real_type const *const	pijbm,
		real_type const	ubfactor
	)

Compute the amount the load imbalance of the graph violates the constraint.

Parameters

graph	The graph.
nparts	The number of partitions.
pijbm	The inverted average partition weight.
ubfactor	The allowed imbalance constraint.

Returns

The amount of imbalance in excess of the constraint.

int graph_isbalanced	(	ctrl_type const *	ctrl,
		graph_type const *	graph,
		real_type	ffactor
	)

Check if a partitioning of a graph is balanced within the given constraint.

Parameters

ctrl	The control structure.
graph	The partitioned graph.
ffactor	The balance constraint.

Returns

1 if the partitioning is balanced.

void graph_readjust_memory	(	graph_type *const	graph,
		adj_type	adjsize
	)

Re-adjust the memory used the by edge arrays of a graph.

Parameters

graph	The graph structure.
adjsize	The current size of the adjacency arrays.

graph_type* graph_setup	(	vtx_type *	nvtxs,
		adj_type **	xadj,
		vtx_type **	adjncy,
		wgt_type **	adjwgt,
		wgt_type **	vwgt,
		tid_type	nthreads
	)

Setup a graph structure given this threads parts of the graph.

Parameters

nvtxs	The number of vertices in the graph.
xadj	The adjacency list pointer.
adjncy	The adjacency list.
adjwgt	The edge weights.
vwgt	The vertex weights.
nthreads	The number of threads the graph is distributed across.

Returns

The setup graph structure.

graph_type* graph_setup_coarse	(	graph_type *	graph,
		vtx_type *	cnvtxs
	)

Setup a coarse graph given the fine graph and the number of coarse vertices.

Parameters

graph	The fine graph.
cnvtxs	The number of coarse vertices for each thread.

Returns

The allocated and setup coarse graph.

void graph_setup_twgts

(

graph_type *

graph

)

Calculate and save the tvwgts of a new graph.

Parameters

graph

The graph.

size_t graph_size

(

graph_type const *

graph

)

Determine the amount of memory required to store the graph.

Parameters

graph

The graph to calculate the size of.

Returns

The number of bytes required to store the graph.

void par_graph_alloc_partmemory	(	ctrl_type *	ctrl,
		graph_type *	graph
	)

Allocate memory for partition informatin.

Parameters

ctrl	The control structure containing nparts.
graph	The graph.

adj_type* par_graph_build_radj

(

graph_type const *

graph

)

Build a reverse adjacency index and store it in graph->radj.

Parameters

graph

The graph to build the reverse adjacency list of.

Returns

The reverse adjacecny index.

void par_graph_contract	(	ctrl_type *	ctrl,
		graph_type *	graph,
		vtx_type const	cnvtxs,
		vtx_type const *const *	gmatch,
		vtx_type const *	fcmap
	)

Create a coarse graph given a matching using hash table to identify edges to be merged.

Parameters

ctrl	The control structure.
graph	The fine graph.
cnvtxs	The number of coarse vertices in the coarse graph.
match	The matchings of vertices (match[match[v]] = v).
fcmap	The mapping of the coarse vertex number to the lowest number fine vertex in the coarse vertex.

graph_type* par_graph_create

(

dlthread_comm_t

comm

)

Allocate and initialize a graph structure.

Parameters

nthreads

The thread communicator.

Returns

The allocated and initialized graph.

wgt_type par_graph_cut	(	graph_type const *	graph,
		pid_type const *const *	where
	)

Compute the edgecut of a partitioning in parallel.

Parameters

graph	The graph structure.
where	The partition labels.

Returns

The total weight of cut edges.

graph_type* par_graph_distribute	(	int	distribution,
		vtx_type	nvtxs,
		adj_type const *	xadj,
		vtx_type const *	adjncy,
		wgt_type const *	vwgt,
		wgt_type const *	adjwgt,
		dlthread_comm_t	comm
	)

Distribute a csr based graph among a set of active threads.

Parameters

dist	The type of distribution to use.
nvtxs	The number of vertices in the graph.
xadj	The adjacency list pointer.
adjncy	The adjacecny list.
vwgt	The vertex weights.
adjwgt	The edge weights.
comm	The active thread communicator.

Returns

The distributed graph.

graph_type* par_graph_extract_aseparator	(	ctrl_type const *	ctrl,
		graph_type const *	graph,
		vtx_iset_t const *	bnd
	)

Extract a subgraph consisting only the current separator and two super vertices representing each half.

Each thread will have two vertices represent the core of each partition, at indices 0 and 1.

Parameters

ctrl	The control structure.
graph	The graph.
bnd	The set of vertices on the immediate boundary.

Returns

The extract boundary subgraph.

graph_type* par_graph_extract_boundary	(	ctrl_type const *	ctrl,
		graph_type const *	graph,
		vtx_iset_t const *	bnd
	)

Extract a subgraph exposing the boundary of a bisection, where the size of the boundary is determined by the maximum imbalanced allowed in the partitioning parameters.

Each thread will have two vertices represent the core of each partition, at indices 0 and 1.

Parameters

ctrl	The control structure.
graph	The graph.
bnd	The set of vertices on the immediate boundary.

Returns

The extract boundary subgraph.

tid_type par_graph_extract_halves	(	graph_type *	graph,
		pid_type const *const *	where,
		graph_type **	halves
	)

Pull out partition 0 and partition 1 from a vertex separated graph or edge bisected graph. Vertices with high partition labels than 1 are dropped. This sets the label[][] array of the new graphs to be global vertex numbers in the original graph, and sets the rename[][] array in the original graph to be global vertex numbers in the new graph.

Parameters

graph	The graph to extract subgraphs from.
where	The partition ID's of each vertex.
halves	The two extracted subgraphs (output).

Returns

Which half of the graph this thread is assigned.

void par_graph_extract_parts	(	graph_type *const	graph,
		pid_type const *const *const	gwhere,
		pid_type const	nparts,
		graph_type **const	parts
	)

Extract the partitions from a graph. If called with more threads than partitions, the number of threads should be a multiple of number of partitions. The supplied 'nparts' can be lower than the actual number of partitions, an donly partitions with IDs lower than 'nparts' will be extracted.

Parameters

graph	The graph to extract partitions from.
gwhere	The partition id of each vertex.
nparts	The number of partitions to extract.
parts	The extracted partitions (output), should be of lenght nparts.

graph_type* par_graph_extract_separator	(	ctrl_type const *	ctrl,
		graph_type const *	graph,
		vtx_iset_t const *	bnd
	)

Extract a subgraph consisting only the current separator and two super vertices representing each half.

Each thread will have two vertices represent the core of each partition, at indices 0 and 1.

Parameters

ctrl	The control structure.
graph	The graph.
bnd	The set of vertices on the immediate boundary.

Returns

The extract boundary subgraph.

void par_graph_free

(

graph_type *

graph

)

Free a graph structure and its associated memory.

Parameters

graph

The graph to free.

void par_graph_free_rdata

(

graph_type *

graph

)

Free partition/refinement data associated with a graph.

Parameters

graph

The graph to free the associated partition/refinement data of.

void par_graph_gather	(	graph_type const *	graph,
		adj_type **	r_xadj,
		vtx_type **	r_adjncy,
		wgt_type **	r_vwgt,
		wgt_type **	r_adjwgt,
		vtx_type *	r_voff
	)

Gather a copy of the graph to each thread. Alias is private to each thread where the other three arrays are not.

Parameters

graph	The distributed graph to gather.
r_xadj	A refernce to the adjacency list pointer.
r_adjncy	A reference to the adjacency list.
r_vwgt	A reference to the vertex weight.
r_adjwgt	A reference to the edge weight.
r_voff	A reference to the offset of the vertices for this thread.

void par_graph_intext_vtx	(	graph_type const *const	graph,
		vtx_type *const	r_nint,
		vtx_type *const	r_next
	)

Count the number of internal and external (interface) vertices owned by this thread.

Parameters

graph	The graph.
r_nint	A reference to the number of internal vertices.
r_next	A reference to the number of external vertices.

void par_graph_readjust_memory	(	graph_type *const	graph,
		adj_type	adjsize
	)

Re-adjust the memory used the by edge arrays of a graph.

Parameters

graph	The graph structure.
adjsize	The current size of the adjacency arrays.

void par_graph_removeislands	(	ctrl_type *	ctrl,
		graph_type *	graph
	)

Remove island vertices from a graph and adjust parameters.

Parameters

ctrl	The control structure.
graph	The graph structure.

void par_graph_restoreislands	(	ctrl_type *	ctrl,
		graph_type *	graph,
		pid_type *const *	gwhere
	)

Restore island vertices and parameters to a graph.

Parameters

ctrl	The control structure.
graph	The graph structure.
gwhere	The where vector (should be large enough to hold island vertices).

graph_type* par_graph_setup	(	vtx_type	nvtxs,
		adj_type *	xadj,
		vtx_type *	adjncy,
		wgt_type *	adjwgt,
		wgt_type *	vwgt,
		dlthread_comm_t	comm
	)

Setup a graph structure given this threads parts of the graph.

Parameters

nvtxs	The number of vertices in the graph.
xadj	The adjacency list pointer.
adjncy	The adjacency list.
adjwgt	The edge weights.
vwgt	The vertex weights.
comm	The thread communicator.

Returns

The setup graph structure.

graph_type* par_graph_setup_coarse	(	graph_type *const	graph,
		vtx_type	cnvtxs
	)

Setup a coarse graph given the fine graph and the number of coarse vertices.

Parameters

graph	The fine graph.
cnvtxs	The number of coarse vertices.

Returns

The allocated and setup coarse graph.

void par_graph_setup_twgts

(

graph_type *

graph

)

Calculate and save the twgts of a new graph.

Parameters

graph

The graph.

void par_graph_shuffle	(	ctrl_type *	ctrl,
		graph_type *	graph,
		pid_type const *const *	where,
		int	wgts
	)

Shuffle the vertices in a graph such that the partition matches the owning thread.

Parameters

ctrl	The control structure.
graph	The graph to shuffle.
where	The partition (destination thread) ids of each vertex.
wgts	Preserve the current weight information.