2

Suppose I have a lattice of points in d times Z with equal spacing apart, how can I efficiently convert this into a graph with nodes being the points and an edge between two points if and only if those points are adjacent?

For example: suppose we're given points in the integers squared corresponding to the vertices of a square... How can we convert this into a 4 by 4 matrix (or graph) with entries 1 or 0 is there are edges connecting the two nodes (which correspond to the points in the integers squared)

The example is simple for two reasons:

  • The points lie in R squared, so the input is a 2-dimensional array (where in general the input would be a d-dimensional array; d>1
  • Most points are connected in an obvious way... but the pattern (at least I find) becomes less apparent in d-dimensions, with more points on each axis.... (which is even clear if we take the 8 points lying on the edge of a cube).

I'm looking for a code which can implement this given any such array (As an input) and outputs a (necessarily symmetric) matrix representing the edges between the nodes on the graph.

I programming in R (and am open to learning Python).

Ps.s:I apologize for the odd syntax... this exchange is not compatible with LaTeX apparently... :0

ABIM
  • 364
  • 3
  • 19

1 Answers1

3

This could be implemented in Python like so:

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

Explanation:

  • First loop over all dimensions, select all coordinates for that dimension

  • Create a new lattice by removing the selected dimension, and iterate over the Cartesian product of all possible combinations of coordinates for the remaining dimensions using itertools.product

  • For the selected dimension, iterate over all the possible pairs of successive coordinates.

  • Generate both coordinates of the edge by putting the coordinate of the selected dimension back into the Cartesian product at the right place.

In case your application involves millions of points and speed is an issue, you might be able to do something similar by generating the Cartesian product using numpy.

Some quick tests:

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)
Community
  • 1
  • 1
Bas Swinckels
  • 18,095
  • 3
  • 45
  • 62
  • Perfect! Thanks you so much Bas (I'm new to python so this wasn't as intuitive to me) – ABIM Feb 27 '16 at 18:04
  • Small question (since I'm still quite new to Python), if I wanted an edge between any two nodes within a certain distance (in R) from eachother instead of only bettween adjacent nodes, how could I modify the above code? – ABIM Mar 23 '16 at 18:51
  • 1
    @CSA that is hard to explain quickly, better to ask a separate question for that. The 'brute force' way to do that would `for c1 in all_possible_coords: for c2 in all_possible_coords: if distanced(c1, c2) < R: add_edge(c1, c2)`. Note that this algorithm loops over all possible combinations, so it takes `O(npoints^2)` operations, this might be slow for big problems. The solution in my answer only scales with `O(npoints * ndim)`, which is no problem if `ndim` is small. – Bas Swinckels Mar 23 '16 at 19:11
  • Cool, thanks for the feedback I'll post a new question on this shortly. Thanks again – ABIM Mar 23 '16 at 19:26