Удалить ненужные пары из рефлексивного асимметричного транзитивного отношения - PullRequest
Новая
       68

Удалить ненужные пары из рефлексивного асимметричного транзитивного отношения

0 голосов
/ 22 октября 2019

У меня рефлексивное асимметричное транзитивное отношение, представленное в виде n x n разреженной scipy csr матрицы.

Теперь в результате некоторых преобразований у меня осталось много «ненужных»пары: 

set([('a','b'),('b','c'),('a','c')])

Мне нужно удалить пары ('a','c'), которые можно рассматривать как «прямые» ребра, когда есть «косвенные».

Сначала я подумал, что это особый охватывающее древовидность , но фактически в следующем случае: 

set([('a','b'),('b','d'),('a','c'),('c','d')])

... ни одна пара не должна быть удалена. Результатом не обязательно является дерево.

  • Есть ли название для такого рода проблемы?

  • Есть ли реализация в scipy?

  • Если нет, можете ли вы предложить эффективный алгоритм в python / numpy / scipy?

РЕДАКТИРОВАТЬ: Похоже, это называется переходное сокращение ? Но реализации scipy.sparse.csgraph нет?

РЕДАКТИРОВАТЬ: Я думаю, чтобы получить ациклический ориентированный граф, мне пришлось бы (временно) удалить «рефлексивность», но этоне проблема.

1 Ответ

0 голосов
/ 22 октября 2019

Таким образом, проблема называется Транзитивное сокращение ориентированного ациклического графа.

Следующий код должен решить проблему, хотя она может быть далека от оптимальной: 

def transitive_reduction(edges): # edges is irreflexive and scipy sparse bool
    reduction = edges.copy()
    num, i    = 99,2
    while num > 0:
        new        = edges**i
        num        = len(new.nonzero()[0])
        reduction  = reduction > new
        i         += 1
        reduction.eliminate_zeros() # might or might not be required
    return reduction

Объяснение: Пока существуют пути этой длины, мы удаляем из reduction все прямые пути, для которых существуют косвенные пути длины i.

Кредиты для @ PaulPanzer.

...