graph.h File Reference

Contains declations of graph types, operations and structure. More...

#include "common.h"
#include "link_list.h"

Go to the source code of this file.

Data Structures
struct	gnode
	graph Vertex More...
struct	gedge
	graph neighbor edges represented in neigh list More...
struct	graph
	graph struct defn More...
struct	bfs_info
	Level and Parent info after BFS walk. More...
struct	dfs_info
	Level and Parent info after DFS walk. More...
struct	dag_info
	Longest Path and Node order after DAG ordering. More...
struct	dist_info
	Dist info. More...

Typedefs
typedef struct gnode	t_gnode
	graph Vertex More...
typedef struct gedge	t_gedge
	graph neighbor edges represented in neigh list More...
typedef t_gen(*	f_wedge) (t_gen, t_gen, t_gen, int)
typedef struct graph	t_graph
	graph struct defn More...
typedef struct bfs_info	t_bfsinfo
	Level and Parent info after BFS walk. More...
typedef struct dfs_info	t_dfsinfo
	Level and Parent info after DFS walk. More...
typedef struct dag_info	t_daginfo
	Longest Path and Node order after DAG ordering. More...
typedef struct dist_info	t_distinfo
	Dist info. More...

Functions
t_gen	create_graph (char *name, int size, t_dparams *prm)
	graph interface APIs More...
t_gen	dijkstra (t_gen d, t_gen data)
	Utils function used by quick sort for swapping graph edges More...
t_gen	bellman_ford (t_gen d, t_gen data)
	Find the shortest path from a given source vertex to all source nodes in a graph with negative edges this is an improvent of bellman ford using Shortest Path Faster Algorithm (SPFA) More...
t_gen	prims_mst (t_gen d)
	Find the Minimum Spanning for weighted undirected graph Using Prim's Algorithm More...
t_gen	kruskals_mst (t_gen d)
	Find the Minimum Spanning for weighted undirected graph Using Kruskal's Algorithm More...

Detailed Description

Contains declations of graph types, operations and structure.

Definition in file graph.h.

Typedef Documentation

f_wedge

typedef t_gen(* f_wedge) (t_gen, t_gen, t_gen, int)

Definition at line 23 of file graph.h.

t_bfsinfo

typedef struct bfs_info t_bfsinfo

Level and Parent info after BFS walk.

t_daginfo

typedef struct dag_info t_daginfo

Longest Path and Node order after DAG ordering.

t_dfsinfo

typedef struct dfs_info t_dfsinfo

Level and Parent info after DFS walk.

t_distinfo

typedef struct dist_info t_distinfo

Dist info.

t_gedge

typedef struct gedge t_gedge

graph neighbor edges represented in neigh list

t_gnode

typedef struct gnode t_gnode

graph Vertex

t_graph

typedef struct graph t_graph

graph struct defn

Function Documentation

bellman_ford()

t_gen bellman_ford	(	t_gen	d,
		t_gen	data
	)

Find the shortest path from a given source vertex to all source nodes in a graph with negative edges this is an improvent of bellman ford using Shortest Path Faster Algorithm (SPFA)

See also

https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm

Parameters

d	- Pointer instance of graph
data	- Pointer to source vertex data

Returns

- Pointer to dist array to all nodes in graph

Definition at line 1135 of file graph.c.

create_graph()

t_gen create_graph	(	char *	name,
		int	size,
		t_dparams *	prm
	)

graph interface APIs

graph interface APIs

Parameters

name	- Name of graph instance
size	- Max vertices in graph
prm	- Data type specific parameters

Returns

- Pointer to instance of graph

Definition at line 42 of file graph.c.

dijkstra()

t_gen dijkstra	(	t_gen	d,
		t_gen	data
	)

Utils function used by quick sort for swapping graph edges

Parameters

d	- Pointer to array
i	- index 1
j	- index 2

Returns

- NA

Find the shortest path from a given source vertex to all source nodes in a graph using Dijkstra's algo

See also

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Note: Dijktra's works for graph with no negative edges

Parameters

d	- Pointer instance of graph
data	- Pointer to source vertex data

Returns

- Pointer to dist array to all nodes in graph

Definition at line 1043 of file graph.c.

kruskals_mst()

t_gen kruskals_mst

(

t_gen

d

)

Find the Minimum Spanning for weighted undirected graph Using Kruskal's Algorithm

See also

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Parameters

d	- Pointer instance of graph

Returns

- Pointer to dist array to all nodes in graph

Definition at line 1295 of file graph.c.

prims_mst()

t_gen prims_mst

(

t_gen

d

)

Find the Minimum Spanning for weighted undirected graph Using Prim's Algorithm

See also

https://en.wikipedia.org/wiki/Prim%27s_algorithm

Parameters

d	- Pointer instance of graph

Returns

- Pointer to dist array to all nodes in graph

Definition at line 1217 of file graph.c.