Shortest path algoritmh

Question

I'm trying to calculate the shortest path between two vertices on a unweighted graph. My graph is obtaneid from a csv file and I put all the information in a dictionary structure: EDIT:

class Graph:

def __init__(self, directed=False):
    self._directed = directed
    self._number = 0            
    self._vertices = {}    

def insert_vertex(self, x):
    v = Vertex(x)
    self._vertices[v] = {}      
    self._number = len(self._vertices)
    return v

def insert_edge(self, u, v, x=None):
    e = Edge(u, v, x)
    self._vertices[u][v] = e  
    self._vertices[v][u] = e  

def incident_edges(self, v, outgoing=True):
    for edge in self._vertices[v].values(): 
        if not self._directed:
                yield edge
        else:  
            x, y = edge.endpoints()
            if (outgoing and x == v) or (not outgoing and y == v):
                yield edge

def is_directed(self):
    return self._directed  

def vertex_count(self):
    return self._number

def vertices(self):
    return self._vertices.keys()

def edge_count(self):
    total = sum(len(self._vertices[v]) for v in self._vertices)
    return total if self._directed else total // 2


def edges(self):
    result = set()     
    for secondary_map in self._vertices.values():
        result.update(secondary_map.values())  
    return result


def get_edge(self, u, v):
    edge = self._vertices[u].get(v) 
    if edge != None and self._directed: 
        _, x = edge.endpoints           
        if x != v:
            edge = None
    return edge


def degree(self, v, outgoing=True):
    adj = self._vertices
    if not self._directed:
        count = len(adj[v])
    else:
        count = 0
        for edge in adj[v].values():
            x, y = edge.endpoints()
            if (outgoing and x == v) or (not outgoing and y == v):
                count += 1
    return count


def remove_edge(self, u, v):
    if  u in self._vertices.keys() and v in self._vertices[u].keys():
        del self._vertices[u][v]
        del self._vertices[v][u]

def remove_vertex(self, v):
    if v in self._vertices.keys():
        lst = [i for i in self.incident_edges(v)]
        for i in lst:
            x, y = i.endpoints()
            self.remove_edge(x,y)
        del self._vertices[v]
    #return v

def github_csv():
    lista = []
    with open('Github1.csv', 'r') as csv_file:
        data = csv.DictReader(csv_file)
        next(data)
        for row in data:
            lista.append(row)
        rel_dict = {}
        for d in lista:
            if d["follower"] in rel_dict.keys():
                rel_dict[d['follower']].append(d['followed'])
            else:
                rel_dict[d['follower']] = [d['followed']]
        return rel_dict

The output of git_hub() is:

{'9236': ['1570', '13256', '45703', '10005', '30355', '1564', '11917'], '13256': ['9236', '1570', '1563', '22390', '4140', '28106', '11914', '10005', '1567', '1565', '28464', '14922', '41223', '1564', '14613', '1569', '1934', '32872', '11917', '109144', '144589']}

def build_graph():
    graph = Graph(True)
    git = github_csv()
    for k,v in git.items():
        k_vertex = graph.insert_vertex(k)
        for v_item in v:
            v_item_vertex = graph.insert_vertex(v_item)
            graph.insert_edge(k_vertex,v_item_vertex)
    graph.printG()
    return graph

The output is something like:

vertex  59216  grau_in:  1 grau_out:  1
  (4140, 59216) 
vertex  59570  grau_in:  1 grau_out:  1
  (4140, 59570) 

I'm using the following to calculate the shortest path between two vertexs:

def shortest_path(graph, start, goal):
    explored = []

    queue = [[start]]

    if start == goal:
        print("Same Node")
        return

    while queue:
        path = queue.pop(0)
        node = path[-1]

        if node not in explored:
            neighbours = graph[node]

            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)

                if neighbour == goal:
                    print("Shortest path = ", *new_path)
                    return
            explored.append(node)

    print("So sorry, but a connecting" \
          "path doesn't exist :(")
    return

The outuput is:

 Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "C:\Program Files\JetBrains\PyCharm Community Edition 2020.2.3\plugins\python-ce\helpers\pydev\_pydev_bundle\pydev_umd.py", line 197, in runfile
    pydev_imports.execfile(filename, global_vars, local_vars)  # execute the script
  File "C:\Program Files\JetBrains\PyCharm Community Edition 2020.2.3\plugins\python-ce\helpers\pydev\_pydev_imps\_pydev_execfile.py", line 18, in execfile
    exec(compile(contents+"\n", file, 'exec'), glob, loc)
  File "C:/Users/sandr/PycharmProjects/ProjetoEDA/main.py", line 334, in <module>
    shortest_path(graph,'1563','133')
  File "C:/Users/sandr/PycharmProjects/ProjetoEDA/main.py", line 271, in shortest_path
    neighbours = graph[node]
TypeError: 'Graph' object is not subscriptable

Can somenone help me understand what I'm doing wrong?

Answer 1

Class does not support [] operator natively which means that if you define a class Foo you cannot do

foo = Foo()
a = foo[1] # throw subscriptable error

If you want to be able to do graph[node], you need to define the getitem method. More information is available on that post or this post

In your code, you put the graph as an attribute of the graph, so if it is ok with you, you can just use graph._vertices[node]. your graph is represented as {Vertex: {Vertex: Edge}} in your Graph class so node MUST be an instance of Vertex class and return a dictionary looking like {Vertex: Edge}.

To not be lost in your own code, I recommend you to use type hints, then you will know exactly what you are doing. I know it is a little more complicated as you have to install visual studio code and pyright, but you will definitely be more productive as you will know exactly the type of the objects you use. This will make debugging far more easier.

Answer 2

From the general flow of your code, I gather that you expect graph[node] to magically return a sequence of neighboring nodes. Again, you need to learn the interface you've implemented (or chosen). There is no such facility in Graph. Instead, you need to iterate through the incident_edges, working with the destination node of each such edge.

for neighbour_edge in graph.incident_edges(node):
    # access the edge endpoint that is *not* "node"
    neighbour = neighbour_edge.???    # Again, your posting is incomplete.  You'll have to do this part.