IdelHamza - 1 year ago 73

Python Question

I built a graph in Python, based on Vertex and graph classes, but in

`isCycleUtil()`

`for i in self.vert_dict[v]`

Can you help me to fix It and have a functional isCycleUtil method?

`class Vertex:`

def __init__(self, node):

self.id = node

self.adjacent = {}

def __str__(self):

return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])

def add_neighbor(self, neighbor, weight=0):

self.adjacent[neighbor] = weight

def get_connections(self):

return self.adjacent.keys()

def get_id(self):

return self.id

def get_weight(self, neighbor):

return self.adjacent[neighbor]

def set_weight(self, neighbor, newvalue):

self.adjacent[neighbor] = newvalue

and the graph class:

`class Graph:`

def __init__(self):

self.vert_dict = {}

self.num_vertices = 0

def __iter__(self):

return iter(self.vert_dict.values())

def add_vertex(self, node):

self.num_vertices += 1

new_vertex = Vertex(node)

self.vert_dict[node] = new_vertex

return new_vertex

def get_vertex(self, n):

if n in self.vert_dict:

return self.vert_dict[n]

else:

return None

def add_edge(self, frm, to, cost = 0):

if frm not in self.vert_dict:

self.add_vertex(frm)

if to not in self.vert_dict:

self.add_vertex(to)

self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)

def get_vertices(self):

return self.vert_dict.keys()

def isCyclicUtil(self,v,visited,parent):

#Mark the current node as visited

if not visited[v]:

visited[v]= True

parent[v] = True

#Recur for all the vertices adjacent to this vertex

for i in self.vert_dict[v]:

# If the node is not visited then recurse on it

if (not visited[i] and self.isCyclicUtil(i,visited,parent)):

return True

elif (not parent[i]):

return True

parent[v] = False

return False

#Returns true if the graph contains a cycle, else false.

def isCyclic(self):

# Mark all the vertices as not visited

visited = {}

parent = {}

for i in self.vert_dict:

visited[i] = False

parent[i] = False

# Call the recursive helper function to detect cycle in different

#DFS trees

for i in self.vert_dict:

if(self.isCyclicUtil(i,visited,parent)):

return True

return False

Answer Source

To avoid this error you need to replace:

```
for i in self.vert_dict[v]
```

with

```
for i in self.vert_dict[v].get_connections()
```

and use:

```
visited[v.get_id()]
```

instead of

```
visited[v]
```

to avoid KeyError

Your graph is directed so correct algoritm is descibed in this topic:

How to detect if a directed graph is cyclic?

You need to change implementation of isCyclicuntil method:

```
def isCyclicUtil(self, v, visited, parent):
# Mark the current node as visited
if not visited[v]:
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.vert_dict[v].get_connections():
# If the node is not visited then recurse on it
if visited[i.get_id()]:
return True
elif self.isCyclicUtil(i.get_id(), visited, parent):
return True
return False
```