存储子图的非浪费方式

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

Python 中有一些库，例如 networkx 或 igraph

网络x

我用了很长时间 networkx。 documented 很好。我将在这里展示有向图和无向图之间的区别：

导演：

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 2

您可以为此使用集合。

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

如果您需要快速从一个元素转到其集合，请使用字典。

Answer 3

您可以使用 Disjoint Sets。这是可能的实现：

# 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 4

您可以将您的关系表示为字符集，并使用 Python Rosetta 代码任务的解决方案计算连接字符集 "Set consolidation" here.

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

Answer 5

如果您严格地寻找无向图的高效存储，您可以使用具有几个约定的字符串。首先，节点名称配对（边）始终按降序字母（或字母数字）顺序表示。其次，您不会通过仅在较大对应节点之后列出相关节点来重复该配对的左侧。

这将给出这样的字符串："B,A|C,A,B|E,D|F"

您可以在此字符串编码和内存中完全扩展的字典表示之间来回切换（这对于任何有意义的操作都是必需的）：

从字符串到字典：

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': []}

注意：根据您的处理需要，可以省略最后一个 for 循环（上面）。这将为您提供图形的完整表示，边缘没有冗余（但这会使操作变得更加困难）

# {'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 是顶点数（假设每个顶点名称一个 letter/character）。

存储子图的非浪费方式

non-wasteful way to store subgraphs

python

algorithm

graph-theory

data-structures