networkx（Python）中基于边权重排序的相邻边

Question

我建立了一个基于networkx的图，其中边表示它们之间的距离。在

  GraphLoc.G.add_edge(fnode_id, snode_id, score=score)

分数是边缘权重。在

我找不到API，它可以提供有边的相邻节点，结果按权重排序。在

显然，我也可以自己排序，但我不想要运行时计算。那么networkx是否提供了任何解决方案

Answer 1

首先，您应该做一些测试，确保按分数对节点的邻居进行排序是代码中的一个瓶颈。在由典型数据源产生的许多图中，一个节点不太可能有多个邻居。在这种情况下，按分数对邻居进行排序非常便宜，不值得预先计算。在

如果您出于某种原因认为这是不够的，并且必须对节点进行预排序，那么我认为您最好的选择是将networkx.Graph子类化，并为其内部表示图提供自己的映射类型。请注意，这只在networkx的开发版本中有记录，所以这个功能还不能保证是可用的或稳定的。在

有两种方法，第二种更一般，但更复杂。在第一种情况下，我假设您可以控制向图中添加边的顺序，并且可以一次添加所有边。在第二种情况下，我不做这样的假设，但代码会更复杂。在

情况1：按排序顺序插入边

在这种情况下，我假设您可以按照分数增加的顺序插入边。所有需要做的就是为子类提供一个工厂，用于保持边的顺序的邻接映射。collections.OrderedDict可以：

import networkx as nx
import collections

class OrderedGraph(nx.Graph):
    adjlist_dict_factory = collections.OrderedDict

g = OrderedGraph()
g.add_edge(1, 3, score=17)
g.add_edge(1, 2, score=42)
g.add_edge(1, 4, score=55)

请注意，边是根据分数按递增顺序添加的！如果我们写下：

^{pr2}$

如你所愿。但是，请注意，如果我们在以后添加一条边，它的分数必须大于它的任何相邻边，排序后的分数不变才能保持不变。也就是说，您不能运行上述代码，然后再执行以下操作：

>>> g.add_edge(1, 5, score=1)

希望它能起作用。您将获得：

>>> g.neighbors(1)
[3, 2, 4, 5]

其中[5, 3, 2, 4]是需要的。如果不能一次添加所有边，并且不能保证它们只是按排序顺序插入的，那么您将需要一个更通用的实现，例如在下一个例子中。在

情况2：以任意顺序插入边

在这种情况下，我们需要一个类似于映射的类，但它按照节点得分的递增顺序跟踪插入的节点。为此，我们将在继承自collections.abc.MutableMapping的类中使用堆和字典。堆将以额外内存为代价保持节点的分数顺序。在

下面的实现非常粗略，请谨慎使用：

import heapq

class SortedScoreMap(collections.abc.MutableMapping):

    def __init__(self):
        self._data = {}
        self._heap = []

    def __getitem__(self, key):
        return self._data[key]

    def __setitem__(self, key, value):
        if key in self._data:
            self._heap_remove_key(key)
        self._data[key] = value
        heapq.heappush(self._heap, (value['score'], key))

    def __delitem__(self, key):
        del self._data[key]
        self._heap_remove_key(key)

    def __iter__(self):
        yield from (key for (score, key) in self._heap)

    def __len__(self):
        return len(self._data)

    def _heap_remove_key(self, key_to_remove):
        entries = []
        for score, key in self._heap:
            if key == key_to_remove:
                entries.append((score, key))

        for entry in entries:
            self._heap.remove(entry)

SortedScoreMap要求其值是带有score键的字典。为了空间的利益，上面的代码并没有强制执行这一点。下面是一个演示：

>>> sm = SortedScoreMap()
>>> sm[5] = {'score': 17}
>>> sm[7] = {'score': 2}
>>> sm[1] = {'score': 42}
>>> list(sm.keys())
[7, 5, 1]
>>> sm[7] = 99
[5, 1, 7]

如您所见，这将保持键按得分顺序排列。现在我们将其用作邻接映射工厂：

import networkx as nx
import collections

class OrderedGraph(nx.Graph):
    adjlist_dict_factory = SortedScoreMap

g = OrderedGraph()
g.add_edge(1, 3, score=17)
g.add_edge(1, 2, score=42)
g.add_edge(1, 4, score=55)

如果我们写下：

^{pr2}$

我们甚至可以：

>>> g.add_edge(1, 5, score=1)
>>> g.neighbors(1)
[5, 3, 4, 2]

而且很管用！在

现在，这是以额外内存（每个键都被有效地复制）和计算为代价的，因为需要一个额外的间接层。根据问题的大小，您可能会发现，每次需要时对邻居进行排序实际上要比这种方法快。所以正如我在开头所说的：分析代码，找出真正的瓶颈是什么，只有然后才能实现改进。在

Answer 2

选择单个节点将返回其相邻节点。然后，您可以很容易地对边缘列表进行排序。首先，我们建立图表。在

>>> G = nx.Graph()
>>> G.add_edge('a', 'b', score=3)
>>> G.add_edge('b', 'c', score=4)
>>> G.add_edge('a', 'c', score=1)

如果我们想要a的邻居，我们只需直接访问该节点：

^{pr2}$

为了对这些结果进行排序，我们使用标准Python工具箱中的工具。.items()将dict转换为tuple，并使用sorted内置函数对结果进行排序：

>>> sorted(G['a'].items(), key=lambda edge: edge[1]['score'])
[('c', {'score': 1}), ('b', {'score': 3})]

如果需要明确显示结果与原始节点之间的关系，则可以通过列表理解将其包含在结果中：

>>> neighbors = sorted(G['a'].items(), key=lambda edge: edge[1]['score'])
>>> [('a', node) for node, _metadata in neighbors]
[('a', 'c'), ('a', 'b')]