Преобразование решетки в граф?

Question

Предположим, что у меня есть решетка точек в d times Z с равным интервалом друг от друга, как я могу эффективно преобразовать это в граф с узлами, являющимися точками и ребром между двумя точками тогда и только тогда, когда эти точки смежны?

Например: предположим, что нам даны точки в квадратах, соответствующих вершинам квадрата ... Как мы можем преобразовать это в матрицу (или график) 4 на 4 с элементами 1 или 0 является ребром, соединяющее два узла (которые соответствуют точкам в целых числах в квадрате)

пример прост по двум причинам:

• точек лежат в R в квадрате, так что входной сигнал представляет собой 2-мерный массив (где в общем случае вход был бы d-мерным массивом; d> 1
• Большинство точек связаны очевидным образом ... но шаблон (по крайней мере, я нахожу) становится менее очевидным в d-измерениях, с большим количеством точек на каждой оси .... (что даже ясно, если взять 8 точек лежащий на краю куба).

Я ищу код, который может реализовать это при любом таком массиве (как вход) и выводит (обязательно симметричную) матрицу, представляющую ребра между узлами на графике.

I программирование в 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)