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

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

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

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

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()])

python graph undirected-graph
person sledgehammr    schedule 24.03.2020    source источник
comment
Есть ли причина, по которой вы не используете NetworkX?   -  person busybear    schedule 25.03.2020
comment
Немного не по теме, но почему тебя зовут Кувалда, а на аватарке коала? Это наводит на некоторые подозрения...   -  person    schedule 25.03.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

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

Псевдокод (который очень похож на 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)
    }
}
person Community    schedule 25.03.2020