python - 创建连接公共(public)点的线

Question

我有坐标列表，我想从这些点创建一条链(线)，例如输入

[
  [
    ((1, 1), (2, 3)), ((1, 1), (3, 4))
  ],
  [
    ((2, 3), (6, 6)), ((3, 4), (7, 8))
  ],
  [
    ((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))
  ],
  [
    ((11, 11), (12, 13))
  ]
]

我想创建一个链我们有共同点例如在上面的输入中我们有(2, 3), (3, 4), (6, 6), ( 7、8)是共同点。

输出:我想收集所有这些公共(public)坐标点并从中取出一个产品来创建多条候选线，例如

# expected outputs from above input
out1 = [((1, 1), (2, 3))] X [((2, 3), (6, 6))] X [((6, 6), (9, 10)), ((6, 6), (7, 9))]
out2 = [((1, 1), (3, 4))] X [((3, 4), (7, 8))] X [((7, 8), (9, 9))]

# will take product for combinations, which results in-
# for out1
= [((1, 1), (2, 3)), ((2, 3), (6, 6)), ((6, 6), (9, 10))]
= [((1, 1), (2, 3)), ((2, 3), (6, 6)), ((6, 6), (7, 9))]

感谢任何指针、伪代码!

---

我的尝试#1适用于前 2 个列表项 :( 不确定如何在完整列表中扩展它

def pairs(ps):
    for i in range(1, len(ps)):
        yield (ps[i - 1], ps[i])

ls = [
    [((1, 1), (2, 3)), ((1, 1), (3, 4))],
    [((2, 3), (6, 6)), ((3, 4), (7, 8))],
    [((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))],
    [((11, 11), (12, 13))],
]

master_list = []
for l in pairs(ls[:2]): # take fist 2 sub-list
    for k, v in groupby(sorted(l[0], key=lambda t: t[1]), key=lambda t: t[1]):
        new_ls = []
        t = [p for p in l[1] if p[0] == k]
        if t:
            new_ls.append(list(v))
            new_ls.append(t)
        master_list.append(new_ls)

gls = []
for m in master_list:
    for l in list(product(*m)):
        gl = nx.Graph() 
        print("Candidate Line: ", l)
        gl.add_edges_from(l)
        gls.append(gl)

nx.draw_networkx(gls[0])

输出

Candidate Line:  (((1, 1), (2, 3)), ((2, 3), (6, 6)))
Candidate Line:  (((1, 1), (3, 4)), ((3, 4), (7, 8)))

Answer 1

[E_0, ... E_n] 的每个元素都是一个边列表。如果可能，您希望将列表 E_k 中的边 u, v 连接到以下列表 中的边 v, w >E_{k+1}。您可以为每个列表 E_k 存储 from 列表中的顶点 F_k 和 to 顶点列出 T_k。如果顶点在 T_k 和 F_{k+1} 中，则它是您定义的公共(public)点:

Es = [
    [((1, 1), (2, 3)), ((1, 1), (3, 4))],
    [((2, 3), (6, 6)), ((3, 4), (7, 8))],
    [((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))],
    [((11, 11), (12, 13))],
]

Fs = [set(e[0] for e in E) for E in Es]
Ts = [set(e[1] for e in E) for E in Es]

commons = set(t for v, u in zip(Ts, Fs[1:]) for t in v & u)
# set([(3, 4), (2, 3), (7, 8), (6, 6)])