graph.c File Reference

routine for handling dgraphs More...

#include "graph.h"
#include "check.h"
#include "dlpq_headers.h"
#include "dlsort_headers.h"

Classes
struct	gau_ptrs_type

Macros
#define	MTMETIS_GRAPH_C
#define	DLPQ_PREFIX   vv
#define	DLPQ_KEY_T   vtx_type
#define	DLPQ_VAL_T   vtx_type
#define	DLPQ_MIN   1
#define	DLPQ_STATIC
#define	DLSORT_PREFIX   adj
#define	DLSORT_TYPE_T   adj_type
#define	DLSORT_STATIC

Typedefs
typedef struct gau_ptrs_type	gau_ptrs_type

Functions
graph_type *	graph_create (tid_type const nthreads)
	Allocate and initialize a graph structure. More...
graph_type *	graph_setup (vtx_type *const nvtxs, adj_type **const xadj, vtx_type **const adjncy, wgt_type **const adjwgt, wgt_type **const vwgt, tid_type const nthreads)
	Setup a graph structure given this threads parts of the graph. More...
graph_type *	graph_distribute (int const distribution, vtx_type const nvtxs, adj_type const *const xadj, vtx_type const *const adjncy, wgt_type const *const vwgt, wgt_type const *const adjwgt, tid_type const nthreads)
	Distribute a csr based graph among threads. More...
void	graph_gather (graph_type const *const graph, adj_type **const r_xadj, vtx_type **const r_adjncy, wgt_type **const r_vwgt, wgt_type **const r_adjwgt, vtx_type **const 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 *const graph, vtx_type *const cnvtxs)
	Setup a coarse graph given the fine graph and the number of coarse vertices. More...
void	graph_setup_twgts (graph_type *const graph)
	Calculate and save the tvwgts of a new graph. More...
void	graph_alloc_partmemory (ctrl_type *const ctrl, graph_type *const 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 *const graph, pid_type const nparts, real_type const *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 *const graph, pid_type const *const *const gwhere)
	Compute the edgecut of a partitioning. More...
int	graph_isbalanced (ctrl_type const *const ctrl, graph_type const *const graph, real_type const 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...
size_t	graph_size (graph_type const *const graph)
	Determine the amount of memory required to store the graph. More...
void	graph_calc_dist (vtx_type const maxnvtxs, tid_type const nthreads, graphdist_type *const dist)
	Configure the distribution structure. More...
graph_type *	par_graph_create (dlthread_comm_t const comm)
	Allocate and initialize a graph structure. More...
graph_type *	par_graph_setup (vtx_type const nvtxs, adj_type *const xadj, vtx_type *const adjncy, wgt_type *const vwgt, wgt_type *const adjwgt, dlthread_comm_t const comm)
	Setup a graph structure given this threads parts of the graph. More...
void	par_graph_setup_twgts (graph_type *const graph)
	Calculate and save the twgts of a new graph. 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_gather (graph_type const *const graph, adj_type **const r_xadj, vtx_type **const r_adjncy, wgt_type **const r_vwgt, wgt_type **const r_adjwgt, vtx_type *const 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 *const ctrl, graph_type *const graph, pid_type const *const *const gwhere, int const 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 const cnvtxs)
	Setup a coarse graph given the fine graph and the number of coarse vertices. More...
void	par_graph_alloc_partmemory (ctrl_type *const ctrl, graph_type *const graph)
	Allocate memory for partition informatin. More...
tid_type	par_graph_extract_halves (graph_type *const graph, pid_type const *const *const gwhere, graph_type **const 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...
adj_type *	par_graph_build_radj (graph_type const *const graph)
	Build a reverse adjacency index and store it in graph->radj. 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 *const graph, pid_type const *const *const where)
	Compute the edgecut of a partitioning in parallel. More...
void	par_graph_removeislands (ctrl_type *const ctrl, graph_type *const graph)
	Remove island vertices from a graph and adjust parameters. More...
void	par_graph_restoreislands (ctrl_type *const ctrl, graph_type *const graph, pid_type *const *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 const distribution, vtx_type const nvtxs, adj_type const *const xadj, vtx_type const *const adjncy, wgt_type const *const vwgt, wgt_type const *const adjwgt, dlthread_comm_t const comm)
	Distribute a csr based graph among a set of active threads. More...

Detailed Description

routine for handling dgraphs

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

2012-06-12

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_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.

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.

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.

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_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.