# my net house

WAHEGURU….!

## Graph-Algorithms in Python Part-1

November 25, 2020

Posted by on Things required in Graph-Base-Class:

- Number of vertices.
- Graph Type-(Directed or un-directed)
- Method to add Edges
- Method to find adjacent Vertices.
- Method to Get InDegree
- Method to Get Edge Weight
- method to Display the Graph

https://github.com/arshpreetsingh/GraphAlgos/blob/master/graph.py#L11

Adjacency Set: Use the folowing image to learn about Adjacency-Set.

Node:

A single node in a graph represented by an adjacency set. Every node

has a vertex id, Each node is associated with a set of adjacent vertices

Link for Node Code here: https://github.com/arshpreetsingh/GraphAlgos/blob/master/graph.py#L45

**AdjacencyGraph:**

Represents a graph as an adjacency set. A graph is a list of Nodes

and each Node has a set of adjacent vertices.

This graph in this current form cannot be used to represent

weighted edges only unweighted edges can be represented

Inherit from Graph Class,

Number of vertices—Graph Type

1. Add multiple-Nodes in the init() method of the class.

2. Method to add vertices/Edges with some Checks(vertex should not be equal to zero and Vertices value should not be more than nuber of vertices )

```
if v1 >= self.numVertices or v2 >= self.numVertices or v1 < 0 or v2 < 0:
raise ValueError("Vertices %d and %d are out of bounds" % (v1, v2))
```

3. Get Adjacent Vertex.

**For specific Location on Vertex List get adjacent value. **

`self.vertex_list[v].get_adjacent_vertices()`

4. Get Iindegree of Vertex.

Find all the vertices which are connected with specifc vertex.

```
indegree = 0
for i in range(self.numVertices):
if v in self.get_adjacent_vertices(i):
indegree = indegree + 1
return indegree
```

5. Display a Graph:

iterate through list of vertices(self.vertex_list) after that iterate through each Node in the list to get_adjacent_verices!

```
def display(self):
for i in range(self.numVertices):
for v in self.get_adjacent_vertices(i):
print(i, "-->", v)
```

https://github.com/arshpreetsingh/GraphAlgos/blob/master/graph.py#L68

**AdjacencyMatrixGraph:**

Represents a graph as an adjacency matrix. A cell in the matrix has

a value when there exists an edge between the vertex represented by

the row and column numbers.

Weighted graphs can hold values > 1 in the matrix cells

A value of 0 in the cell indicates that there is no edge

Rest of the methods will be Same as AdjacencyGraph. All operaitions will be replaced by matrix operarions insted of set().