Jump to content

Determinar o caminho mais curto num grafo


Sandra Silva

Recommended Posts

Sandra Silva

Estou a aprender python há relativamente pouco tempo. No âmbito de um projeto académico, foi-nos proposta a construção de um grafo que relaciona as interações entre utilizadores nas redes sociais, sem o recurso a módulos/bibliotecas do python.

Até à data já temos as classes vértice, aresta e grafo concluídas e conseguimos inserir todos os elementos no grafo. Contudo, quando tentamos determinar o caminho mais curto entre dois vértices, os métodos que implementámos ou não retornam qualquer resultado ou retornam o erro e não conseguimos entender o que está errado.

"""Modules"""
import csv

# == Class Vertex == #
class Vertex:
    """Estrutura de Nó para um grafo: um elemento que é o identificador deste nó"""

    __slots__ = "_element", "neighbors"

    def __init__(self, x):
        """O vértice será inserido no Grafo usando o método insert_vertex(x) que cria um Vertex"""
        self._element = x
        self.neighbors = list()

    def vertice(self):
        """Devolve o nome deste vértice; esconde o verdadeiro identificador do atributo"""
        return self._element

    def add_neighbor(self, v):
        if v not in self.neighbors:
            self.neighbors.append(v)
            self.neighbors.sort()

    """Comparação de vértices"""

    def __eq__(self, other):
        if isinstance(other, Vertex):
            return self._element == other.vertice()
        return False

    def __repr__(self):
        return '{0}'.format(self._element)

    def __hash__(self):
        """Referência de memória (usada por causa das keys dos dicionários)"""
        return hash(id(self))  # devolve um inteiro que identifica este vértice como uma chave num dicionário


# == Class Edge == #
class Edge:
    """Estrutura de Aresta para um Grafo: (origem, destino) e seu peso """

    __slots__ = '_origin', '_destination', '_weight'

    def __init__(self, u, v, p=None):
        self._origin = u
        self._destination = v
        self._weight = p

    def __hash__(self):
        # para associar a aresta a uma chave para um dicionário
        return hash((self._origin, self._destination))

    def __repr__(self):
        if self._weight is None:
            return '({0}, {1})'.format(self._origin, self._destination)
        return '({0}, {1}, {2})'.format(self._origin, self._destination, self._weight)

    def endpoints(self):
        """Return (u,v) tuple for vertices u and v."""
        return self._origin, self._destination

    def opposite(self, v):
        """Return the vertex that is opposite v on this edge."""
        return self._origin if v is self._destination else self._origin

    def cost(self):
        """Return the value associated with this edge."""
        return self._weight

    def show_edge(self):
        print('(', self._origin, ', ', self._destination, ') com peso', self._weight)


# == Class Graph == #
class Graph:
    '''Representação de um grafo usando mapeamentos de adjacências (associações) com dictionaries'''

    def __init__(self, directed=False):
        '''Cria um grafo vazio (dicionário de _vertices); é orientado se o parâmetro directed tiver o valor True'''
        self._directed = directed
        self._number = 0            # quantidade de nós no Grafo
        self._vertices = {}         # dicionário com chave vértice e valor dicionário de adjacências

    def __getitem__(self, arg):
        return self._vertices[arg]

    def insert_vertex(self, x):
        '''Insere e devolve um novo vértice com o elemento x'''
        v = Vertex(x)
        self._vertices[v] = {}      # inicializa o dicionário de adjacências a vazio
        self._number = len(self._vertices)
        return v

    def insert_edge(self, u, v, x=None):
        '''Cria u e v e insere e devolve uma nova aresta entre u e v com peso x'''
        e = Edge(u, v, x)
        self._vertices[u][v] = e  # vai colocar nas adjacências de u
        self._vertices[v][u] = e  # e nas adjacências de v (para facilitar a procura de todos os arcos incidentes)

    def incident_edges(self, v, outgoing=True):
        '''Gerador: indica todas as arestas (outgoing) incidentes em v
           Se for um grafo dirigido e outgoing for False, devolve as arestas em incoming
        '''
        for edge in self._vertices[v].values(): # para todas as arestas relativas a v:
            if not self._directed:
                    yield edge
            else:  # senão deve ir procurar em todas as arestas para saber quais entram ou saiem
                x, y = edge.endpoints()
                if (outgoing and x == v) or (not outgoing and y == v):
                    yield edge

    def is_directed(self):
        '''com base na criação original da instância, devolve True se o Grafo é dirigido; False senão '''
        return self._directed  # True se os dois contentores são distintos

    def vertex_count(self):
        '''Devolve a quantidade de vértices no grafo'''
        return self._number

    def vertices(self):
        '''Devolve um iterável sobre todos os vértices do Grafo'''
        return self._vertices.keys()

    def edge_count(self):
        '''Devolve a quantidade de arestas do Grafo'''
        total = sum(len(self._vertices[v]) for v in self._vertices)
        # for undirected graphs, make sure not to double-count edges
        return total if self._directed else total // 2


    def edges(self):
        '''Devolve o conjunto de todas as arestas do Grafo'''
        result = set()      # avoid double-reporting edges in undirected graph
        for secondary_map in self._vertices.values():
            result.update(secondary_map.values())  # add edges to resulting set
        return result


    def get_edge(self, u, v):
        '''Devolve a aresta que liga u e v ou None se não forem adjacentes'''
        edge = self._vertices[u].get(v) # returns None se não existir aresta alguma entre u e v
        if edge != None and self._directed: # se é dirigido
            _, x = edge.endpoints           # vai confirmar se é u --> v
            if x != v:
                edge = None
        return edge


    def degree(self, v, outgoing=True):
        '''quantidade de arestas incidentes no vértice v
        Se for um grafo dirigido, conta apenas as arestas outcoming ou em incoming, de acordo com o valor de outgoing
        '''
        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):
        '''Remove a aresta entre u e 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):
        '''remove o vértice v'''
        # remover todas as arestas de [v]
        # remover todas as arestas com v noutros vertices
        # remover o vértice
        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 __repr__(self):
        """TODO: A Implementar"""
        res = "nodes: "
        '''
        for node in self.vertices():
            res += str(node) + " "
        res += "\nedges: "
        '''
        for edge in self.edges():
            res += str(edge) + " "
        return res

    def printG(self):
        '''Mostra o grafo por linhas'''
        print('Grafo orientado:', self._directed)
        for v in self.vertices():
            print('\nvertex ', v, ' grau_in: ', self.degree(v,False), end=' ')
            if self._directed:
                print('grau_out: ', self.degree(v, False))
            for i in self.incident_edges(v):
                print(' ', i, end=' ')
            if self._directed:
                for i in self.incident_edges(v, False):
                    print(' ', i, end=' ')

def read_csv(filename):

    graph = Graph()
    with open(filename, 'r') as csv_file:
        data = csv.reader(csv_file)
        next(data)

        for linha in data:
            id_origem = linha[0]
            id_destino = linha[1]
            peso = linha[2] if len(linha) > 2 else 1 # None

            v_origem = graph.insert_vertex(id_origem)
            v_destino = graph.insert_vertex(id_destino)

            graph.insert_edge(v_origem, v_destino, peso)

        return graph

read_csv("Data_Facebook.csv")

""" 5. Implementação de métodos para determinar caminhos mais curtos num grafo """

"""(a) sem usar os pesos nas arestas)"""
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._vertices

            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

""" (b) usando os pesos nas arestas"""
def dijkstra(graph, start, goal):
    shortest_distance = {}
    predecessor = {}
    unseenNodes = graph
    infinity = 9999999
    path = []
    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start] = 0

    while unseenNodes:
        minNode = None
        for node in unseenNodes:
            if minNode is None:
                minNode = node
            elif shortest_distance[node] < shortest_distance[minNode]:
                minNode = node

        for childNode, weight in graph[minNode].items():
            if weight + shortest_distance[minNode] < shortest_distance[childNode]:
                shortest_distance[childNode] = weight + shortest_distance[minNode]
                predecessor[childNode] = minNode
        unseenNodes.pop(minNode)

    currentNode = goal
    while currentNode != start:
        try:
            path.insert(0, currentNode)
            currentNode = predecessor[currentNode]
        except KeyError:
            print('Path not reachable')
            break
    path.insert(0, start)
    if shortest_distance[goal] != infinity:
        print('Shortest distance is ' + str(shortest_distance[goal]))
        print('And the path is ' + str(path))

"""
"""
#print(shortest_path(graph, '1563', '1564'))

Alguém pode ajudar o que está errado tanto no método shortest_path() como no método dijkstra()?

Obrigada,

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.