Geometric graph generation: possible bug, difficult to re-produce

Hello,

I apologise I can't give a better bug report than this, but I've been
playing with generating geometric graphs using graph-tool. I think the
periodic boundary conditions may not be working properly in some cases,
literally I think corner cases, or maybe there's a rounding error of some
kind?

I was trying to create a hexagonal close packed-like geometric graph. (I'm
fairly new to graph analysis, and I've been struggling to come up with a
good example that would show this bug because I'm finding it difficult to
track down exactly which edges are missing, but I'm pretty sure something's
wrong because I'm not getting the number of edges I expect.)

I'd be grateful for any help or direction.

Thanks,

Matthew

It is difficult to say anything without a specific example of the
problem. Please post a small, self-contained code where the issue can be
seen.

Best,
Tiago

Okay, I can provide two examples given below.

I wouldn't be surprised if it's not a bug and I'm missing something
obvious, e.g. my neighbour cut-off is wrong. I've tried a few different
values and can sometimes get it to work for graphs of certain sizes, but it
then breaks when I try a graph of a different size. It's perplexing because
I've used these same points and boundaries in a different context and they
seem to be correct.

This example works (vertices corresponding to a 3x3x3 repeated
hexagonal-close-packed lattice), the ratio of edges to vertices is 6.0 as
expected:

g,pos = gt.geometric_graph(points_working, 1.00000001,
[(0, 3.0), (0, 5.196152422706632), (0, 4.8989794855663558)])

While this one (vertices corresponding to a 4x4x4 repeated
hexagonal-close-packed lattice) doesn't work, and the ratio of edges to
vertices is 5.625:

g,pos = gt.geometric_graph(points_not_working, 1.00000001,
[(0, 4.0), (0, 6.9282032302755088), (0, 6.5319726474218083)])

where points_working =

[[ 0. 0. 0. ]
[ 0.5 0.8660254 0. ]
[ 0.5 0.28867513 0.81649658]
[ 0. 1.15470054 0.81649658]
[ 0. 0. 1.63299316]
[ 0.5 0.8660254 1.63299316]
[ 0.5 0.28867513 2.44948974]
[ 0. 1.15470054 2.44948974]
[ 0. 0. 3.26598632]
[ 0.5 0.8660254 3.26598632]
[ 0.5 0.28867513 4.0824829 ]
[ 0. 1.15470054 4.0824829 ]
[ 0. 1.73205081 0. ]
[ 0.5 2.59807621 0. ]
[ 0.5 2.02072594 0.81649658]
[ 0. 2.88675135 0.81649658]
[ 0. 1.73205081 1.63299316]
[ 0.5 2.59807621 1.63299316]
[ 0.5 2.02072594 2.44948974]
[ 0. 2.88675135 2.44948974]
[ 0. 1.73205081 3.26598632]
[ 0.5 2.59807621 3.26598632]
[ 0.5 2.02072594 4.0824829 ]
[ 0. 2.88675135 4.0824829 ]
[ 0. 3.46410162 0. ]
[ 0.5 4.33012702 0. ]
[ 0.5 3.75277675 0.81649658]
[ 0. 4.61880215 0.81649658]
[ 0. 3.46410162 1.63299316]
[ 0.5 4.33012702 1.63299316]
[ 0.5 3.75277675 2.44948974]
[ 0. 4.61880215 2.44948974]
[ 0. 3.46410162 3.26598632]
[ 0.5 4.33012702 3.26598632]
[ 0.5 3.75277675 4.0824829 ]
[ 0. 4.61880215 4.0824829 ]
[ 1. 0. 0. ]
[ 1.5 0.8660254 0. ]
[ 1.5 0.28867513 0.81649658]
[ 1. 1.15470054 0.81649658]
[ 1. 0. 1.63299316]
[ 1.5 0.8660254 1.63299316]
[ 1.5 0.28867513 2.44948974]
[ 1. 1.15470054 2.44948974]
[ 1. 0. 3.26598632]
[ 1.5 0.8660254 3.26598632]
[ 1.5 0.28867513 4.0824829 ]
[ 1. 1.15470054 4.0824829 ]
[ 1. 1.73205081 0. ]
[ 1.5 2.59807621 0. ]
[ 1.5 2.02072594 0.81649658]
[ 1. 2.88675135 0.81649658]
[ 1. 1.73205081 1.63299316]
[ 1.5 2.59807621 1.63299316]
[ 1.5 2.02072594 2.44948974]
[ 1. 2.88675135 2.44948974]
[ 1. 1.73205081 3.26598632]
[ 1.5 2.59807621 3.26598632]
[ 1.5 2.02072594 4.0824829 ]
[ 1. 2.88675135 4.0824829 ]
[ 1. 3.46410162 0. ]
[ 1.5 4.33012702 0. ]
[ 1.5 3.75277675 0.81649658]
[ 1. 4.61880215 0.81649658]
[ 1. 3.46410162 1.63299316]
[ 1.5 4.33012702 1.63299316]
[ 1.5 3.75277675 2.44948974]
[ 1. 4.61880215 2.44948974]
[ 1. 3.46410162 3.26598632]
[ 1.5 4.33012702 3.26598632]
[ 1.5 3.75277675 4.0824829 ]
[ 1. 4.61880215 4.0824829 ]
[ 2. 0. 0. ]
[ 2.5 0.8660254 0. ]
[ 2.5 0.28867513 0.81649658]
[ 2. 1.15470054 0.81649658]
[ 2. 0. 1.63299316]
[ 2.5 0.8660254 1.63299316]
[ 2.5 0.28867513 2.44948974]
[ 2. 1.15470054 2.44948974]
[ 2. 0. 3.26598632]
[ 2.5 0.8660254 3.26598632]
[ 2.5 0.28867513 4.0824829 ]
[ 2. 1.15470054 4.0824829 ]
[ 2. 1.73205081 0. ]
[ 2.5 2.59807621 0. ]
[ 2.5 2.02072594 0.81649658]
[ 2. 2.88675135 0.81649658]
[ 2. 1.73205081 1.63299316]
[ 2.5 2.59807621 1.63299316]
[ 2.5 2.02072594 2.44948974]
[ 2. 2.88675135 2.44948974]
[ 2. 1.73205081 3.26598632]
[ 2.5 2.59807621 3.26598632]
[ 2.5 2.02072594 4.0824829 ]
[ 2. 2.88675135 4.0824829 ]
[ 2. 3.46410162 0. ]
[ 2.5 4.33012702 0. ]
[ 2.5 3.75277675 0.81649658]
[ 2. 4.61880215 0.81649658]
[ 2. 3.46410162 1.63299316]
[ 2.5 4.33012702 1.63299316]
[ 2.5 3.75277675 2.44948974]
[ 2. 4.61880215 2.44948974]
[ 2. 3.46410162 3.26598632]
[ 2.5 4.33012702 3.26598632]
[ 2.5 3.75277675 4.0824829 ]
[ 2. 4.61880215 4.0824829 ]]

and points_not_working =

[[ 0. 0. 0. ]
[ 0.5 0.8660254 0. ]
[ 0.5 0.28867513 0.81649658]
[ 0. 1.15470054 0.81649658]
[ 0. 0. 1.63299316]
[ 0.5 0.8660254 1.63299316]
[ 0.5 0.28867513 2.44948974]
[ 0. 1.15470054 2.44948974]
[ 0. 0. 3.26598632]
[ 0.5 0.8660254 3.26598632]
[ 0.5 0.28867513 4.0824829 ]
[ 0. 1.15470054 4.0824829 ]
[ 0. 0. 4.89897949]
[ 0.5 0.8660254 4.89897949]
[ 0.5 0.28867513 5.71547607]
[ 0. 1.15470054 5.71547607]
[ 0. 1.73205081 0. ]
[ 0.5 2.59807621 0. ]
[ 0.5 2.02072594 0.81649658]
[ 0. 2.88675135 0.81649658]
[ 0. 1.73205081 1.63299316]
[ 0.5 2.59807621 1.63299316]
[ 0.5 2.02072594 2.44948974]
[ 0. 2.88675135 2.44948974]
[ 0. 1.73205081 3.26598632]
[ 0.5 2.59807621 3.26598632]
[ 0.5 2.02072594 4.0824829 ]
[ 0. 2.88675135 4.0824829 ]
[ 0. 1.73205081 4.89897949]
[ 0.5 2.59807621 4.89897949]
[ 0.5 2.02072594 5.71547607]
[ 0. 2.88675135 5.71547607]
[ 0. 3.46410162 0. ]
[ 0.5 4.33012702 0. ]
[ 0.5 3.75277675 0.81649658]
[ 0. 4.61880215 0.81649658]
[ 0. 3.46410162 1.63299316]
[ 0.5 4.33012702 1.63299316]
[ 0.5 3.75277675 2.44948974]
[ 0. 4.61880215 2.44948974]
[ 0. 3.46410162 3.26598632]
[ 0.5 4.33012702 3.26598632]
[ 0.5 3.75277675 4.0824829 ]
[ 0. 4.61880215 4.0824829 ]
[ 0. 3.46410162 4.89897949]
[ 0.5 4.33012702 4.89897949]
[ 0.5 3.75277675 5.71547607]
[ 0. 4.61880215 5.71547607]
[ 0. 5.19615242 0. ]
[ 0.5 6.06217783 0. ]
[ 0.5 5.48482756 0.81649658]
[ 0. 6.35085296 0.81649658]
[ 0. 5.19615242 1.63299316]
[ 0.5 6.06217783 1.63299316]
[ 0.5 5.48482756 2.44948974]
[ 0. 6.35085296 2.44948974]
[ 0. 5.19615242 3.26598632]
[ 0.5 6.06217783 3.26598632]
[ 0.5 5.48482756 4.0824829 ]
[ 0. 6.35085296 4.0824829 ]
[ 0. 5.19615242 4.89897949]
[ 0.5 6.06217783 4.89897949]
[ 0.5 5.48482756 5.71547607]
[ 0. 6.35085296 5.71547607]
[ 1. 0. 0. ]
[ 1.5 0.8660254 0. ]
[ 1.5 0.28867513 0.81649658]
[ 1. 1.15470054 0.81649658]
[ 1. 0. 1.63299316]
[ 1.5 0.8660254 1.63299316]
[ 1.5 0.28867513 2.44948974]
[ 1. 1.15470054 2.44948974]
[ 1. 0. 3.26598632]
[ 1.5 0.8660254 3.26598632]
[ 1.5 0.28867513 4.0824829 ]
[ 1. 1.15470054 4.0824829 ]
[ 1. 0. 4.89897949]
[ 1.5 0.8660254 4.89897949]
[ 1.5 0.28867513 5.71547607]
[ 1. 1.15470054 5.71547607]
[ 1. 1.73205081 0. ]
[ 1.5 2.59807621 0. ]
[ 1.5 2.02072594 0.81649658]
[ 1. 2.88675135 0.81649658]
[ 1. 1.73205081 1.63299316]
[ 1.5 2.59807621 1.63299316]
[ 1.5 2.02072594 2.44948974]
[ 1. 2.88675135 2.44948974]
[ 1. 1.73205081 3.26598632]
[ 1.5 2.59807621 3.26598632]
[ 1.5 2.02072594 4.0824829 ]
[ 1. 2.88675135 4.0824829 ]
[ 1. 1.73205081 4.89897949]
[ 1.5 2.59807621 4.89897949]
[ 1.5 2.02072594 5.71547607]
[ 1. 2.88675135 5.71547607]
[ 1. 3.46410162 0. ]
[ 1.5 4.33012702 0. ]
[ 1.5 3.75277675 0.81649658]
[ 1. 4.61880215 0.81649658]
[ 1. 3.46410162 1.63299316]
[ 1.5 4.33012702 1.63299316]
[ 1.5 3.75277675 2.44948974]
[ 1. 4.61880215 2.44948974]
[ 1. 3.46410162 3.26598632]
[ 1.5 4.33012702 3.26598632]
[ 1.5 3.75277675 4.0824829 ]
[ 1. 4.61880215 4.0824829 ]
[ 1. 3.46410162 4.89897949]
[ 1.5 4.33012702 4.89897949]
[ 1.5 3.75277675 5.71547607]
[ 1. 4.61880215 5.71547607]
[ 1. 5.19615242 0. ]
[ 1.5 6.06217783 0. ]
[ 1.5 5.48482756 0.81649658]
[ 1. 6.35085296 0.81649658]
[ 1. 5.19615242 1.63299316]
[ 1.5 6.06217783 1.63299316]
[ 1.5 5.48482756 2.44948974]
[ 1. 6.35085296 2.44948974]
[ 1. 5.19615242 3.26598632]
[ 1.5 6.06217783 3.26598632]
[ 1.5 5.48482756 4.0824829 ]
[ 1. 6.35085296 4.0824829 ]
[ 1. 5.19615242 4.89897949]
[ 1.5 6.06217783 4.89897949]
[ 1.5 5.48482756 5.71547607]
[ 1. 6.35085296 5.71547607]
[ 2. 0. 0. ]
[ 2.5 0.8660254 0. ]
[ 2.5 0.28867513 0.81649658]
[ 2. 1.15470054 0.81649658]
[ 2. 0. 1.63299316]
[ 2.5 0.8660254 1.63299316]
[ 2.5 0.28867513 2.44948974]
[ 2. 1.15470054 2.44948974]
[ 2. 0. 3.26598632]
[ 2.5 0.8660254 3.26598632]
[ 2.5 0.28867513 4.0824829 ]
[ 2. 1.15470054 4.0824829 ]
[ 2. 0. 4.89897949]
[ 2.5 0.8660254 4.89897949]
[ 2.5 0.28867513 5.71547607]
[ 2. 1.15470054 5.71547607]
[ 2. 1.73205081 0. ]
[ 2.5 2.59807621 0. ]
[ 2.5 2.02072594 0.81649658]
[ 2. 2.88675135 0.81649658]
[ 2. 1.73205081 1.63299316]
[ 2.5 2.59807621 1.63299316]
[ 2.5 2.02072594 2.44948974]
[ 2. 2.88675135 2.44948974]
[ 2. 1.73205081 3.26598632]
[ 2.5 2.59807621 3.26598632]
[ 2.5 2.02072594 4.0824829 ]
[ 2. 2.88675135 4.0824829 ]
[ 2. 1.73205081 4.89897949]
[ 2.5 2.59807621 4.89897949]
[ 2.5 2.02072594 5.71547607]
[ 2. 2.88675135 5.71547607]
[ 2. 3.46410162 0. ]
[ 2.5 4.33012702 0. ]
[ 2.5 3.75277675 0.81649658]
[ 2. 4.61880215 0.81649658]
[ 2. 3.46410162 1.63299316]
[ 2.5 4.33012702 1.63299316]
[ 2.5 3.75277675 2.44948974]
[ 2. 4.61880215 2.44948974]
[ 2. 3.46410162 3.26598632]
[ 2.5 4.33012702 3.26598632]
[ 2.5 3.75277675 4.0824829 ]
[ 2. 4.61880215 4.0824829 ]
[ 2. 3.46410162 4.89897949]
[ 2.5 4.33012702 4.89897949]
[ 2.5 3.75277675 5.71547607]
[ 2. 4.61880215 5.71547607]
[ 2. 5.19615242 0. ]
[ 2.5 6.06217783 0. ]
[ 2.5 5.48482756 0.81649658]
[ 2. 6.35085296 0.81649658]
[ 2. 5.19615242 1.63299316]
[ 2.5 6.06217783 1.63299316]
[ 2.5 5.48482756 2.44948974]
[ 2. 6.35085296 2.44948974]
[ 2. 5.19615242 3.26598632]
[ 2.5 6.06217783 3.26598632]
[ 2.5 5.48482756 4.0824829 ]
[ 2. 6.35085296 4.0824829 ]
[ 2. 5.19615242 4.89897949]
[ 2.5 6.06217783 4.89897949]
[ 2.5 5.48482756 5.71547607]
[ 2. 6.35085296 5.71547607]
[ 3. 0. 0. ]
[ 3.5 0.8660254 0. ]
[ 3.5 0.28867513 0.81649658]
[ 3. 1.15470054 0.81649658]
[ 3. 0. 1.63299316]
[ 3.5 0.8660254 1.63299316]
[ 3.5 0.28867513 2.44948974]
[ 3. 1.15470054 2.44948974]
[ 3. 0. 3.26598632]
[ 3.5 0.8660254 3.26598632]
[ 3.5 0.28867513 4.0824829 ]
[ 3. 1.15470054 4.0824829 ]
[ 3. 0. 4.89897949]
[ 3.5 0.8660254 4.89897949]
[ 3.5 0.28867513 5.71547607]
[ 3. 1.15470054 5.71547607]
[ 3. 1.73205081 0. ]
[ 3.5 2.59807621 0. ]
[ 3.5 2.02072594 0.81649658]
[ 3. 2.88675135 0.81649658]
[ 3. 1.73205081 1.63299316]
[ 3.5 2.59807621 1.63299316]
[ 3.5 2.02072594 2.44948974]
[ 3. 2.88675135 2.44948974]
[ 3. 1.73205081 3.26598632]
[ 3.5 2.59807621 3.26598632]
[ 3.5 2.02072594 4.0824829 ]
[ 3. 2.88675135 4.0824829 ]
[ 3. 1.73205081 4.89897949]
[ 3.5 2.59807621 4.89897949]
[ 3.5 2.02072594 5.71547607]
[ 3. 2.88675135 5.71547607]
[ 3. 3.46410162 0. ]
[ 3.5 4.33012702 0. ]
[ 3.5 3.75277675 0.81649658]
[ 3. 4.61880215 0.81649658]
[ 3. 3.46410162 1.63299316]
[ 3.5 4.33012702 1.63299316]
[ 3.5 3.75277675 2.44948974]
[ 3. 4.61880215 2.44948974]
[ 3. 3.46410162 3.26598632]
[ 3.5 4.33012702 3.26598632]
[ 3.5 3.75277675 4.0824829 ]
[ 3. 4.61880215 4.0824829 ]
[ 3. 3.46410162 4.89897949]
[ 3.5 4.33012702 4.89897949]
[ 3.5 3.75277675 5.71547607]
[ 3. 4.61880215 5.71547607]
[ 3. 5.19615242 0. ]
[ 3.5 6.06217783 0. ]
[ 3.5 5.48482756 0.81649658]
[ 3. 6.35085296 0.81649658]
[ 3. 5.19615242 1.63299316]
[ 3.5 6.06217783 1.63299316]
[ 3.5 5.48482756 2.44948974]
[ 3. 6.35085296 2.44948974]
[ 3. 5.19615242 3.26598632]
[ 3.5 6.06217783 3.26598632]
[ 3.5 5.48482756 4.0824829 ]
[ 3. 6.35085296 4.0824829 ]
[ 3. 5.19615242 4.89897949]
[ 3.5 6.06217783 4.89897949]
[ 3.5 5.48482756 5.71547607]
[ 3. 6.35085296 5.71547607]]

The points themselves are generated from a hexagonal-close-packed
basis set of vertices (given here in fractional co-ordinates):

[[ 0. , 0. , 0. ],
[ 0.5 , 0.5 , 0. ],
[ 0.5 , 0.16666667, 0.5 ],
[ 0. , 0.66666667, 0.5 ]]

and the boundary conditions from the ideal (scaled) lattice
parameters, which are 1.0, sqrt(3), and sqrt(8/3.)

Matthew

attachment.html (22.9 KB)

Well, can you pinpoint any of the missing edges? It would be much easier
to debug if the example contained only two points where a missing edge
should have been...

Also, please provide data in a way that is easy to load in a program, at
least with copy and paste. If you do print(array), it is not a good
idea, since one would need to parse it by hand. Instead do
print(repr(array)).

Best,
Tiago

Hi Tiago,

Thanks for the reply. I've written up the example as a github gist, I hope
that makes it easier to run. I will try and pinpoint some specific example
edges too.

https://gist.github.com/mkhorton/aefa5378ec7ec3160876

Thanks,

Matthew

attachment.html (4.96 KB)