时间戳

首页 > 解决方案 > 网络链路布线的路径查找器 - 后续

python - 网络链路布线的路径查找器 - 后续

问题描述

请参阅有关代码审查的初始帖子

感谢@Graipher，他提出了networkx用 Python 调用的库来回答我的问题。我的代码现在得到了改进和清洁：

# Path finder improved

class Edge:
  # An Edge is a link (physical, radio, logical) between two assets/nodes/vertices
  def __init__(self, sku, e1, e2, re1, re2):
    # The SKU is the unique ID of the edge
    # An edge two vertices that can be inversable (undirected edge)
    self.sku = sku
    self.sku_endpoint_1 = e1
    self.sku_endpoint_2 = e2
    self.reverse_sku_endpoint_1 = re1
    self.reverse_sku_endpoint_2 = re2

# We can instanciante a edge like that

edge1 = Edge("Edge1","A", "B", "B", "A")
edge2 = Edge("Edge2","B", "C", "C", "B")
edge3 = Edge("Edge3","A", "C", "C", "A")
edge4 = Edge("Edge4","C", "D", "D", "C")
edge5 = Edge("Edge5","B", "E", "E", "B")
edge6 = Edge("Edge6","D", "E", "E", "D")

edges = [edge1, edge2, edge3, edge4, edge5, edge6]

# And then we can find all paths using @Graipher method

def solve(edges, source, target):
  g = nx.Graph()  # bi-directional edges.
  for edge in edges: 
    g.add_edge(edge.sku_endpoint_1, edge.sku_endpoint_2, sku=edge.sku)
  paths = nx.all_simple_paths(g, source=source, target=target)
  index = 0
  paths_dict = {}
  # Creating the dict of paths with only the edgesku
  for path in map(nx.utils.pairwise, paths):
    paths_dict[index] = []
    for edge in path:
        paths_dict[index].append(g.edges[edge]["sku"])
    index+=1
  return paths_dict

但是现在，如何找到所有具有重复节点但不重复相同边的路径呢？我现在看到networkx库在搜索路径时明确不重复节点......

但请考虑下图：

g.add_edges_from([("A", "B", {"sku": "Edge1"}),
                  ("B", "C", {"sku": "Edge2"}),
                  ("A", "C", {"sku": "Edge3"}),
                  ("C", "D", {"sku": "Edge4"}),
                  ("B", "E", {"sku": "Edge5"}),
                  ("D", "E", {"sku": "Edge6"}),
                  ("C", "E", {"sku": "Edge7"})]

我们看到的图表是这样的：

在此处输入图像描述

当我们想找到从 A 到 D 的所有路径时，我们也想找到一条路径，即使它使用了一个已经发现的节点（这里是 C）。我们想要的唯一规则是，不要添加使用相同边缘的路径（以防止无限循环）。

在此示例中，与 A 到 D 的这些规则匹配的一条路径是：

 A->C : "Edge3"
 C->E : "Edge7"
 E->B : "Edge5"
 B->C : "Edge2"
 C->D : "Edge4"

有没有办法用这个库做到这一点？因为通过我的代码（参见之前关于 codereview 的帖子），我能够找到这些路径。但这不是很优化，因为程序会搜索所有路径，然后我才会删除重复且无意义的路径。

标签： python

解决方案

我想了一会儿这个有趣的问题，但不幸的是没有一个很好的答案。

1.方法

我的第一种方法是基于以下观察（我将您正在寻找的路径称为edge-simple）：

  1. 每个简单的路径显然是边缘简单的。
  2. 通过删除多个节点之间的循环（循环），可以将每个边简单图简化为简单路径。

为了说明 2. 点，请查看您用作示例路径的路径A-C-E-B-C-D。它有C两次节点，去掉对应的循环后C-E-B-C，就很简单了：A-C-D。

我的想法是使用两个节点之间的简单路径作为边缘简单路径的基础

simple_paths = list(nx.all_simple_paths(G, 'A', 'D'))

并将循环添加到它包含的节点（这里通过（完整）相应的有向图构造）

H = nx.DiGraph()
H.add_edges_from(list(G.edges) + [(edge[1], edge[0]) for edge in G.edges])
cycles_basis = [cycle for cycle in nx.simple_cycles(H) if len(cycle) > 2]

但是我在第二部分的路上迷路了......

2.方法

我最终得到了第二种方法，类似于@JordanSimba 给出的方法：

import networkx as nx

def remove_edge(G, node1, node2):
    return G.edge_subgraph(list(set(G.edges)
                                .difference({(node1, node2), (node2, node1)})))

def all_edge_simple_paths(G, source, target):
    paths = []
    if source == target:
        paths.append([source])
    for node in G[source]:
        G_sub = remove_edge(G, source, node)
        if node in G_sub.nodes and target in G_sub.nodes:
            paths.extend([[source] + path
                          for path in all_edge_simple_paths(G_sub, node, target)])
        else:
            if node == target:
                paths.append([source, target])
    return paths

用你的图表

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('B', 'C'), ('A', 'C'), ('C', 'D'), ('B', 'E'),
                  ('D', 'E'), ('C', 'E')])

结果 ( all_edge_simple_paths(G, 'A', 'D')) 是

[['A', 'B', 'C', 'D'],
 ['A', 'B', 'C', 'E', 'D'],
 ['A', 'B', 'E', 'D'],
 ['A', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'B', 'E', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D'],
 ['A', 'C', 'E', 'D']]

如果一个小循环被添加到节点上D

G.add_edges_from([('D', 'F'), ('F', 'G'), ('G', 'D')])

结果包括它（通过循环的两个方向）

[['A', 'B', 'C', 'D'],
 ['A', 'B', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'C', 'E', 'D'],
 ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'C', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'E', 'D'],
 ['A', 'B', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'E', 'C', 'D'],
 ['A', 'B', 'E', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'E', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'B', 'E', 'D'],
 ['A', 'C', 'B', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'B', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'D'],
 ['A', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'E', 'D'],
 ['A', 'C', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'E', 'D', 'G', 'F', 'D']]

老实说：我不是 100% 确定它可以正常工作（适用于所有情况）。我只是没有时间进行广泛的测试。并且路径的数量随着图形大小的增加而迅速增长，这使得很难跟踪正在发生的事情。

我对效率有严重的怀疑。最近有人向我指出，使用子图视图可能会减慢速度。因此，也许只有较低级别的实现可能会产生您正在寻找的速度。

但也许它有帮助。

推荐阅读