Modeling Graphs in DSA
Advanced data structures called graphs are used to model the interactions between pairs of things and arrange related items in a network. This idea of a “graph” should not be confused with function plots or bar charts.
Vertices and Edges
Vertices and Edges The formal definition of a graph G is a collection E of pairs of vertices from V (also known as edges) and a set of V vertices (also known as nodes). In a data structure, vertices are common records that represent entities such as files, departments, files, or individuals. Nodes are objects in object-oriented programming that represent actual entities. These entities’ relationships are defined by their edges.
Undirected or directed edges. V gets an edge (u,v) if u comes first. When (u,v) = (v,u) and the pair is unordered, undirected edges occur. Only directed edges make up directed graphs, also known as digraphs. There are both directed and undirected edges in mixed graphs. A graph without self-loops (an edge connecting a vertex to itself) or parallel edges (many edges connecting the same two vertices) is said to be simple. It’s common to presume that graphs are basic unless otherwise noted.
An edge’s endpoints are the two vertices that it connects. The first endpoint is the directed edge’s origin, and the second is its destination. An edge connecting two vertices, u and v, indicates that they are adjacent. A vertex is considered incident to an edge if it is one of its endpoints. The number of incident edges is the degree of a vertex v, or deg(v). In a directed graph, the numbers of entering and outgoing edges are denoted by indeg(v) and outdeg(v), respectively.
Modeling Graphs: Adjacency List vs. Adjacency Matrix
Modelling Graphs Comparing Adjacency Matrix with Adjacency List A program’s ability to display a graph effectively is essential. The adjacency list (or its derivative, the adjacency map) and the adjacency matrix are two popular data structures for this.
Adjacency Matrix Organisation: A two-dimensional n × n array, A, with n being the number of vertices, is used to represent a graph in the adjacency matrix. Vertices usually denote numbers between 0 and n-1. If the edge (u,v) exists, the cell A[i, j] references it. A[i, j] is None without such an edge. As a symmetric undirected graph matrix, A[i, j] = A[j, i].
Accessing any edge (u,v) in worst-case O(1) time is an adjacency matrix’s main benefit. One bit may be used per edge slot in a Boolean adjacency matrix if edges lack auxiliary data, indicating that A[i, j] = True if (u,v) is an edge. Cons: Usually utilising O(n^2) space, adjacency matrices are inefficient for sparse graphs (graphs with a much less number of edges than n^2 possibilities). Finding all incident edges to a vertex is one example of an operation that takes O(n) time because it involves looking at all n entries in a row. Since the entire matrix needs to be adjusted, adding or removing vertices is also challenging.
Adjacency List Structure: The Structure of Adjacency Lists On the other hand, the adjacency list structure associates edges with specific vertices in smaller, secondary containers, so grouping them. An incidence collection I(v) holds the edges incident to each vertex v. Iout(v) and Iin(v), two distinct collections, can be used to record incoming and outgoing edges for directed graphs.
When n is the number of vertices and m is the number of edges, the space needed for an adjacency list is O(n + m). This is more effective for sparse graphs than an adjacency matrix. Vertex v’s incident edges can be iterated through in O(deg(v)) time, which is ideal for reporting those edges. Cons: Searching across I(u) or I(v) is necessary to find a specific edge (u,v), which takes O(min(deg(u), deg(v)) time.
Adjacency Map (Python Implementation): Adjacency Map An adjacency map, a variation of the adjacency list, is used in a popular Python implementation of graph modelling. A Python dictionary represents the incidence map I(v) for every vertex v. In this map, the edge structure is the value and the opposing endpoint of an incident edge is the key. For every vertex v, a top-level dictionary D maps it to its incidence map I(v). Because iteration can be accomplished by mixing edges from incidence maps or by creating keys of D, this method avoids explicitly storing lists of all vertices and edges.
Finding u as a key in I(v) (or vice versa) allows the get edge(u,v) method to be implemented in predicted O(1) time, which is the main benefit of the adjacency map over a simple adjacency list. For graph representation, it is a great all-purpose option because it delivers nearly optimal execution times for the majority of techniques.
An example of Python code A Graph class implementation with nested Vertex and Edge classes that makes use of the adjacency map structure is shown in the Python code below:
Example:
class GraphAdjList:
def __init__(self):
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list:
self.adj_list[vertex] = []
def add_edge(self, u, v):
"""Add an edge from u to v."""
if u not in self.adj_list:
self.add_vertex(u)
if v not in self.adj_list:
self.add_vertex(v)
self.adj_list[u].append(v)
def display(self):
for vertex, neighbors in self.adj_list.items():
print(f"{vertex}: {neighbors}")
# Example
graph = GraphAdjList()
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "E")
graph.display()Output:
A: ['B', 'C']
B: ['D']
C: ['E']
D: []
E: []In this Python version, the graph structure is represented using dictionaries. With destination vertices as the keys and Edge objects as the values, outgoing translates each vertex v to a dictionary that contains its outgoing edges. In directed graphs, incoming maps vertices to their incoming edges in a similar manner. Incoming and outgoing aliases are used in undirected graphs to prevent redundant storage.
An essential component of the adjacency map implementation is the ability to utilise these objects as keys in Python’s hash-based sets and dictionaries, which is made possible by the hash methods in the Vertex and Edge classes. On the basis of this dictionary structure, functions such as vertex count(), edges(), obtain edge(), degree(), incident edges(), insert vertex(), and insert edge() are built. It is used to implement methods such as vertex count(), edges(), obtain edge(), degree(), incident edges(), insert vertex(), and insert edge().