class Graph: def __init__(self, num_nodes): self.num_nodes = num_nodes # Initialize a 2D matrix with zeros self.adj_matrix = [[0] * num_nodes for _ in range(num_nodes)] def add_edge(self, node1, node2): # Add an undirected edge between node1 and node2 self.adj_matrix[node1][node2] = 1 self.adj_matrix[node2][node1] = 1 def remove_edge(self, node1, node2): # Remove the edge between node1 and node2 self.adj_matrix[node1][node2] = 0 self.adj_matrix[node2][node1] = 0 def num_edges(self): num_edges = 1 for i in range(self.num_nodes): for j in range(i+1, self.num_nodes): if self.adj_matrix[i][j] == 1: num_edges += 1 return num_edges def num_edges_in_set(self, node, subset): # count the number of edges joining the given node and nodes in subset. # example input: 1, {0, 2} num_edges = 0 for s in subset: if self.adj_matrix[node][s] == 1: num_edges += 1 return num_edges def edges_between_sets(self, setX, setY): # TODO: return the edges that have one end in setX, another end in setY pass def edge_cut(self, setX): # TODO: return the edge cut of a given subset of vertices pass def is_even(self): # TODO: return true is the graph is even, false otherwise pass def count_components(self): # return the number of components in graph. def dfs(node, visited): visited[node] = True for neighbor, is_edge in enumerate(self.adj_matrix[node]): if is_edge and not visited[neighbor]: dfs(neighbor, visited) visited = [False] * self.num_nodes num_components = 0 for node in range(self.num_nodes): if not visited[node]: # If the node hasn't been visited, it's a new component dfs(node, visited) num_components += 1 return num_components def is_connected(self): # TODO: return true is the graph is connected, false otherwise pass def is_bridge(self, edge): # TODO: return true if the given edge is an bridge, false otherwise # edge is given as a python pair. pass def is_adjacent(self, node1, node2): if self.adj_matrix[node1][node2] == 1: return True else: return False def print_graph(self): # Print the adjacency matrix for row in self.adj_matrix: print(" ".join(map(str, row))) if __name__ == "__main__": # use case test_graph = Graph(3) test_graph.add_edge(1,0) test_graph.add_edge(1, 2) print("Is even: ", test_graph.is_even()) x = {1} print("Edge cut is ", test_graph.edge_cut(x)) print("Is connected: ", test_graph.is_connected()) print("Is bridge: ", test_graph.is_bridge((1, 2))) from Graph import *import copy def Fleury(g, u): # TODO: implement Fleury's algorithm. # input: a graph and a vertex of the graph, # return: an array of vertices representing the Euler tour. # Return empty array if g is not even or not connected. if not g.is_even() or not g.is_connected(): return [] # Run the algorithm when g is even and connected W = [u] x = u F = copy.deepcopy(g) edge_cut = F.edge_cut({x}) current_edge = (-1, -1) pass # testtest_graph = Graph(5)test_graph.add_edge(0,3)test_graph.add_edge(0,2)test_graph.add_edge(1,3)test_graph.add_edge(1,2)test_graph.add_edge(2,3)test_graph.add_edge(2,4)test_graph.add_edge(3,4)print(Fleury(test_graph, 1))
class Graph:
def __init__(self, num_nodes):
self.num_nodes = num_nodes
# Initialize a 2D matrix with zeros
self.adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]
def add_edge(self, node1, node2):
# Add an undirected edge between node1 and node2
self.adj_matrix[node1][node2] = 1
self.adj_matrix[node2][node1] = 1
def remove_edge(self, node1, node2):
# Remove the edge between node1 and node2
self.adj_matrix[node1][node2] = 0
self.adj_matrix[node2][node1] = 0
def num_edges(self):
num_edges = 1
for i in range(self.num_nodes):
for j in range(i+1, self.num_nodes):
if self.adj_matrix[i][j] == 1:
num_edges += 1
return num_edges
def num_edges_in_set(self, node, subset):
# count the number of edges joining the given node and nodes in subset.
# example input: 1, {0, 2}
num_edges = 0
for s in subset:
if self.adj_matrix[node][s] == 1:
num_edges += 1
return num_edges
def edges_between_sets(self, setX, setY):
# TODO: return the edges that have one end in setX, another end in setY
pass
def edge_cut(self, setX):
# TODO: return the edge cut of a given subset of vertices
pass
def is_even(self):
# TODO: return true is the graph is even, false otherwise
pass
def count_components(self):
# return the number of components in graph.
def dfs(node, visited):
visited[node] = True
for neighbor, is_edge in enumerate(self.adj_matrix[node]):
if is_edge and not visited[neighbor]:
dfs(neighbor, visited)
visited = [False] * self.num_nodes
num_components = 0
for node in range(self.num_nodes):
if not visited[node]:
# If the node hasn't been visited, it's a new component
dfs(node, visited)
num_components += 1
return num_components
def is_connected(self):
# TODO: return true is the graph is connected, false otherwise
pass
def is_bridge(self, edge):
# TODO: return true if the given edge is an bridge, false otherwise
# edge is given as a python pair.
pass
def is_adjacent(self, node1, node2):
if self.adj_matrix[node1][node2] == 1:
return True
else:
return False
def print_graph(self):
# Print the adjacency matrix
for row in self.adj_matrix:
print(" ".join(map(str, row)))
if __name__ == "__main__":
# use case
test_graph = Graph(3)
test_graph.add_edge(1,0)
test_graph.add_edge(1, 2)
print("Is even: ", test_graph.is_even())
x = {1}
print("Edge cut is ", test_graph.edge_cut(x))
print("Is connected: ", test_graph.is_connected())
print("Is bridge: ", test_graph.is_bridge((1, 2)))
from Graph import *
import copy
def Fleury(g, u):
# TODO: implement Fleury's algorithm.
# input: a graph and a vertex of the graph,
# return: an array of vertices representing the Euler tour.
# Return empty array if g is not even or not connected.
if not g.is_even() or not g.is_connected():
return []
# Run the algorithm when g is even and connected
W = [u]
x = u
F = copy.deepcopy(g)
edge_cut = F.edge_cut({x})
current_edge = (-1, -1)
pass
# test
test_graph = Graph(5)
test_graph.add_edge(0,3)
test_graph.add_edge(0,2)
test_graph.add_edge(1,3)
test_graph.add_edge(1,2)
test_graph.add_edge(2,3)
test_graph.add_edge(2,4)
test_graph.add_edge(3,4)
print(Fleury(test_graph, 1))
Step by step
Solved in 2 steps with 1 images
