graph.h File Reference

Interface for creating graph. More...

#include <stdio.h>
#include <stdbool.h>

Go to the source code of this file.

Data Structures
struct	edge
	Representation of an edge. More...

Typedefs
typedef struct node	Node
	Node is an opaque type. More...
typedef struct graph	Graph
	Graph is an opaque type. More...

Functions
unsigned int	node_get_id (Node *n)
	Get id of a node. More...
unsigned short	node_get_n_outgoing (Node *n)
	Get number of outgoing edges from a node. More...
struct edge *	node_get_edges (Node *n)
	Get array of outgoing edges. More...
unsigned int	node_get_distance (Node *n)
	Get distance of this node from starting node. More...
Node *	node_get_previous (Node *n)
	Get node on (already found) shortest path from which queried node was visited. More...
Graph *	graph_new (void)
	Create a new graph. More...
bool	graph_insert_node (Graph *g, unsigned int id)
	Insert node into the graph. More...
bool	graph_insert_edge (Graph *g, unsigned int source, unsigned int dest, int mindelay)
	Insert an edge into the graph. More...
Node *	graph_get_node (Graph *g, unsigned int id)
	Retrieve a node. More...
void	graph_free (Graph *g)
	Free memory used by nodes and edges. More...

Detailed Description

Interface for creating graph.

This file declares functions and types for creating graphs.

Author

Lubomir Sedlar

Definition in file graph.h.

Typedef Documentation

typedef struct graph Graph

Graph is an opaque type.

To work with it, use provided functions, but do not try to access its members directly.

Definition at line 25 of file graph.h.

typedef struct node Node

Node is an opaque type.

You can have a pointer to it, but the only thing you can do with that pointer is pass it given functions.

Definition at line 19 of file graph.h.

Function Documentation

void graph_free

(

Graph *

g

)

Free memory used by nodes and edges.

Parameters

g	graph to be freed

Definition at line 176 of file graph.c.

Node* graph_get_node	(	Graph *	g,
		unsigned int	id
	)

Retrieve a node.

This function performs binary search, therefore needs the nodes to be sorted. Sorting is done automatically if necessary. Inserting a node will break the sorted property, so first node retrieval after insertion is going to be slow.

Parameters

g	graph to be searched
id	identifier of the node

Returns

pointer to node or NULL if such node does not exist

Definition at line 132 of file graph.c.

bool graph_insert_edge	(	Graph *	g,
		unsigned int	source,
		unsigned int	dest,
		int	mindelay
	)

Insert an edge into the graph.

Both nodes need to be present in the graph, otherwise the function will fail. Other reason of failure is malloc failure.

Parameters

g	graph to insert into
source	starting node of the edge
dest	ending node of the edge
mindelay	minimum delay on this edge

Returns

true if successful, false otherwise

Definition at line 103 of file graph.c.

bool graph_insert_node	(	Graph *	g,
		unsigned int	id
	)

Insert node into the graph.

This function fails only if memory runs out.

Parameters

g	graph to insert into
id	identifier of the new node

Returns

true if successful, false otherwise

Definition at line 75 of file graph.c.

Graph* graph_new

(

void

)

Create a new graph.

Returns

new graph or NULL if memory is exhausted

Definition at line 60 of file graph.c.

unsigned int node_get_distance

(

Node *

n

)

Get distance of this node from starting node.

Infinity is signalled by UINT_MAX.

Parameters

n	node to query

Returns

total distance

Definition at line 43 of file graph.c.

struct edge* node_get_edges

(

Node *

n

)

Get array of outgoing edges.

The number of elements in this array is returned by node_get_n_outgoing().

Parameters

n	node to query

Returns

array of outgoing edges

Definition at line 37 of file graph.c.

unsigned int node_get_id

(

Node *

n

)

Get id of a node.

Parameters

n	node to query

Returns

node id

Definition at line 25 of file graph.c.

unsigned short node_get_n_outgoing

(

Node *

n

)

Get number of outgoing edges from a node.

Parameters

n	node to query

Returns

number of outgoing edges

Definition at line 31 of file graph.c.

Node* node_get_previous

(

Node *

n

)

Get node on (already found) shortest path from which queried node was visited.

For starting and unreachable nodes this function returns NULL.

Parameters

n	node to query

Returns

previous node or NULL

Definition at line 49 of file graph.c.