尝试创建边列表（加权）来创建邻接列表

Question

我将开放坐标存储为一个列表中的两个属性：

self.x, self.y = []

我对边缘列表的尝试（从堆栈溢出中取出，哈哈）：

edge = []
        for i in self.x, self.y:
            for j in i[1]:
                edge.append([i[0], j])
                for i in edge:
                    print(i)

每当我尝试此错误时：

for j in i[1]:
TypeError: 'int' object is not subscriptable

出现。

我猜这是因为它是一个元组？我正在尝试创建一个邻接列表，其中带有坐标之间距离的加权边缘，但我还没有考虑添加权重。

将坐标添加到大列表中时，如下所示：

[[[0, 0], [1, 0], [2, 0].....]]

但是当我将它们插入类中时，我是单独进行的。

另一方面，我可以像这样有效地将所有坐标存储到一个属性中吗？或者属性每次都会被覆盖并且只做一个坐标？？

我期待或希望它会在节点之间创建边，然后创建一个邻接列表（我也不知道如何编码）。有了完整的图表，我的目标是创建一个 a* 算法..

抱歉，如果这可能很明显，但我已经很长时间没有正确编码了。我知道这有点乱。

谢谢你。

Answer 1

有这样的事吗？

import itertools
import math

class Graph:
    def __init__(self):
        self.coords = []  # ← array of coords tuples (x, y)
        self.adjacency_list = (
            {}
        )  # ^ dictionary (hash lookup structure of 'key': 'value' pairs):
        #      where each key is a tuple (x, y)
        #      and each value is a list of (neighbor, weight) tuples.

    def add_coord(self, x, y):
        self.coords.append((x, y))

    def calculate_distance(self, coord1, coord2):
        x1, y1 = coord1
        x2, y2 = coord2
        return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

    def build_adjacency_list(self):
        for coord1 in self.coords:
            self.adjacency_list[coord1] = []
            for coord2 in self.coords:
                if coord1 != coord2:
                    distance = self.calculate_distance(coord1, coord2)
                    self.adjacency_list[coord1].append((coord2, distance))


# Demo adjacency list
g = Graph()
for (x, y) in list(itertools.product(range(3), range(3))):
    print(x, y)
    g.add_coord(x, y)
g.build_adjacency_list()

# Print out the adjacency list
for coord, neighbors in g.adjacency_list.items():
    print(f"\n{coord}: \n{neighbors}")

打印：

(0, 0): 
[((0, 1), 1.0), ((0, 2), 2.0), ((1, 0), 1.0), ((1, 1), 1.4142135623730951), ((1, 2), 2.23606797749979), ((2, 0), 2.0), ((2, 1), 2.23606797749979), ((2, 2), 2.8284271247461903)]

(0, 1): 
[((0, 0), 1.0), ((0, 2), 1.0), ((1, 0), 1.4142135623730951), ((1, 1), 1.0), ((1, 2), 1.4142135623730951), ((2, 0), 2.23606797749979), ((2, 1), 2.0), ((2, 2), 2.23606797749979)]

(0, 2): 
[((0, 0), 2.0), ((0, 1), 1.0), ((1, 0), 2.23606797749979), ((1, 1), 1.4142135623730951), ((1, 2), 1.0), ((2, 0), 2.8284271247461903), ((2, 1), 2.23606797749979), ((2, 2), 2.0)]

(1, 0): 
[((0, 0), 1.0), ((0, 1), 1.4142135623730951), ((0, 2), 2.23606797749979), ((1, 1), 1.0), ((1, 2), 2.0), ((2, 0), 1.0), ((2, 1), 1.4142135623730951), ((2, 2), 2.23606797749979)]

(1, 1): 
[((0, 0), 1.4142135623730951), ((0, 1), 1.0), ((0, 2), 1.4142135623730951), ((1, 0), 1.0), ((1, 2), 1.0), ((2, 0), 1.4142135623730951), ((2, 1), 1.0), ((2, 2), 1.4142135623730951)]

(1, 2): 
[((0, 0), 2.23606797749979), ((0, 1), 1.4142135623730951), ((0, 2), 1.0), ((1, 0), 2.0), ((1, 1), 1.0), ((2, 0), 2.23606797749979), ((2, 1), 1.4142135623730951), ((2, 2), 1.0)]

(2, 0): 
[((0, 0), 2.0), ((0, 1), 2.23606797749979), ((0, 2), 2.8284271247461903), ((1, 0), 1.0), ((1, 1), 1.4142135623730951), ((1, 2), 2.23606797749979), ((2, 1), 1.0), ((2, 2), 2.0)]

(2, 1): 
[((0, 0), 2.23606797749979), ((0, 1), 2.0), ((0, 2), 2.23606797749979), ((1, 0), 1.4142135623730951), ((1, 1), 1.0), ((1, 2), 1.4142135623730951), ((2, 0), 1.0), ((2, 2), 1.0)]

(2, 2): 
[((0, 0), 2.8284271247461903), ((0, 1), 2.23606797749979), ((0, 2), 2.0), ((1, 0), 2.23606797749979), ((1, 1), 1.4142135623730951), ((1, 2), 1.0), ((2, 0), 2.0), ((2, 1), 1.0)]

itertools.product(range(3), range(3))

产生：

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

在调用构建邻接列表的方法时，所有坐标元组组合（特别是笛卡尔积）成对（不包括自对...）连接都被添加到每个单独坐标元组的字典中。这就是上面打印的输出。下面是可视化的。

---

将邻接列表可视化为网络图

import networkx as nx
from pyvis.network import Network

# Create a NetworkX graph
G_nx = nx.Graph()

# Add edges to the NetworkX graph
for coord, neighbors in g.adjacency_list.items():
    for neighbor, weight in neighbors:
        G_nx.add_edge(coord, neighbor, weight=weight)

# Create a Pyvis network
net = Network(
    notebook=True,
    cdn_resources="remote",
    width="100%",
    bgcolor="white",
    font_color="red",
)
net.repulsion()

# Add nodes to the Pyvis network
for coord in g.adjacency_list.keys():
    net.add_node(str(coord))

# Add edges to the Pyvis network
for coord, neighbors in g.adjacency_list.items():
    for neighbor, weight in neighbors:
        net.add_edge(str(coord), str(neighbor), weight=weight)


for edge in net.edges:
    source, target = edge["from"], edge["to"]
    weight = G_nx[eval(source)][eval(target)]["weight"]
    edge["label"] = str(round(weight, 2))


net.show("example.html")