graph.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>
#include "slist.h"
#include "set.h"
#include "utils.h"

Go to the source code of this file.

Typedefs
typedef enum VertexColor_	VertexColor
typedef struct Vertex_ *	Vertex
typedef struct Graph_ *	Graph
typedef SlistNode	VertexNode
typedef SlistNode	EdgeNode

Enumerations
enum	VertexColor_ { white, gray, black }

Functions
Graph	GRAPHinit (int(*match)(const void *key1, const void *key2), void(*destroy)(void *data))
void	GRAPHdestroy (Graph graph)
int	GRAPHinsvertex (Graph graph, const void *vtxdata)
int	GRAPHinsedge (Graph graph, const void *vtxdata, const void *adjdata)
int	GRAPHremvertex (Graph graph, void **vtxdata)
int	GRAPHremedge (Graph graph, void *vtxdata, void **edgedata)
VertexNode	GRAPHgetvertexhead (Graph graph)
EdgeNode	GRAPHgetedgehead (VertexNode vtxnode)
VertexNode	GRAPHgetvertexnext (VertexNode vtxnode)
EdgeNode	GRAPHgetedgenext (EdgeNode enode)
void *	GRAPHgetvertexdata (VertexNode vtxnode)
void *	GRAPHgetedgedata (EdgeNode enode)
int	GRAPHgetedgecount (VertexNode vtxnode)
int	GRAPHvcount (Graph graph)
int	GRAPHecount (Graph graph)
void	GRAPHprint (Graph graph, void(*vtxcallback)(const void *data), void(*edgecallback)(const void *data))
void	GRAPHtraverse (Graph graph, void(*vtxcallback)(const void *data), void(*edgecallback)(const void *data))
VertexNode	GRAPHfindvertex (const Graph graph, const void *vtxdata)
EdgeNode	GRAPHfindedge (const Graph graph, const void *vtxdata, const void *edgedata)
int	GRAPHis_adjacent (const Graph graph, const void *vtxdata, const void *edgedata)
int	GRAPHis_isolated (const Graph graph, const void *vtxdata)

Typedef Documentation

typedef struct Graph_* Graph

Use a typedef - to hide the interior of Graph_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 57 of file graph.h.

typedef struct Vertex_* Vertex

Use a typedef - to hide the interior of Vertex_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 50 of file graph.h.

typedef enum VertexColor_ VertexColor

Define colors for vertices in graphs

Enumeration Type Documentation

enum VertexColor_

Define colors for vertices in graphs

Definition at line 42 of file graph.h.

Function Documentation

void GRAPHdestroy

(

Graph

graph

)

Destroy the graph

The graph is destroyed - that is, all the memory occupied by the vertices and edges is deallocated. The user-defined callback function destroy, given as an argument to GRAPHinit(), is responsible for freeing dynamically allocated vertex/edge data, when this function is called. When all vertices/edges and corresponding data have been deallocated - the graph header is deallocated, too.

Parameters

[in]

graph

- a reference to current graph.

Returns

Nothing.

See Also

GRAPHinit()

Definition at line 70 of file graph.c.

int GRAPHecount

(

Graph

graph

)

Get total number of edges

Parameters

[in]

graph

- a reference to current graph.

Returns

The total number of edges contained in graph.

Definition at line 300 of file graph.c.

EdgeNode GRAPHfindedge	(	const Graph	graph,
		const void *	vtxdata,
		const void *	edgedata
	)

Find edge - incident from vertex specified by vtxdata - and also incident to vertex specfied by edgedata

Search the graph for an edge, whose data matches search key data referenced by parameter edgedata. Moreover, this data should be found in a node, present in the adjacency list of a vertex, matching data referenced by parameter vtxdata. Thus, if an edge exists, incident from vertex specified by vtxdata - and also incident to vertex specified by edgedata - then a node must exist in the adjacency list of vertex specified by vtxdata, that is matching edgedata. In other words, parameter edgedata specifies the vertex, which the target edge is incident to. This is how edges are implemented in our graph. A reference to the node with a match will be returned - NULL otherwise. A user-defined callback function, responsible for doing the matching of node data - with data referenced by parameter data - must exist for this function to work - otherwise NULL will be returned - always. This user-supplied match-callback is set into the graph when it was created, with a call to function - GRAPHinit().

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- reference to search key data for the vertex node, which the target edge is incident from.
[in]	edgedata	- reference to search key data for the (edge) node - situated in the adjacency list of vertex node specified by parameter vtxdata

Returns

A reference to a node in the adjacency list of vertex node specified by vtxdata, that is matching search (key) data referenced by edgedata, if found - or NULL otherwise.

See Also

GRAPHis_adjacent()

Definition at line 359 of file graph.c.

VertexNode GRAPHfindvertex	(	const Graph	graph,
		const void *	vtxdata
	)

Find vertex node containing data referenced by vtxdata

Search the graph for a vertex, whose data matches the search key data referenced by parameter vtxdata. A reference to the vertex with a match will be returned - NULL otherwise. A user-defined callback function, responsible for doing the matching of vertex data - with data referenced by parameter vtxdata - must exist for this function to work - otherwise NULL will be returned - always. This user-supplied match-callback was set into the graph when it was created, with a call to function - GRAPHinit().

Parameters

[in]	graph	- a reference to current graph
[in]	vtxdata	- a reference to search key data for the vertex to be found

Returns

A reference to vertex node matching search key data referenced by parameter vtxdata, if found - or NULL otherwise

Definition at line 342 of file graph.c.

int GRAPHgetedgecount

(

VertexNode

vtxnode

)

Get number of edges incident from a vertex

Alternate desription: Get the number of nodes in the adjacency list of the vertex node vtxdata.

Parameters

[in]

vtxnode

- a reference to a valid vertex node in the graph.

Returns

The total number of edges incident from the vertex specified by vtxnode.

Definition at line 290 of file graph.c.

void* GRAPHgetedgedata

(

EdgeNode

enode

)

Get data from an edge

Parameters

[in]

enode

- reference to a valid node in an adjacency list of a vertex node in the graph.

Returns

A reference to the data part of parameter enode.

Definition at line 263 of file graph.c.

EdgeNode GRAPHgetedgehead

(

VertexNode

vtxnode

)

Get the first edge node

Parameters

[in]

vtxnode

- reference to a valid vertex node in the graph.

Returns

A reference to the first node in the collection of adjacent nodes, incident from argument vtxnode.

Definition at line 273 of file graph.c.

EdgeNode GRAPHgetedgenext

(

EdgeNode

enode

)

Get next edge node

Parameters

[in]

enode

- reference to a valid node in an adjacency list of a vertex node in the graph.

Returns

A reference to the next node in the adjacency list.

Definition at line 285 of file graph.c.

void* GRAPHgetvertexdata

(

VertexNode

vtxnode

)

Get data part from a vertex

Parameters

[in]

vtxnode

- reference to a valid vertex node in the graph.

Returns

A reference to the data part of parameter vtxnode.

Definition at line 258 of file graph.c.

VertexNode GRAPHgetvertexhead

(

Graph

graph

)

Get the first vertex node

Parameters

[in]

graph

- a reference to current graph.

Returns

A reference to the first vertex node in the graph.

Definition at line 268 of file graph.c.

VertexNode GRAPHgetvertexnext

(

VertexNode

vtxnode

)

Get next vertex node

Parameters

[in]

vtxnode

- reference to a valid vertex node in the graph.

Returns

A reference to the next vertex node in the graph.

Definition at line 280 of file graph.c.

Graph GRAPHinit	(	int(*)(const void *key1, const void *key2)	match,
		void(*)(void *data)	destroy
	)

Initialize the graph

This function simply sets up the graph so that it can be used in forthcoming operations, i.e. internal counters are set to 0, and the call-backs given as parameters are encapsulated within the graph structure.

Parameters

[in]	match	- a reference to a user-defined function that receives references to vertex key data - and search key data - via its parameters key1 and key2. Hence this callback function can make the actual matching of search key and vertex key data - and determine if search data is present in the graph. This callback function shall return 1 - in case of a hit - or 0 otherwise.
[in]	destroy	- A reference to a user-defined function, reponsible for freeing vertex and edge data, when the graph is deleted. If destroy is NULL - then vertex and edge data will be left untouched when the graph is destroyed.

Returns

A reference - to a new, empty graph - if dynamic memory allocation for the ADT was successful - or NULL otherwise. Take really good care of this return value, since it will be needed as a parameter in subsequent calls - to the majority of other graph handling functions in this function interface - i.e. a sort of "handle" to the graph.

See Also

GRAPHdestroy()

Definition at line 46 of file graph.c.

int GRAPHinsedge	(	Graph	graph,
		const void *	vtxdata,
		const void *	adjdata
	)

Insert an edge, incident from vertex specified by vtxdata - and also incident to vertex specified by adjdata.

Both vertices making up the edge must, of course, already exist in the graph, that is, have been inserted previously by a call to GRAPHinsvertex(). The newly inserted edge is represented by a node, with a reference to adjdata, in the adjacency(=edge) list of the vertex specified by vtxdata. The memory referenced by adjdata should remain valid as long as the edge remains in the graph. This memory is also where you normally put edge data specifics - such as cost, distance, etc. It's the responsibility of the caller to manage the storage referenced by adjdata. To model an edge (u,v) in an undirected graph, you should call this interface function twice: First time to insert an edge from u to v - and again to insert an edge in the opposite direction - from v to u. Thus, in undirected graphs, you have to do 2 edge insertions for each (undirected) edge.

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- a reference to search (key) data of the vertex, which the edge is incident from.
[in]	adjdata	- a reference to data of the vertex, which the edge is incident to. This referenced data memory must remain valid as long as the edge remains in the graph - and it is the responsibility of the caller to handle it from now on.

Returns

Value 0 - if the insertion was successful
Value 1 - if an edge incident from vertex specified by vtxdata - and incident to vertex specified by adjdata - already exists in the graph - i.e. you are trying to insert a duplicate edge
Value -2 - if one - or both vertices specified by vtxdata and adjdata, respectively - is/are missing in the graph. Thus, both vertices must exist prior to successful insertion of an edge.
Value -1 - otherwise, indicating some other (probably fatal) error

Definition at line 133 of file graph.c.

int GRAPHinsvertex	(	Graph	graph,
		const void *	vtxdata
	)

Insert a vertex into the graph

The new vertex node inserted will contain a pointer to vtxdata, so the memory referenced by vtxdata must be valid as long as the vertex is part of the graph. It's the responsibility of the caller to manage this memory - referenced by vtxdata.

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- reference to data of vertex to be inserted.

Returns

Value 0 - if the insertion was successful
Value 1 - if vertex containing vtxdata already exists(=duplicate) in the graph
Value -1 - otherwise, indicating some other (possibly fatal) error

Definition at line 99 of file graph.c.

int GRAPHis_adjacent	(	const Graph	graph,
		const void *	vtxdata,
		const void *	edgedata
	)

Determine if 2 vertices are adjacent - i.e. if there is an edge connecting them

More in detail, this function determines if there is an edge - incident from vertex matching search key data referenced by parameter vtxdata - which is incident to another vertex, matching search key data referenced by parameter edgedata. Or - equivalently put - if vertex matching search key data referenced by edgedata is present in the adjacency list of vertex specified by parameter vtxdata.

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- reference to search key data for vertex, which the edge is incident from.
[in]	edgedata	- reference to search key data for vertex, which the edge is incident to.

Returns

Value 1 - if there is an edge incident from vertex specified by vtxdata - (incident) to a vertex specified by edgedata - or 0 otherwise.

Definition at line 305 of file graph.c.

int GRAPHis_isolated	(	const Graph	graph,
		const void *	vtxdata
	)

Determine if a vertex is isolated - i.e. has no (in- or outgoing) edges

If a vertex is to be considered isolated - the following must be true:

• The vertex specified with parameter vtxdata must not have any edges incident to it - i.e. it must not be part of any adjacency list in the graph, whatsoever.
• Moreover, this vertex must not have any edges incident from it - i.e. its own adjacency list must be empty.

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- reference to search key data for target vertex.

Returns

Value 1 - if target vertex is isolated - 0 otherwise.

Definition at line 311 of file graph.c.

void GRAPHprint	(	Graph	graph,
		void(*)(const void *data)	vtxcallback,
		void(*)(const void *data)	edgecallback
	)

Print all vertex and edge data of the graph - on screen

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxcallback	- reference to user-defined callback function, that gets read access to vertex data via its parameter vtxcallback - to do whatever is relevant. In this case it is a matter of formatting vertex data for printing on screen. The printed data should be kept to a minimum (the key value, for example) in order not to clutter the screen. This function is primarily for small graphs and debugging purposes
[in]	edgecallback	- reference to user-defined callback function, that gets read access to edge data via its parameter edgecallback - to do whatever is relevant. In this case it is a matter of formatting edge data for printing on screen. The printed data should be kept to a minimum (the key value, for example) in order not to clutter the screen. This function is primarily for small graphs and debugging purposes

Returns

Nothing.

Definition at line 232 of file graph.c.

int GRAPHremedge	(	Graph	graph,
		void *	vtxdata,
		void **	edgedata
	)

Remove edge - incident from vertex specified by vtxdata - and also incident to vertex spec. by edgedata

When called, the 3rd parameter of this function, edgedata, should reference an (external) pointer, that points to edge search (key) data. After the call - this pointer referenced by parameter edgedata, has been redirected to point to data part of the removed (edge) node - if the call was succesful. The caller is responsible for the future of this memory - deallocating it, if needed, for example. This removed edge data will typically contain:

• search (key) data for the vertex, which this edge is incident to..
• ..and, moreover, edge specific data, such as cost, weight, etc.

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxdata	- a reference to vertex search (key) data of the vertex, which the target edge is incident from..
[in,out]	edgedata	- a reference to an external pointer, initially pointing to edge search (key) data. After the call, the external pointer is redirected to reference removed edge data - i.e. search key data for the vertex, which the edge is incident to.

Returns

Value 0 - if removal of edge was successful
Value -2 - if one or both of the vertices constituting the edge - is/are missing.
Value -1 - otherwise, indicating some other (possibly fatal) error.

See Also

GRAPHinsedge()

Definition at line 207 of file graph.c.

int GRAPHremvertex	(	Graph	graph,
		void **	vtxdata
	)

Removal of vertex - with data referenced by vtxdata

When called, the 2nd parameter of this function, vtxdata, should reference a pointer, that points to search (key)data. After the call - this (external) data pointer referenced by parameter vtxdata, has been redirected to point to data of the removed node - if the call was succesful. The caller is responsible for the future of this memory - deallocating it, if needed, for example.

For successful removal there are 2 preconditions to be met by the target vertex. The vertex to be removed must be isolated - which implies the following:

• The vertex specified with parameter vtxdata must not have any edges incident to it - i.e. it must not be part of any adjacency list in the graph, whatsoever.
• Moreover, this vertex must not have any edges incident from it - i.e. its own adjacency list must be empty.

Under these circumstances, the vertex specified with parameter vtxdata is isolated (edge-free). Now it can be removed - and accessed by the redirected, external pointer, that was manipulated by parameter vtxdata.

Parameters

[in]	graph	- a reference to current graph.
[in,out]	vtxdata	- reference to (external) pointer, that prior to call should point to vertex search (key) data. After the call, this external pointer is redirected to reference removed vertex data.

Returns

Value 0 - it the removal was successful
Value -2 - if vertex referenced by vtxdata is missing
Value -3 - if the vertex referenced by vtxdata is not isolated - i.e. this vertex has edges, incident from - and/or - to it.
Value -1 - otherwise, indicating some other (maybe fatal) error.

See Also

GRAPHinsvertex(), GRAPHis_isolated()

Definition at line 162 of file graph.c.

void GRAPHtraverse	(	Graph	graph,
		void(*)(const void *data)	vtxcallback,
		void(*)(const void *data)	edgecallback
	)

Traverse all vertices/edges of the graph

Parameters

[in]	graph	- a reference to current graph.
[in]	vtxcallback	- reference to user-defined callback function, that gets read access to vertex data via its parameter vtxcallback - to do whatever is relevant.
[in]	edgecallback	- reference to user-defined callback function, that gets read access to edge data via its parameter edgecallback - to do whatever is relevant.

Returns

Nothing.

Definition at line 247 of file graph.c.

int GRAPHvcount

(

Graph

graph

)

Get total number of vertices

Parameters

[in]

graph

- a reference to current graph.

Returns

The total number of vertices contained in graph.

Definition at line 295 of file graph.c.