Python метод графика для автоматического соединения ребер - PullRequest
Новая
       47

Python метод графика для автоматического соединения ребер

0 голосов
/ 25 марта 2020

Я создаю граф с 5 узлами в нем (A, B, C, D, E) и ребрами / весами ("A", "D", 1), ("D", "B" , 3), ("E", "D", 5), ("C", "B", 4), ("B", "E", 2)

Я хочу создайте для меня функцию, которая будет создавать ребра AB, A C, AE, B C, CE путем суммирования ребер вдоль пути от (например) AB, который будет BD с весом 3 + AD с весом 1 .

Я имею в виду, что если AD - ребро с весом 1, а DB - ребро с весом 3, я хочу, чтобы функция создала ребро AB с весом 4. У меня есть класс графа и вершины, но я не знать, где go отсюда. 

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]

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 = 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)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    def get_vertices(self):
        return self.vert_dict.keys()

if __name__ == '__main__':

    g = Graph()

    g.add_vertex('a')
    g.add_vertex('b')
    g.add_vertex('c')
    g.add_vertex('d')
    g.add_vertex('e')

    allEdges = [("A", "D"), ("D", "B"), ("E", "D"), ("C", "B"), ("B", "E")]
    nodes = ["A", "B", "C", "D", "E"]

    g.add_edge('a', 'd', 1)
    g.add_edge('d', 'b', 3)
    g.add_edge('e', 'd', 5)
    g.add_edge('b', 'c', 4)
    g.add_edge('b', 'e', 2)

    for v in g:
        for w in v.get_connections():
            vid = v.get_id()
            wid = w.get_id()
            print '( %s , %s, %3d)'  % ( vid, wid, v.get_weight(w))

    for v in g:
        print 'g.vert_dict[%s]=%s' %(v.get_id(), g.vert_dict[v.get_id()])

1 Ответ

0 голосов
/ 25 марта 2020

Я не знаю python, но вот алгоритм, о котором я подумал. Кроме того, я предполагаю, что вы говорите о кратчайшем пути между двумя вершинами, потому что в ненаправленном Graph есть бесконечные пути к go от одного Vertex к другому. И я также предполагаю, что вы знаете, как рассчитать кратчайший путь от одного узла ко всем остальным узлам, потому что это довольно сложный топи c, но если вы не сделаете несколько хороших поисков, будет алгоритм кратчайшего пути Дикстры или алгоритм кратчайшего пути Флойда . Итак, после того как вы все это знаете, алгоритм прост.

Начните со случайной исходной вершины, а затем вычислите минимальный вес этой вершины для всех остальных. Затем один за другим go к каждой вершине, к которой текущая вершина не подключена, и соедините их с минимальным весом, который вы рассчитали. Повторите этот же процесс для всех остальных узлов.

Псевдокод (который очень похож на Java, потому что это единственный язык, который я хорошо знаю, но я пытался сделать его понятным): 

for(every Vertex v) {
    Map<Vertex, int> = min-path(v) // min path maps every Vertex with the min weight from v to that Vertex.

    for(every Vertex current that v isn't connected to) {
        connect v -> current with weight map.get-value(current)
    }
}
...