0

My unordered adjacency list of nodes with their 2D coordinates:

adjacency_list = [[1, 4], [0, 2, 5], [1, 3, 7], [2, 6, 12],
                  [5, 0, 11], [4, 1, 7, 13], [3, 15, 8],
                  [2, 5, 12, 14], [6, 9, 16], [8, 10, 17],
                  [9, 19], [4, 13, 18], [7, 15, 3], [5, 11, 14, 20],
                  [7, 13], [6, 12, 16], [8, 15, 17], [16, 9, 19, 22],
                  [11, 20, 21], [10, 17, 24], [13, 18, 23], [18, 23, 27],
                  [17, 24, 28], [20, 21, 25, 30], [19, 22, 31],
                  [23, 26, 32], [25, 29, 34], [21, 30, 35], [22, 31, 36],
                  [26, 33, 37], [23, 27, 32, 38], [24, 28, 39],
                  [25, 30, 34, 40], [29, 36, 41], [26, 32, 37, 42],
                  [27, 38], [33, 43, 39, 28], [29, 34, 41, 44],
                  [30, 35, 40], [31, 36, 45], [32, 38, 42],
                  [33, 37, 43, 46], [34, 44, 40], [36, 41, 45],
                  [46, 37, 42], [39, 43], [41, 44]]

centers = [(1023, 763), (902, 742), (776, 718), (629, 681),
             (1041, 673), (924, 651), (479, 643), (799, 625),
             (329, 620), (180, 599), (41, 581), (1051, 580),
             (653, 580), (937, 556), (810, 529), (498, 529),
             (340, 509), (188, 491), (1059, 490), (47, 470),
             (943, 463), (1059, 393), (195, 386), (941, 365),
             (54, 361), (814, 339), (663, 311), (1055, 294),
             (201, 286), (509, 285), (933, 262), (62, 256),
             (806, 234), (357, 232), (657, 199), (1043, 189),
             (210, 185), (507, 167), (925, 157), (74, 149),
             (798, 128), (360, 122), (652, 88), (219, 79),
             (507, 53), (87, 41), (364, 11)]

When I plot them using these coordinates I get a deformed grid:

graph

I want to determine the connectivity of the nodes in a regular grid (find their locations on a structured 2D grid):

gaph with grid solved

I found a possible solution. To program this in Python my idea is to find the diagonals for every node and then resolve the connectivity between neighboring nodes. I’m looking for a more detailed approach to map the nodes to a regular grid based on the adjacency (and the 2D coordinates if necessary).

My plot already shows the vertices arranged as I want. However, this does not tell me how any given node is connected to others. I can see that node 1 is connected west to node 2, south to node 5, and east to node 0. If I know that node 1 is at position (6,0) in a regular grid I can determine its neighbors at (5,0), (6,1), and (7,0). I’d like to avoid heuristic approaches based on angles or distances in a deformed grid since in my final application the grid can be distorted, with angles greater than 45°.

A simpler example to show the algorithmic idea:

My algorithmic idea

I start at node 0 knowing it is connected to 1 in east direction and connected to 3 in south direction. If we look for common neighbors between pairs of neighbors of node 1, we find node 4 (a diagonal node). Since nodes 0, 1, 4, and 3 form a quadrilateral face and node 0 is connected east to 1 and south to 3, we can deduce that:

  • node 1 is connected west to 0 and south to 4,
  • node 3 is connected north to 0 and east to 4.

If we move to a neighbor of node 0 (node 1), we find that node 3 is a diagonal (in the quadrilateral 0, 1, 4, 3) and so is node 5 (in quadrilateral 1, 2, 5, 4).

  • In the first case we already know that node 0 is connected east to 1 and south to 3. From this we deduce that node 4 is connected west to 3 and north to 1.
  • In the second case with diagonal node 5, we only know that node 1 is connected south to 4. At this point node 2 could be either west or east of node 1. But since node 1 is already connected west to 0, node 2 must be east.

Therefore:

  • node 2 is connected west to 1 and south to 5,
  • node 4 is connected north to 1 and east to 5.
Improve this question
7
  • You appear to be trying to go from the vertices. However, you may find it easier to get a structured arrangement from the quadrilaterals (the figures defined by their four corners) - look for cycles of length 4. Commented Oct 3 at 11:36
  • @lastchance, but there seems no guarantee that there will be cycles of length 4, or maybe just a few: the grid seems to have random gaps. Commented Oct 3 at 11:43
  • 2
    "I’ve been trying to program this in Python, but I haven’t succeeded yet." Post your code, what you expect as output, what you get as output, and explain what is wrong with the output. Commented Oct 3 at 15:02
  • Is it possible that your graph has edges that only have one neighbor? Or that have two neighbors which are going in (approx.) the opposite directions (not 90° apart, but +/- 180°)? Commented Oct 6 at 14:14
  • " edges that only have one neighbor?" Do you mean nodes with one neighbor? Commented Oct 6 at 15:06

2 Answers 2

Reset to default
2

First of all, your "connectivity" will only define the final indexing of a structured mesh up to reflection (2 choices) and rotation (4 choices for each).

The method below gives the final (i,j) index in your hand-annotated diagram. Note that I had to do a reflection to get it right.

The code (1) generates a collection of quadrilaterals, each a list of 4 vertices taken anticlockwise (based on "centres") from the smallest node number; (2) iteratively assigns an I,J index to the quadrilaterals as it checks for a common side (also rotating them where necessary to common orientation); (3) assigns the relevant I,J indices to the vertices bounding each quadrilateral; (4) reflects or rotates as necessary (I only happened to need a simple I-reflection here).

def findQuadrilaterals( AdjList, C ):
    '''
    Compile a list of quadrilaterals, defined by their vertex numbers, indexed by the smallest
    vertex number at "bottom-left" and ordered anticlockwise
    '''
    N = len( AdjList )
    quads = []
    for d in range( N ):
        for e in AdjList[d]:
            for f in AdjList[e]:
                for g in AdjList[f]:
                    if d in AdjList[g] and d < min( [e,f,g] ) and d != f and e != g:
                        anticlockwise = (C[f][0]-C[d][0]) * (C[g][1]-C[e][1]) - (C[f][1]-C[d][1]) * (C[g][0]-C[e][0]) > 0
                        if anticlockwise: quads.append( [ d, e, f, g ] )
    return quads

################################################################################

def assignQuadCoords( Q ):
    '''
    By gradually building up their connections, give the quadrilaterals an I, J index.
    Also, rotate the previous vertices to a common orientation
    '''

    Nquad = len( Q )
    Ival = Nquad * [ Nquad ]
    Jval = Nquad * [ Nquad ]

    Ival[0] = Jval[0] = 0
    numAttached = 1

    # Attach the quadrilaterals, giving them I, J indices relative to the first
    # and rotate them to a common orientation
    while numAttached < Nquad:
        for i in range( Nquad ):
            if Ival[i] < Nquad:                                      # i.e. currently attached
                for j in range( Nquad ):
                    if j == i: continue
                    if Q[i][0] in Q[j] and Q[i][1] in Q[j]:          # join up "below"
                        pos = Q[j].index( Q[i][0] );   r = [3,2,1,0][pos]
                        Q[j] = Q[j][-r:] + Q[j][:-r]
                        Ival[j] = Ival[i]
                        Jval[j] = Jval[i] - 1
                        numAttached += 1
                    if Q[i][1] in Q[j] and Q[i][2] in Q[j]:          # join up "to right"
                        pos = Q[j].index( Q[i][1] );   r = [0,3,2,1][pos]
                        Q[j] = Q[j][-r:] + Q[j][:-r]
                        Ival[j] = Ival[i] + 1
                        Jval[j] = Jval[i]
                        numAttached += 1
                    if Q[i][2] in Q[j] and Q[i][3] in Q[j]:          # join up "above"
                        pos = Q[j].index( Q[i][2] );   r = [1,0,3,2][pos]
                        Q[j] = Q[j][-r:] + Q[j][:-r]
                        Ival[j] = Ival[i]
                        Jval[j] = Jval[i] + 1
                        numAttached += 1
                    if Q[i][3] in Q[j] and Q[i][0] in Q[j]:          # join up "to left"
                        pos = Q[j].index( Q[i][3] );   r = [2,1,0,3][pos]
                        Q[j] = Q[j][-r:] + Q[j][:-r]
                        Ival[j] = Ival[i] - 1
                        Jval[j] = Jval[i]
                        numAttached += 1

    # Now make the minimum I and J to be 0
    Imin = min( Ival )
    Jmin = min( Jval )
    for n in range( Nquad ):
         Ival[n] -= Imin
         Jval[n] -= Jmin

    return Q, Ival, Jval, max( Ival ) + 1, max( Jval ) + 1

################################################################################

adjacency_list = [[1, 4], [0, 2, 5], [1, 3, 7], [2, 6, 12],
                  [5, 0, 11], [4, 1, 7, 13], [3, 15, 8],
                  [2, 5, 12, 14], [6, 9, 16], [8, 10, 17], 
                  [9, 19], [4, 13, 18], [7, 15, 3], [5, 11, 14, 20], 
                  [7, 13], [6, 12, 16], [8, 15, 17], [16, 9, 19, 22], 
                  [11, 20, 21], [10, 17, 24], [13, 18, 23], [18, 23, 27], 
                  [17, 24, 28], [20, 21, 25, 30], [19, 22, 31], 
                  [23, 26, 32], [25, 29, 34], [21, 30, 35], [22, 31, 36], 
                  [26, 33, 37], [23, 27, 32, 38], [24, 28, 39], 
                  [25, 30, 34, 40], [29, 36, 41], [26, 32, 37, 42], 
                  [27, 38], [33, 43, 39, 28], [29, 34, 41, 44], 
                  [30, 35, 40], [31, 36, 45], [32, 38, 42], 
                  [33, 37, 43, 46], [34, 44, 40], [36, 41, 45], 
                  [46, 37, 42], [39, 43], [41, 44]]

centers = [(1023, 763), (902, 742), (776, 718), (629, 681), 
             (1041, 673), (924, 651), (479, 643), (799, 625), 
             (329, 620), (180, 599), (41, 581), (1051, 580), 
             (653, 580), (937, 556), (810, 529), (498, 529), 
             (340, 509), (188, 491), (1059, 490), (47, 470), 
             (943, 463), (1059, 393), (195, 386), (941, 365),
             (54, 361), (814, 339), (663, 311), (1055, 294), 
             (201, 286), (509, 285), (933, 262), (62, 256), 
             (806, 234), (357, 232), (657, 199), (1043, 189),
             (210, 185), (507, 167), (925, 157), (74, 149), 
             (798, 128), (360, 122), (652, 88), (219, 79), 
             (507, 53), (87, 41), (364, 11)]


###############################################################################

numNodes = len( adjacency_list )
Q = findQuadrilaterals( adjacency_list, centers )          # Collect the quadrilaterals
Q, I, J, NI, NJ = assignQuadCoords( Q )                    # Assign I,J indices to the quadrilaterals
                                                           #
                                                           #     I,J+1----I+1,J+1
                                                           #      |          |
                                                           #      |   I,J    |
                                                           #      |          |
                                                           #     I,J------I+1,J
                                                           #
# Now sort out vertex indices
Ival = numNodes * [-1]
Jval = numNodes * [-1]
for n in range( len( Q ) ):
    Ival[Q[n][0]] = I[n]  ;   Jval[Q[n][0]] = J[n]
    Ival[Q[n][1]] = I[n]+1;   Jval[Q[n][1]] = J[n]
    Ival[Q[n][2]] = I[n]+1;   Jval[Q[n][2]] = J[n]+1
    Ival[Q[n][3]] = I[n]  ;   Jval[Q[n][3]] = J[n]+1
    
# Rotate and/or reflect if necessary
for n in range( numNodes ):
    Ival[n] = NI - Ival[n]

print( "Node  -->  i, j" )
for n in range( len( adjacency_list ) ):
    print( n, "  -->  ", Ival[n], Jval[n] )

Output (compare with your hand-annotated diagram):


Node  -->  i, j
0   -->   7 0
1   -->   6 0
2   -->   5 0
3   -->   4 0
4   -->   7 1
5   -->   6 1
6   -->   3 0
7   -->   5 1
8   -->   2 0
9   -->   1 0
10   -->   0 0
11   -->   7 2
12   -->   4 1
13   -->   6 2
14   -->   5 2
15   -->   3 1
16   -->   2 1
17   -->   1 1
18   -->   7 3
19   -->   0 1
20   -->   6 3
21   -->   7 4
22   -->   1 2
23   -->   6 4
24   -->   0 2
25   -->   5 4
26   -->   4 4
27   -->   7 5
28   -->   1 3
29   -->   3 4
30   -->   6 5
31   -->   0 3
32   -->   5 5
33   -->   2 4
34   -->   4 5
35   -->   7 6
36   -->   1 4
37   -->   3 5
38   -->   6 6
39   -->   0 4
40   -->   5 6
41   -->   2 5
42   -->   4 6
43   -->   1 5
44   -->   3 6
45   -->   0 5
46   -->   2 6
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

Assuming:

  • that your co-ords are in windows format ( increasing x moves left, increasing y move down )
  • the graph specified by your adjacencies is a single component ( every node is reachable from every other by traversing the links )
  • The grid distortion is limited so that no vector between adjacent nodes is close to 45 degrees from any axis, say in the range of 42 to 48 degrees.

Then the algorithm is:

  • find node with least x and least y. This will be the top left node of the grid.
  • Starting from the top left node, do a breadth first search
    • When you reach a new node, set its new location to that of its predecessor's new location plus or minus one of x or y, depending on which axis makes the smallest angle with the vector from predecessor to new ( vector of original locations ).
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.