Сколько степеней разделения между двумя вершинами в триангуляции Делоне

Question

Я создал диаграмму Вороного, используя библиотеку Python scipy.spatial из набора точек LatLon, чтобы найти соседей каждой точки. Затем я обнаружил, что триангуляция Делоне была бы более полезной, и теперь я легко могу найти соседей «первого уровня» и «второго уровня» каждой точки, используя этот алгоритм:

def findNeighbors(delaunay):
    "Returns a adjacency list of the graph"
    neighbors = defaultdict(set)

    for simplex in delaunay.simplices:
        for vertice in simplex:
            other = set(simplex)
            other.remove(vertice)
            neighbors[vertice] = neighbors[vertice].union(other)
    return neighbors

def neighborCount(graph, start, target):
    if target in graph[start]:
        return 'First Tier Neighbor'
    elif graph[start] & graph[target]:
        return 'Second Tier Neighbor'

Но проблема в том, что мне нужно найти «соседа 6-го уровня», и я не могу найти способ сделать это, не просматривая весь список смежности. Вот пример "Соседа 3-го уровня", который я хочу найти.

Есть ли более умный способ сделать это?

Answer 1

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

def getNeighbor(neighbors, graph):
    out = set()
    for neighbor in neighbors:
        out = out.union(graph[neighbor])
    return out 


def tier_count(graph, start, target):

    if target in graph[start]:
        return "1 tier"

    else:  
        visited = set()
        queue = getNeighbor(graph[start], graph)
        count = 2

        while queue:
            if target in queue:
                return str(count) + " Tier'

            else:
                count += 1
                visited = visited.union(queue)
                queue = getNeighbor(queue, graph) - visited

    return "No tiers between these cells"