graph.c File Reference

Contains definitions of routines supported by graph. More...

#include "graph.h"
#include "link_list.h"
#include "queue.h"
#include "stack.h"
#include "heap.h"
#include "disjoint_set.h"
#include "array.h"

Go to the source code of this file.

Functions
t_gen	graph_delete (t_gen, t_gen)
t_gen	graph_find (t_gen d, t_gen data)
	Find a Vertex(node) in graph; More...
int	graph_len (t_gen g)
	get num Vertex(nodes) in graph; More...
t_gen	graph_add_vertex (t_gen d, t_gen data)
	Add a Vertex(node) in graph; More...
t_gen	graph_has_edge (t_gen d, t_gen n1, t_gen n2)
	Check edge between two Vertices(nodes) in graph; More...
t_gen	graph_add_edge (t_gen d, t_gen n1, t_gen n2)
	Add an asymmetric edge between two vertices(nodes) in graph; More...
t_gen	graph_del_edge (t_gen d, t_gen n1, t_gen n2)
	Del an asymmetric edge between two vertices(nodes) in graph; More...
t_gen	graph_add_edge_sym (t_gen d, t_gen n1, t_gen n2)
	Add a symmetric edge between two vertices(nodes) in graph; More...
t_gen	graph_del_edge_sym (t_gen d, t_gen n1, t_gen n2)
	Del a symmetric edge between two vertices(nodes) in graph; More...
t_gen	graph_del_vertex (t_gen d, t_gen n1)
	Del a vertex(node) in graph; More...
t_gen	graph_add_wedge (t_gen d, t_gen n1, t_gen n2, int weight)
	Add an asymmetric weighted edge between two vertices(nodes) in graph; More...
t_gen	graph_add_wedge_sym (t_gen d, t_gen n1, t_gen n2, int weight)
	Add a symmetric weighted edge between two vertices(nodes) in graph; More...
t_gen	graph_bfs (t_gen d, t_gen n)
	Breath First Search BFS info Contains More...
t_gen	graph_dfs (t_gen d, t_gen n)
	Depth First Search DFS info contains More...
t_gen	graph_toplogicaly_order_dag (t_gen d)
	Topologicaly order/Topologicaly sort the nodes of a DAG And get the longest path to each of the vertices in DAG The topologicaly order nodes instead of being printed can be pushed to link list and return. More...
void	graph_neigh_print (t_gen d, t_gen neigh)
	Util function to Print neighbor list of a vetex(node) More...
void	graph_print (t_gen d)
	Print Graph info More...
void	graph_wprint (t_gen d)
	Print Graph info with edge weights More...
void	graph_destroy (t_gen d)
	Destroy instance of graph More...
t_gen	create_graph (char *name, int size, t_dparams *prm)
	Create an instance of graph More...
e_cmpr	graph_neigh_list_compare (t_gen x, t_gen y)
	Util compare function for neigh link list node data More...
void	graph_neigh_list_free (t_gen mem, char *file, int line)
	Util free function for deleting neigh link list node data More...
void	bfs_core (t_graph *g, t_gnode *node, t_bfsinfo *bfs, t_queue *q, int comp)
	Breath First Search Core routine This routine does bfs on all conncted components More...
void	dfs_core (t_graph *g, t_gnode *node, t_dfsinfo *dfs, t_stack *s, int comp, int *gcount)
	Depth First Search Core routine This routine does dfs on all conncted components More...
t_gen	graph_dfs_optimised (t_gen d, t_gen n)
	Depth First Search Optimised by eliminating the need for revisiting a previously visited vetex in neighbor list. Note: These visits happen only during the scanning of neighbor list to get an unvisited node More...
void	graph_wneigh_print (t_gen d, t_gen neigh)
	Util function to Print neighbor list of a vetex(node) with edge weights More...
e_cmpr	graph_wedge_cmpr (t_gen x, t_gen y)
	Utils function used for comparing two different graph edges More...
e_cmpr	graph_wedge_cmpr_idx (t_gen x, int i, int j)
	Utils function used by genric heap for comparing graph edge weights More...
e_cmpr	graph_wedge_cmpr_idx2 (t_gen x, int i, int j)
	Utils function used by quick sort for comparing graph edge weights 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 definitions of routines supported by graph.

Author

Meraj

Definition in file graph.c.

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.

bfs_core()

void bfs_core	(	t_graph *	g,
		t_gnode *	node,
		t_bfsinfo *	bfs,
		t_queue *	q,
		int	comp
	)

Breath First Search Core routine This routine does bfs on all conncted components

Parameters

g	- Pointer instance of graph
d	- Pointer to Source node from where to start BFS
bfs	- Pointer to bfs info of each vertex
q	- Pointer to queue used for BFS
comp	- Component of the graph

Returns

- NA

Definition at line 435 of file graph.c.

create_graph()

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

Create an instance of graph

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.

dfs_core()

void dfs_core	(	t_graph *	g,
		t_gnode *	node,
		t_dfsinfo *	dfs,
		t_stack *	s,
		int	comp,
		int *	gcount
	)

Depth First Search Core routine This routine does dfs on all conncted components

Parameters

g	- Pointer instance of graph
d	- Pointer to Source node from where to start DFS
dfs	- Pointer to dfs info of each vertex
s	- Pointer to stack used for DFS
comp	- Component of the graph
gcount	- Pointer to count value that used to store pre/post(arrival/depature) of a vertex

Returns

- NA

Definition at line 550 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.

graph_add_edge()

t_gen graph_add_edge	(	t_gen	d,
		t_gen	n1,
		t_gen	n2
	)

Add an asymmetric edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2

Returns

- Pointer to Vertex(node) else null

Definition at line 219 of file graph.c.

graph_add_edge_sym()

t_gen graph_add_edge_sym	(	t_gen	d,
		t_gen	n1,
		t_gen	n2
	)

Add a symmetric edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2

Returns

- Pointer to Vertex(node) else null

Definition at line 324 of file graph.c.

graph_add_vertex()

t_gen graph_add_vertex	(	t_gen	d,
		t_gen	data
	)

Add a Vertex(node) in graph;

Parameters

d	- Pointer instance of graph
data	- Pointer to data

Returns

- Pointer to Vertex(node) else null

Definition at line 153 of file graph.c.

graph_add_wedge()

t_gen graph_add_wedge	(	t_gen	d,
		t_gen	n1,
		t_gen	n2,
		int	weight
	)

Add an asymmetric weighted edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2
weight	- Edge weight

Returns

- Pointer to Vertex(node) else null

Definition at line 259 of file graph.c.

graph_add_wedge_sym()

t_gen graph_add_wedge_sym	(	t_gen	d,
		t_gen	n1,
		t_gen	n2,
		int	weight
	)

Add a symmetric weighted edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2
weight	- Edge weight

Returns

- Pointer to Vertex(node) else null

Definition at line 345 of file graph.c.

graph_bfs()

t_gen graph_bfs	(	t_gen	d,
		t_gen	n
	)

Breath First Search BFS info Contains

• Level of the vertex from Source node
  • Parent node of a vertex
  • Component of the graph that the a vertex belongs to

    Parameters

    d	- Pointer instance of graph
    n	- Pointer to data1 (Source node from where to start BFS)

    Returns

    - Pointer to BFS info if node present else null

Definition at line 485 of file graph.c.

graph_del_edge()

t_gen graph_del_edge	(	t_gen	d,
		t_gen	n1,
		t_gen	n2
	)

Del an asymmetric edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2

Returns

- Pointer to Vertex(node) else null

Definition at line 298 of file graph.c.

graph_del_edge_sym()

t_gen graph_del_edge_sym	(	t_gen	d,
		t_gen	n1,
		t_gen	n2
	)

Del a symmetric edge between two vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2

Returns

- Pointer to Vertex(node) else null

Definition at line 365 of file graph.c.

graph_del_vertex()

t_gen graph_del_vertex	(	t_gen	d,
		t_gen	n1
	)

Del a vertex(node) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1

Returns

- Pointer to Vertex(node) else null

Definition at line 384 of file graph.c.

graph_delete()

t_gen graph_delete	(	t_gen	,
		t_gen
	)

graph_destroy()

void graph_destroy

(

t_gen

d

)

Destroy instance of graph

Parameters

d	- Pointer instance of graph

Returns

- NA

Definition at line 1368 of file graph.c.

graph_dfs()

t_gen graph_dfs	(	t_gen	d,
		t_gen	n
	)

Depth First Search DFS info contains

• pre/post(arrival/depature) intervals of a vertex
  • Parent node of a vertex
  • Component of the graph that the a vertex belongs to

    Parameters

    d	- Pointer instance of graph
    n	- Pointer to data1 (Source node from where to start DFS)

    Returns

    - Pointer to DFS info of all nodes if node present else null

Definition at line 622 of file graph.c.

graph_dfs_optimised()

t_gen graph_dfs_optimised	(	t_gen	d,
		t_gen	n
	)

Depth First Search Optimised by eliminating the need for revisiting a previously visited vetex in neighbor list. Note: These visits happen only during the scanning of neighbor list to get an unvisited node

Parameters

d	- Pointer instance of graph
n	- Pointer to data1 (Source node from where to start DFS)

Returns

- Pointer to DFS info if node present else null

Definition at line 685 of file graph.c.

graph_find()

t_gen graph_find	(	t_gen	d,
		t_gen	data
	)

Find a Vertex(node) in graph;

Parameters

d	- Pointer instance of graph
data	- Pointer to data

Returns

- Pointer to Vertex(node) containing data else null

Definition at line 98 of file graph.c.

graph_has_edge()

t_gen graph_has_edge	(	t_gen	d,
		t_gen	n1,
		t_gen	n2
	)

Check edge between two Vertices(nodes) in graph;

Parameters

d	- Pointer instance of graph
n1	- Pointer to data1
n2	- Pointer to data2

Returns

- Pointer to Vertex(node) else null

Definition at line 195 of file graph.c.

graph_len()

int graph_len

(

t_gen

g

)

get num Vertex(nodes) in graph;

Parameters

d	- Pointer instance of graph

Returns

- Vertex(node) Count

Definition at line 87 of file graph.c.

graph_neigh_list_compare()

e_cmpr graph_neigh_list_compare	(	t_gen	x,
		t_gen	y
	)

Util compare function for neigh link list node data

Parameters

x	- Pointer linklist node
y	- Pointer to data to be compared

Returns

- Equal, Less or Great

Definition at line 118 of file graph.c.

graph_neigh_list_free()

void graph_neigh_list_free	(	t_gen	mem,
		char *	file,
		int	line
	)

Util free function for deleting neigh link list node data

Parameters

mem	- Pointer to memory
file	- File name
line	- line number

Returns

- NA

Definition at line 137 of file graph.c.

graph_neigh_print()

void graph_neigh_print	(	t_gen	d,
		t_gen	neigh
	)

Util function to Print neighbor list of a vetex(node)

Parameters

d	- Pointer instance of graph
neigh	- Pointer to neigh link list

Returns

- NA

Definition at line 880 of file graph.c.

graph_print()

void graph_print

(

t_gen

d

)

Print Graph info

Parameters

d	- Pointer instance of graph

Returns

- NA

Definition at line 908 of file graph.c.

graph_toplogicaly_order_dag()

t_gen graph_toplogicaly_order_dag

(

t_gen

d

)

Topologicaly order/Topologicaly sort the nodes of a DAG And get the longest path to each of the vertices in DAG The topologicaly order nodes instead of being printed can be pushed to link list and return.

Parameters

d	- Pointer instance of graph

Returns

- DAG info struct containg longest path and vertices in topological order

Definition at line 789 of file graph.c.

graph_wedge_cmpr()

e_cmpr graph_wedge_cmpr	(	t_gen	x,
		t_gen	y
	)

Utils function used for comparing two different graph edges

Parameters

x	- Pointer to edge1
y	- Pointer to edge2

Returns

- Comparision resutlt

See also

e_cmpr

Definition at line 980 of file graph.c.

graph_wedge_cmpr_idx()

e_cmpr graph_wedge_cmpr_idx	(	t_gen	x,
		int	i,
		int	j
	)

Utils function used by genric heap for comparing graph edge weights

Parameters

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

Returns

- Comparision resutlt

See also

e_cmpr

Definition at line 1004 of file graph.c.

graph_wedge_cmpr_idx2()

e_cmpr graph_wedge_cmpr_idx2	(	t_gen	x,
		int	i,
		int	j
	)

Utils function used by quick sort for comparing graph edge weights

Parameters

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

Returns

- Comparision resutlt

See also

e_cmpr

Definition at line 1018 of file graph.c.

graph_wneigh_print()

void graph_wneigh_print	(	t_gen	d,
		t_gen	neigh
	)

Util function to Print neighbor list of a vetex(node) with edge weights

Parameters

d	- Pointer instance of graph
neigh	- Pointer to neigh link list

Returns

- NA

Definition at line 929 of file graph.c.

graph_wprint()

void graph_wprint

(

t_gen

d

)

Print Graph info with edge weights

Parameters

d	- Pointer instance of graph

Returns

- NA

Definition at line 959 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.