I am trying to implement a graph data structure represented by an adjacency list. I am using a dictionary with the vertices as keys and each key can have one or several values. A value consists of a list containing another vertice that the key-vertice is connected to, as well as the cost of traversing between the vertices (undirected graph). Since a a vertice can be connected to several other vertices, the value of a certain key can consist of a nested list.
I know that my implementation is not very object-oriented and that my code could be improved in many ways, but I want to keep it like this for now because I learn better when I start with something very bad and improve it afterwards.
I am having problems with the function is_connected(self, node1, node2). I am trying to see if two vertices are connected (in the adjacency list) by first copying each keys' values to two separate lists. Then I perform a list comprehension for each list in order to flatten any nested list. The idea was to check if each vertice is in each others' list of values, and thereby concluding if they are connected or not.
The problem, though, arises when trying to do the list comprehension.
class UndirectedGraph():
def __init__(self):
self.vertices = my_dict = {
'A' : ['B', 10],
'B' : [['A', 10], ['C', 5]],
'C' : [['B', 5], ['D', 15]],
'D' : [['C', 15], ['E', 25]],
'E' : ['D', 25]
}
def __str__(self):
return str(self.vertices)
def add(self, new_node):
if new_node in self.vertices:
return False
else:
self.vertices[new_node] = []
return True
def connect(self, node1, node2, cost):
if node1 in self.vertices and node2 in self.vertices:
if self.is_connected(node1, node2):
for x, y in [(x, y) for x in self.vertices.get(node1) for y in self.vertices.get(node2)]:
if node2 in x and node1 in y:
x[1] = cost
y[1] = cost
else:
if node1 == node2:
node1_values = [node2, cost]
self.vertices[node1].append(node1_values)
else:
node1_values = [node2, cost]
self.vertices[node1].append(node1_values)
node2_values = [node1, cost]
self.vertices[node2].append(node2_values)
def is_connected(self, node1, node2):
node1_values = self.vertices[node1]
node2_values = self.vertices[node2]
n1 = [str(item) for sublist in node1_values for item in sublist]
n2 = [str(item) for sublist in node2_values for item in sublist]
if node2 in n1 and node1 in n2:
print(node1, "and", node2, "are connected")
return True
else:
print(node1, "and", node2, "are not connected")
return False
I create n class instance and call the method is_connected(self, node1, node2)
g = UndirectedGraph()
g.is_connected('A', 'B')
I get the following error:
Traceback (most recent call last):
File ".\UndirectedGraph.py", line 83, in <module>
g.is_connected('A', 'B')
File ".\UndirectedGraph.py", line 53, in is_connected
n1 = [str(item) for sublist in node1_values for item in sublist]
File ".\UndirectedGraph.py", line 53, in <listcomp>
n1 = [str(item) for sublist in node1_values for item in sublist]
TypeError: 'int' object is not iterable
I suspect it has something to do with the fact that some of the elements in the value lists are integers, which is why tried to convert them to String objects in the beginning if the list comprehension, but I guess they are still interpreted as integers.
I'm thinking that maybe I have to do the integer-to-String conversion before the list comprehension, but I have not been able to find any other solution to that than the .join() method, which I don't want to use because I want to be able to compare elements of two different lists to each other. If I use the .join() method, that means I would have to add all the values to a String, and the split the String into a list?
How do I solve this issue?
Thanks in advance! Or is there any
Compare these two nodes (from your self.vertices dict):
'A' : ['B', 10],
'B' : [['A', 10], ['C', 5]],
I assume this is supposed to represent that node 'A' has an edge to node 'B' with cost 10 and node 'B' has that same edge plus another edge to node 'C' with cost 5. Essentially, your vertices dict is supposed to map from node name (e.g. 'A') to "list of edges with their cost". However, for the node 'A' you forgot to include the outer list: the dict-value is not a nested list. The fix is simple:
# in you __init__ function
self.vertices = my_dict = {
'A' : [['B', 10]],
'B' : [['A', 10], ['C', 5]],
'C' : [['B', 5], ['D', 15]],
'D' : [['C', 15], ['E', 25]],
'E' : [['D', 25]]
}
With this fix, I get:
>>> g = UndirectedGraph()
>>> g.is_connected('A', 'B')
('A', 'and', 'B', 'are connected')