my net house

WAHEGURU….!

Graph-Algorithms in Python Part-1

Things required in Graph-Base-Class:

  1. Number of vertices.
  2. Graph Type-(Directed or un-directed)
  3. Method to add Edges
  4. Method to find adjacent Vertices.
  5. Method to Get InDegree
  6. Method to Get Edge Weight
  7. method to Display the Graph

Graph code Link here:

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().

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: