Networkx - 查找蜂窝结构中的各个六边形

Question

我正在研究这个蜂窝状结构网络，它是通过遵循此线程中接受的答案生成的：networkx 的不同层中的六角形晶格

为方便起见，复制如下：

def node_dist(x,y, cx, cy):
    """Distance of each node from the center of the innermost layer"""
    return abs(cx-x) + abs(cy-y)


def remove_unwanted_nodes(G, m):
    """Remove all the nodes that don't belong to an m-layer hexagonal ring."""
    
    #Compute center of all the hexagonal rings as cx, cy
    cx, cy = m-0.5, 2*m -(m%2) #odd is 2m-1, even is 2m
    
    #in essence, we are converting from a rectangular grid to a hexagonal ring... based on distance.
    unwanted = []
    for n in G.nodes:    
        x,y = n
        #keep short distance nodes, add far away nodes to the list called unwanted
        if node_dist(x,y, cx, cy) > 2*m:
            unwanted.append(n)

    #now we are removing the nodes from the Graph
    for n in unwanted:
        G.remove_node(n)
        
    return G

m = 2 #change m here. 1 = 1 layer, single hexagon.
G = nx.hexagonal_lattice_graph(2*m-1,2*m-1, periodic=False, 
                               with_positions=True, 
                               create_using=None)
pos = nx.get_node_attributes(G, 'pos')
G = remove_unwanted_nodes(G, m)

#render the result
plt.figure(figsize=(4,4)) 
nx.draw(G, pos=pos, with_labels=True)
plt.axis('scaled')
plt.show()

这会产生这样的情节：

如何找到形成这个蜂窝的所有单独的六边形？

我尝试过循环、派系和连锁，但它们似乎都没有给我我想要的答案......除非我做错了什么。

如有任何帮助，我们将不胜感激！

Answer 1

我相信

nx.simple_cycles()

是您想要的，但如果您尝试在无向图上调用它，则会收到错误消息，指出该算法未针对此图类型实现。

以下方法不太优雅，如果您需要的话，可能无法很好地扩展，但它达到了预期的结果。您可以将无向图转换为有向图，这只是将所有无向边替换为两个有向边，每个方向一个。然后，您可以对其调用

nx.simple_cycles()

，限制长度为 6 的循环，并根据每个循环中存在的节点集对 6 个循环进行重复数据删除：

DG = G.to_directed()
cycles = nx.simple_cycles(DG)
hex_cycles = [path for path in cycles if len(path) == 6]
hex_loops = []
for cycle in hex_cycles:
    if set(cycle) not in [set(loop) for loop in hex_loops]:
        hex_loops.append(cycle)

根据需要给出

hex_loops

：

[[(3, 4), (2, 4), (2, 5), (2, 6), (3, 6), (3, 5)],
 [(3, 4), (2, 4), (2, 3), (2, 2), (3, 2), (3, 3)],
 [(0, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 3)],
 [(0, 5), (0, 6), (1, 6), (1, 5), (1, 4), (0, 4)],
 [(2, 2), (2, 3), (1, 3), (1, 2), (1, 1), (2, 1)],
 [(2, 4), (2, 5), (1, 5), (1, 4), (1, 3), (2, 3)],
 [(2, 7), (1, 7), (1, 6), (1, 5), (2, 5), (2, 6)]]

Answer 2

对于大量的六边形单元，Frodnar 给出的解决方案非常慢，即使对于简单的 m x n 单元配置也是如此。六边形格子充满了结构，因此我们可以遍历格子的每一水平行并根据您研究的图案创建六边形。让

import networkx as nx

M, N = 4, 4 # try higher dimensions
g = nx.hexagonal_lattice_graph(M, N, False)
θ = -np.pi / 2
A = np.array([
        [cos(θ), -sin(θ)],
        [sin(θ), cos(θ)]
    ])
# Rotate the lattice to see the order of the nodes as we read
# from top to bottom, left to right.
for node in g.nodes:
    g.nodes[node]['pos'] = tuple(A @ np.array(g.nodes[node]['pos']))

pos = nx.get_node_attributes(g, 'pos')

hex_cells = get_hex_cells(M, N, g)

# get_hex_cells(M,N,g)

def get_hex_cells(M, N, g):
    """
    :param M: M rows for the hexagonal lattice
    :param N: N rows [...]
    :param g: The hexagonal lattice object
    :return: A list containing all the nodes for individual hexagons                           inside lists. The first list is the first hexagon and so on.
             Not fully tested for arbitrary M, N, it works well for NxN. You might need to adjust the code depending on the structure of the lattice.     
    """
    nodes = list(g.nodes)
    k = 2 * N + 1
    i, j = 0, k
    hex_cells = []
    for m in range(M):
        row0 = nodes[i:j]
        row1 = nodes[j:j + k + 1]
        if (m + 1) % 2 != 0:
            if len(row0) < len(row1):
                top_row = row0
                bottom_row = row1[:-1]
                hex_cells += [top_row[2*n:2*n+3] + bottom_row[2*n:2*n+3] for n in range(M)]
            else:
                top_row = row0[:-1]
               enter code here bottom_row = row1[:-1]
                hex_cells += [top_row[2*n:2*n+3] + bottom_row[2*n:2*n+3] for n in range(M)]

        else:
            if len(row0) == len(row1):
                top_row = row0[1:]
                bottom_row = row1[1:]
                hex_cells += [top_row[2*n:2*n+3] + bottom_row[2*n:2*n+3] for n in range(M)]

            else:
                top_row = row0[1:]
                bottom_row = row1
                hex_cells += [top_row[2*n:2*n+3] + bottom_row[2*n:2*n+3] for n in range(M)]
        i = j
        j += k + 1

    return hex_cells