Python graph data structure implementation

Python graph data structure implementation

Python is a popular programming language for creating various types of graphs. Here are some ways to implement a graph data structure using Python:

    class Graph:
def init(self):
self.adjMat = None
def addEdge(self, v1, v2):
if not self.adjMat:
numVertices = len(v1)
self.adjMat = [[0 for row in range(numVertices)]
for col in range(numVertices)]
self.adjMat[v1][v2] = 1
self.adjMat[v2][v1] = 1
def displayGraph(self):
if not self.adjMat:
return
numVertices = len(self.adjMat)
for i in range(numVertices):
print('Adjacency matrix:', end=' ')
for j in range(numVertices):
print(f' {self.adjMat[i][j]}', end=' ')
print()

    class Graph:
def init(self):
self.adjList = {}
def addEdge(self, v1, v2):
if v1 not in self.adjList:
self.adjList[v1] = []
if v2 not in self.adjList:
self.adjList[v2] = []
self.adjList[v1].append(v2)
self.adjList[v2].append(v1)
def displayGraph(self):
for vertex, edges in self.adjList.items():
print(f'Vertex {vertex}: {edges}')

    class Graph:
def init(self):
self.edges = []
def addEdge(self, v1, v2):
self.edges.append((v1, v2))
def displayGraph(self):
for edge in self.edges:
print(f'Edge {edge[0]}-{edge[1]}')

    class DirectedGraph:
def init(self):
self.adjList = {}
def addEdge(self, v1, v2):
if v1 not in self.adjList:
self.adjList[v1] = []
self.adjList[v1].append(v2)
def displayGraph(self):
for vertex, edges in self.adjList.items():
print(f'Vertex {vertex}: {edges}')

    class UndirectedGraph:
def init(self):
self.adjList = {}
def addEdge(self, v1, v2):
if v1 not in self.adjList:
self.adjList[v1] = []
if v2 not in self.adjList:
self.adjList[v2] = []
self.adjList[v1].append(v2)
self.adjList[v2].append(v1)
def displayGraph(self):
for vertex, edges in self.adjList.items():
print(f'Vertex {vertex}: {edges}')

Remember that these are just some basic implementations and there are many variations depending on your specific needs.

How do you represent a graph in Python?

Representing graphs in Python can be achieved using various libraries and data structures. Here are some popular methods:

    import numpy as np
from scipy.sparse import csr_matrix
Define nodes and edges
nodes = [0, 1, 2]
edges = [(0, 1), (1, 2)]
Create adjacency matrix
adj_matrix = np.zeros((len(nodes), len(nodes)), dtype=int)
for edge in edges:
i, j = edge
adj_matrix[i][j] = 1
Convert to scipy sparse matrix
adj_matrix = csr_matrix(adj_matrix)
print("Adjacency Matrix:")
print(adj_matrix.todense())

    nodes = [0, 1, 2]
edges = [(0, 1), (1, 2), (2, 0)]
print("Edges:")
for edge in edges:
print(edge)

    nodes = [0, 1, 2]
graph = {i: [] for i in nodes}
for edge in edges:
i, j = edge
graph[i].append(j)
print("Adjacency List:")
for node, neighbors in graph.items():
print(f"Node {node} is connected to: {[str(n) for n in neighbors]}")

        import networkx as nx
Create a directed graph
G = nx.DiGraph()
Add nodes and edges to the graph
G.add_node("A")
G.add_node("B")
G.add_edge("A", "B")
print("NetworkX Graph:")
print(G.edges())

    import igraph as ig
Create a directed graph
G = ig.Graph()
G.add_vertices(3)
G.add_edges([(0, 1), (1, 2)])
print("Directed Graph:")
for edge in G.get_edgelist():
print(edge)
Create an undirected graph
G = ig.Graph()
G.add_vertices(3)
G.add_edges([(0, 1), (1, 2)])
print("Undirected Graph:")
for edge in G.get_edgelist():
print(edge)

These are some of the ways you can represent a graph in Python. The choice depends on your specific use case and personal preference.

References: