python - 将格子转换为图形？

Question

假设我有一个 d 乘以 Z 且间距相等的点格，我如何才能有效地将其转换为以节点为点、两点之间有一条边的图形，当且仅当这些点相邻时？

例如:假设我们在对应于正方形顶点的整数平方中给出点...我们如何将其转换为具有条目 1 或 0 的 4 x 4 矩阵(或图形)是否存在连接两个节点的边(对应于整数平方中的点)

这个例子很简单有两个原因:

• 点位于 R 平方内，因此输入是一个二维数组(通常输入是一个 d 维数组；d>1
• 大多数点都以明显的方式连接......但模式(至少我发现)在 d 维度上变得不那么明显，每个轴上有更多点......(如果我们采用位于立方体边缘的 8 个点)。

我正在寻找一种代码，它可以在给定任何此类数组(作为输入)的情况下实现此代码，并输出一个(必须对称的)矩阵，该矩阵表示图上节点之间的边。

我用 R 编程(并且愿意学习 Python)。

Ps.s:我为奇怪的语法道歉......这个交换显然与 LaTeX 不兼容......:0

Answer 1

这可以像这样用 Python 实现:

from itertools import product

def print_lattice_edges(lattice):
    """prints all edges of a lattice, given as a list of lists of coordinates"""
    for idim, dim_coords in enumerate(lattice):
        for other_coords in product(*lattice[:idim] + lattice[idim+1:]):
            for coord1, coord2 in zip(dim_coords[:-1], dim_coords[1:]):
                edge1 = other_coords[:idim] + (coord1,) + other_coords[idim:]
                edge2 = other_coords[:idim] + (coord2,) + other_coords[idim:]
                print edge1, '->', edge2

解释:

• 首先遍历所有维度，选择该维度的所有坐标

• 通过删除选定的维度创建一个新的晶格，并遍历 Cartesian product使用 itertools.product 的剩余维度的所有可能的坐标组合

• 对于选定的维度，遍历所有可能的连续坐标对。

• 通过将所选维度的坐标放回正确位置的笛卡尔积来生成边的两个坐标。

如果您的应用程序涉及数百万个点并且速度是一个问题，您可以通过使用 numpy 生成笛卡尔积来执行类似的操作。 .

一些快速测试:

In [23]: print_lattice_edges([[0, 1], [0, 1]])  # your example
(0, 0) -> (1, 0)
(0, 1) -> (1, 1)
(0, 0) -> (0, 1)
(1, 0) -> (1, 1)

In [24]: print_lattice_edges([[0, 1], [3, 4, 5]])  # 2x3 points, 7 edges
(0, 3) -> (1, 3)
(0, 4) -> (1, 4)
(0, 5) -> (1, 5)
(0, 3) -> (0, 4)
(0, 4) -> (0, 5)
(1, 3) -> (1, 4)
(1, 4) -> (1, 5)

In [25]: print_lattice_edges([[0, 1], [0, 1], [0, 1]])  # cube, 12 edges
(0, 0, 0) -> (1, 0, 0)
(0, 0, 1) -> (1, 0, 1)
(0, 1, 0) -> (1, 1, 0)
(0, 1, 1) -> (1, 1, 1)
(0, 0, 0) -> (0, 1, 0)
(0, 0, 1) -> (0, 1, 1)
(1, 0, 0) -> (1, 1, 0)
(1, 0, 1) -> (1, 1, 1)
(0, 0, 0) -> (0, 0, 1)
(0, 1, 0) -> (0, 1, 1)
(1, 0, 0) -> (1, 0, 1)
(1, 1, 0) -> (1, 1, 1)