Graphs

Quick Start Guide

# import required data structures
>>> from pythorn.data_structures.graphs import AdjanceyList

# pass number of nodes
>>> a = AdjanceyList(5)

# add edge with source node and destination node
>>> a.add_edge(0,1)
>>> a.add_edge(0,3)
>>> a.add_edge(4,3)
>>> a.add_edge(2,4)

# printing Adjancey List
>>> a.print_list()
node 1 -> 5
node 2 -> 4
node 3 -> 0 4
node 4 -> 3 2
node 5 -> 5 3

Graph Programs

Author : Robin Singh

Programs List : 1 . Adjancey List with Node Class 2 . Adjancey Matrix 3 . Breath First Search 4 . Depth First Search 5 . Topological Sort

Adjancey List

class pythorn.data_structures.graphs.AdjanceyList(number_of_nodes)

Adjancey list implementation

create_nodes()

function for creating nodes

last_node(first_node)

function for getting the last node

add_edge(node1, node2)

function for adding new edges

Parameters

• node1 – from vertex (source)

• node2 – to vertex (destination)

print_adjancey(node, node_No)

Prints

prints adjancey list for a specific node

print_list()

function for printing all the node’s adjancey list

static get_code()

Returns

source code

static time_complexity()

Returns

time complexity

Adjancey Matrix

Example :

>>> from pythorn.data_structures.graphs import AdjanceyMatrix
>>> a = AdjanceyMatrix(5)
>>> a.add_edge(1,5)
>>> a.add_edge(1,4)
>>> a.add_edge(2,4)
>>> a.add_edge(3,4)
>>> a.add_edge(3,2)
>>> a.add_edge(3,1)
>>> a.print_matrix()
[0, 0, 1, 1, 1]
[0, 0, 1, 1, 0]
[1, 1, 0, 1, 0]
[1, 1, 1, 0, 0]
[1, 0, 0, 0, 0]
[1, 0, 0, 0, 0]

class pythorn.data_structures.graphs.AdjanceyMatrix(no_of_verices)

Adjancey Matrix Implementation

make_matrix()

function for making matrix of NxN. where n is the number of vertices

add_edge(node1, node2)

function for adding an edge

Parameters

• node1 – vertex 1 (source)

• node2 – vertex 2 (destination)

print_matrix()

function for printing the matrix

static get_code()

Returns

source code

static time_complexity()

Returns

time complexity

BFS

Example :

# import required algorithm
>>> from pythorn.data_structures.graphs import BFS

# create graph
>>> graph={  0: [1, 3,4],
...             1: [2],
...             2: [3],
...             3: [1,4],
...             4: [0,2] }

# pass graph and value 0 as argument
>>> bfs1 = BFS(graph,0)

# call bfs main function
>>> z = bfs1.bfs()

>>> print(z)
[0, 1, 3, 4, 2]

class pythorn.data_structures.graphs.BFS(graph, start)

BFS implementation with adjancey list

bfs()

Returns

BFS path

static get_code()

Returns

source code

static time_complexity()

Returns

time complexity

DFS

Example :

# import required algorithm
>>> from package.pygostructures.data_structures.graphs import DFS

# create graph
>>> graph1 = {
...             0: [1, 3,4],
...             1: [2],
...             2: [3],
...             3: [1,4],
...             4: [0,2]}

# pass graph and start vertex as argument
>>> dfs1 = DFS(graph1,2)

# call the function
>>> z = dfs1.dfs()

>>> print(z)
[2, 3, 1, 4, 0]

class pythorn.data_structures.graphs.DFS(graph, start, path=[])

DFS implementation with adjancey list

dfs()

Returns

DFS path

static get_code()

Returns

source code

static time_complexity()

Returns

time complexity

Topological Sort

Example :

# import required algorithm
>>> from package.pygostructures.data_structures.graphs import *

# pass number of vertices as argument
>>> a = TopologicalSort(5)

# adding edge with source and destination vertex
>>> a.add_edge(0,3)
>>> a.add_edge(0,4)
>>> a.add_edge(0,3)
>>> a.add_edge(2,3)
>>> a.add_edge(2,1)
>>> a.add_edge(2,4)


# printing list
>>> a.print_list()
0 Vertex :  ->  3 -> 4 -> 3
3 Vertex :  ->
2 Vertex :  ->  3 -> 1 -> 4

# call main function
>>> a.topological_Sort()
2--> 0--> 3

class pythorn.data_structures.graphs.TopologicalSort(vertices)

Topological Sort Implementation

print_list()

function for printing graph

add_edge(node1, node2)

Parameters

• node1 – from vertex (source)

• node2 – to vertex (destination)

static get_code()

Returns

source code

static time_complexity()

Returns

time complexity