Graph-Algorithms in Python Part-1
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
Adjacency Set: Use the folowing image to learn about Adjacency-Set.
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
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.
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)
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().