Skip to content

Instantly share code, notes, and snippets.

@achingachris
Created April 17, 2023 20:58
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save achingachris/18ceecdc4a3a156afaf811f4d29c31b2 to your computer and use it in GitHub Desktop.
import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
self.nx_graph = nx.DiGraph()
def add_edge(self, u, v):
self.graph[u].append(v)
self.nx_graph.add_edge(u, v)
def draw_graph(self, layout='circular'):
if layout == 'circular':
pos = nx.circular_layout(self.nx_graph)
elif layout == 'kamada_kawai':
pos = nx.kamada_kawai_layout(self.nx_graph)
elif layout == 'spring':
pos = nx.spring_layout(self.nx_graph)
else:
raise ValueError("Invalid layout parameter. Choose from 'circular', 'kamada_kawai', or 'spring'.")
nx.draw(self.nx_graph, pos, with_labels=True, node_color='lightblue', font_weight='bold', arrows=True, node_size=2000)
plt.show()
def dfs(self, v, visited, stack):
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
self.dfs(i, visited, stack)
stack.append(v)
def topological_sort(self):
visited = [False] * self.V
stack = []
for i in range(self.V):
if not visited[i]:
self.dfs(i, visited, stack)
return stack[::-1]
# Test the implementation
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
print("Graph Visualization (Circular layout):")
g.draw_graph(layout='circular')
print("Graph Visualization (Kamada-Kawai layout):")
g.draw_graph(layout='kamada_kawai')
print("Graph Visualization (Spring layout):")
g.draw_graph(layout='spring')
print("\nTopological Sort:")
print(g.topological_sort())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment