Найти граничные петли в смежности с помощью разреженной разреженной матрицы (python) - PullRequest
Новая
       9

Найти граничные петли в смежности с помощью разреженной разреженной матрицы (python)

0 голосов
/ 02 февраля 2019

Мне нравится находить петли в матрице направленной смежности.Матрица разреженная, содержит 1 в (i, j) направленном ребре от i -> j.Других ребер и одного или нескольких непересекающихся циклов / петель нет.

Изначально у меня была треугольная сетка с ориентированными треугольниками, и я создал матрицу смежности, а затем удалил внутренние ребра (это было сделано путем созданиянаправленная симметричная прилегающая матрица, поиск внутренних ребер со значением = 2 и удаление их из направленной (несимметричной) прилегающей матрицы).Если сетка многообразна (что я тестировал ранее), граничные ребра будут образовывать отдельные граничные петли.Есть ли эффективный способ найти все эти циклы из разреженной матрицы в Python?

Идея состоит в том, чтобы найти первый ненулевой столбец.Получить индекс входа, затем взять столбец с этим индексом, пока мы снова не достигнем первого индекса.Регистрация записей завершит цикл, а установка записей данных на ноль удалит этот цикл из матрицы, а затем перейдет к следующему циклу.Я также думал об итеративном умножении столбца (начало) на матрицу, пока мы не получим запись в строке (начало).

def tria_get_boundary(t):
    import numpy as np
    adj = tria_get_adj(t, directed=False)
    if (np.max(adj.data) > 2):
        raise ValueError('Error: tria not manifold (edges with more than 2 triangles)!')
    if (1 not in adj.data):
        return []  
    # get directed matrix of only boundary edges
    inneredges = (adj==2)
    adj = tria_get_adj(t,directed=True)
    adj[inneredges] = 0
    adj.eliminate_zeros()
    # find loops
    firstcol = np.nonzero(adj.indptr)[0][0]-1
    loops=[]
    while not firstcol == []:
        loop = [firstcol]
        adj.data[adj.indptr[firstcol]] = 0 # visited
        ncol =adj.indices[adj.indptr[firstcol]]
        while not ncol == firstcol:
            loop.append(ncol)
            adj.data[adj.indptr[ncol]] = 0 # visited
            ncol = adj.indices[adj.indptr[ncol]]
        adj.eliminate_zeros()
        loops.append(loop)
        nz = np.nonzero(adj.indptr)[0]
        if len(nz) > 0:
            firstcol = nz[0]-1
        else:
            firstcol=[]
    return loops

Может ли это быть сделано более эффективно (или более питонно)?Спасибо.

...