libs/ck-libs/metis/libmetis/checkgraph.c File Reference

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.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, gk_free(), PUP::l, graph_t::nvtxs, graph_t::xadj, and xadj.

Referenced by CoarsenGraph(), CoarsenGraphNlevels(), main(), METIS_NodeND(), and SetupGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, CreateGraph(), edges, gk_free(), gk_malloc(), PUP::l, graph_t::ncon, graph_t::nvtxs, PUP::u, uvw_t::u, uvwsorti(), uvw_t::v, graph_t::vsize, graph_t::vwgt, uvw_t::w, graph_t::xadj, and xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function: