checkgraph.c File Reference

#include "metislib.h"

Include dependency graph for checkgraph.c:

Go to the source code of this file.

Functions
int	CheckGraph (graph_t *graph, int numflag, int verbose)
int	CheckInputGraphWeights (idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt)
graph_t *	FixGraph (graph_t *graph)

Function Documentation

int CheckGraph	(	graph_t *	graph,
		int	numflag,
		int	verbose
	)

This function checks if a graph is valid. A valid graph must satisfy the following constraints:

• It should contain no self-edges.
• It should be undirected; i.e., (u,v) and (v,u) should be present.
• The adjacency list should not contain multiple edges to the same other vertex.

Parameters

graph	is the graph to be checked, whose numbering starts from 0.
numflag	is 0 if error reporting will be done using 0 as the numbering, or 1 if the reporting should be done using 1.
verbose	is 1 the identified errors will be displayed, or 0, if it should run silently.

Definition at line 32 of file checkgraph.c.

int CheckInputGraphWeights	(	idx_t	nvtxs,
		idx_t	ncon,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	vsize,
		idx_t *	adjwgt
	)

This function performs a quick check of the weights of the graph

Definition at line 120 of file checkgraph.c.

graph_t* FixGraph

(

graph_t *

graph

)

This function creates a graph whose topology is consistent with Metis' requirements that:

• There are no self-edges.
• It is undirected; i.e., (u,v) and (v,u) should be present and of the same weight.
• The adjacency list should not contain multiple edges to the same other vertex.

Any of the above errors are fixed by performing the following operations:

• Self-edges are removed.
• The undirected graph is formed by the union of edges.
• One of the duplicate edges is selected.

The routine does not change the provided vertex weights.

Definition at line 176 of file checkgraph.c.