Почему мой код принимает разные значения, когда я переключаю порядок в наборе (зная, что порядок не имеет значения для множеств)

Question

Я пытаюсь реализовать метод, который возвращает ребра графа, представленного списком / словарем смежности.

Итак, для итерации по словарю сначала я итерировал по ключам, а затем по каждому значению, сохраненному в соответствующем ключе. Внутри вложенного цикла for у меня было условие, когда, если конкретное ребро, скажем, (a, b) не входит в набор ребер, добавьте его в набор - передайте иначе. В моем первом запуске метод получил ребра, которые одинаковы, то есть в наборе ребер есть (a, b) и (b, a).

class Graph():
    def __init__(self, grph={}):
        self.graph = grph

    def get_vertices(self):
        for keys in self.graph:
            yield keys

    def get_edges(self):
        edges = set()
        for key in self.graph:
            for adj_node in self.graph[key]:
                if (key, adj_node) not in edges:
                    edge = (key, adj_node)
                    edges.add(edge)
                else:
                    pass
        return edges


def main():
    graph1 = {
        'A': ['B','C','D'],
        'B': ['A','E'],
        'C': ['A', 'D'],
        'D': ['A', 'C'],
        'E': ['B'],
    }
    graph_one = Graph(graph1)
    print(list(graph_one.get_vertices()))
    print(graph_one.get_edges())

if __name__ =='__main__':
    main()

вывод:

{( 'А', 'В'), ( 'D', 'A'), ( 'B', 'A'), ( 'B', 'E'), ( 'А',» D '), (' D ' 'C'), ( 'E', 'В'), ( 'C', 'D'), ( 'A', 'C'), ( 'C',' А ')}

Итак, я просто изменил выражение if:

"if (adj_node, key) не по краям:"

def get_edges(self):
        edges = set()
        for key in self.graph:
            for adj_node in self.graph[key]:
                if (adj_node, key) not in edges:
                    edge = (key, adj_node)
                    edges.add(edge)
                else:
                    pass
        return edges

Теперь вывод был:

{( 'C', 'D'), ( 'A', 'B'), ( 'E', 'В'), ( 'А', 'С'), ( 'А',» D ')}

Мне очень любопытно, почему это так, и я был бы так благодарен, если бы вы, ребята, смогли мне это объяснить. Заранее спасибо!

Answer 1

Когда мы говорим, что наборы не имеют порядка или этот порядок не имеет значения, это означает, что {x, y} == {y, x}. Но (a, b) и (b, a) являются кортежами, для них важен порядок, поэтому (a, b) != (b, a) и, следовательно, {(a, b), (b, a)} - это набор с двумя различными элементами, хотя он равен {(b, a), (a, b)}.

Когда ваш код выглядит так:

        if (adj_node, key) not in edges:
            edge = (key, adj_node)
            edges.add(edge)

затем, когда впервые встречается ребро a <-> b, оно равно (key, adj_node) == (a, b) и добавляется в набор. Когда он встречается во второй (и только другой) раз, он обозначается как (key, adj_node) == (b, a), что означает (adj_node, key) == (a, b), который уже находится в наборе, поэтому (adj_node, key) not in edges имеет значение false и (b, a) не добавляется в набор.

Answer 2

Я думаю, что это просто нужно немного изменить, попробуйте это:

def get_edges(self):
    edges = set()
    for key in self.graph:
        for adj_node in self.graph[key]:
            if ((key, adj_node) not in edges) and ((adj_node, key) not in edges):
                edge = (key, adj_node)
                edges.add(edge)
            else:
                pass
    return edges

Обновление:
Так что это Ундиграф.
И это меня слишком усложнило.
И твой путь на самом деле лучше, чем моя проверка в обе стороны.

Причина, по которой ваш код выполнен успешно, заключается в том, что set будет содержать только один экземпляр любого значения.
Поэтому каждый раз, когда выполняется add, если уже существует такой же кортеж, набор просто не изменится.
И вы уже использовали if, чтобы проверить кортеж противоположного направления, чтобы он не создавал повторяющиеся ребра.

Например, когда (a, b) попадет на проверку if, он проверит, существует ли (b,a) в наборе или нет, если существует, то пройдет. Если нет, добавьте (a, b) в набор, если (a, b) существует, набор не изменится, так как в наборе будет только одна группа.
И позже, когда оно зациклено на (b, a), так как (a, b) уже в наборе, if будет ложным и переданным.
Таким образом, набор безопасен, без повторяющихся краев.