безотходный способ хранения подграфов

Question

Предположим, у меня есть 6 элементов: A, B, C, D, E и F. A подключается к B (альтернативно B подключается к A - нет понятия направления), B подключается к C, D соединяется с E, а F не связан ни с чем. Но то, что я на самом деле хочу, это не прямые связи, а просто узнать, какие элементы имеют некоторый путь, соединяющий их.

Я знаю, что одним из способов кодирования этого в Python является матрица смежности 6x6. Но так как это довольно разреженная матрица, это приводит к расточительству памяти.

Другой способ, который я знаю со словарем. Вот как это будет выглядеть в Python.

graph = {
    A: [B, C],
    B: [A, C],
    C: [A, B],
    D: [E],
    E: [D],
    F: []
}

Однако эта структура действительно лучше отслеживает прямые связи, чем связанные подграфы. В частности, используется много неиспользуемой памяти, например, A: [B, C] и B: [A, C] кодируют одно и то же.

Может кто-нибудь порекомендовать структуру данных, которая была бы лучше для хранения этой информации и / или алгоритм для создания такой структуры, которая масштабируется лучше, чем либо матрица смежности, либо приведенный выше словарь?

Answer 1

Вы можете express свои отношения в виде наборов символов и вычислять наборы связанных символов, используя решение Python для задачи Кодекса Розетты "Установить консолидацию" здесь .

>>> consolidate([set('AB'), set('BC'), set('DE'), set('F')])
[{'A', 'C', 'B'}, {'E', 'D'}, {'F'}]
>>> 

Answer 2

Вы можете использовать Несвязанные множества . Здесь возможна реализация:

# Implementation of Union-Find (Disjoint Set)
class Node:
    def __init__(self, value):
        self.value = value
        self.values = [value]
        self.parent = self
        self.rank = 0

    def find(self):
        if self.parent.parent != self.parent:
            self.parent = self.parent.find()
        return self.parent

    def union(self, other):
        node = self.find()
        other = other.find()
        if node == other:
            return True # was already in same set
        if node.rank > other.rank:
            node, other = other, node
        node.parent = other
        other.rank = max(other.rank, node.rank + 1)
        other.values.extend(node.values)
        node.values = None # Discard
        return False # was not in same set, but now is

nodes = "ABCDEF"
edges = ["AB", "AC", "DE"]

# create Node instances
nodes = {node: Node(node) for node in nodes}
# process the edges
for a, b in edges:
    nodes[a].union(nodes[b])

# now do a query
print("group with 'B' {}".format(nodes["B"].find().values))

Answer 3

В Python есть некоторые библиотеки, такие как networkx или igraph

Networkx

Я использовал networkx в течение длительного времени. Это задокументировано очень хорошо. Здесь я покажу, в чем разница между направленным и неориентированным графами:

Направлено:

import matplotlib.pyplot as plt
import networkx as nx
A, B, C, D, E, F = 'A', 'B', 'C', 'D', 'E', 'F'
dictionary = {A: [B, C], B: [A, C], C: [A, B], D: [E], E: [D], F: []}
G = nx.DiGraph(dictionary)
nx.draw(G, with_labels=True)
plt.show() 

Доступ к подключенным компонентам можно получить следующим образом:

>>> print([list(n) for n in nx.strongly_connected_components(G)])
[['B', 'A', 'C'], ['D', 'E'], ['F']]

Ненаправленный:

import matplotlib.pyplot as plt
import networkx as nx
A, B, C, D, E, F = 'A', 'B', 'C', 'D', 'E', 'F'
dictionary = {A: [B], B: [C], C: [A], D: [E], F: []}
G = nx.Graph(dictionary)
nx.draw(G, with_labels=True)
plt.show() 

Доступ к подключенным компонентам можно получить следующим образом:

>>> print([list(n) for n in nx.connected_components(G)])
[['B', 'A', 'C'], ['E', 'D'], ['F']]

Answer 4

Если вы строго ищете эффективное хранение неориентированного графа, вы можете использовать строку с несколькими соглашениями. Сначала пары имен узлов (ребра) всегда выражаются в убывающем алфавитном (или буквенно-цифровом) порядке. Во-вторых, вы не повторяете левую сторону этого спаривания, перечисляя только связанные узлы после их большего аналога.

Это даст строку, подобную этой: "B, A | C, A, B | E, D | F "

Вы можете go назад и вперед между этой строковой кодировкой и полностью расширенным словарным представлением в памяти (что будет необходимо для любых значимых манипуляций):

От строка в словарь:

sGraph = "B,A|C,A,B|E,D|F"
dGraph = { v:[] for v in sGraph.replace("|",",").split(",") }
dGraph.update({ v[0]:v[1:] for vG in sGraph.split("|") for v in[vG.split(",")]})
for v1,v2 in [(v1,v2) for v1,vN in dGraph.items() for v2 in vN]:dGraph[v2].append(v1)

Вывод:

print(dGraph) 
# {'B': ['A', 'C'], 'A': ['B', 'C'], 'C': ['A', 'B'], 'E': ['D'], 'D': ['E'], 'F': []}

примечание: в зависимости от ваших потребностей обработки последний для l oop (выше) может быть опущен. Это дало бы вам полное представление графа без избыточности по краям (но было бы намного сложнее манипулировать)

# {'B': ['A'], 'A': [], 'C': ['A', 'B'], 'E': ['D'], 'D': [], 'F': []}

Форма словаря в строку (на основе полностью развернутого представления):

dGraph = {'B': ['A', 'C'], 'A': ['B', 'C'], 'C': ['A', 'B'], 'E': ['D'], 'D': ['E'], 'F': []}
sGraph = sorted(v for v,vN in dGraph.items() if any(v2<v for v2 in vN) or not vN)
sGraph = "|".join( ",".join([v1,*(v2 for v2 in dGraph[v1] if v2<v1)]) for v1 in sGraph)

вывод:

print(sGraph)
# B,A|C,A,B|E,D|F

Длина строки всегда будет меньше 2 * (E + V), где E - количество ребер, а V - количество вершин ( предполагая одну букву / символ на имя вершины).

Answer 5

Вы можете использовать наборы для этого.

Set1: {A, B, C},
Set2: {D, E},
Set3: {F}

Если вам нужно быстро go от элемента к его набору, используйте словарь.