Блог

для ориентированного графа у меня есть ограничение, которое заключается в том, что матрица смежности A должна быть верхней треугольной с диагональю 0 (утверждение ациклического условия). Теперь предположим, что я произвольно изменил порядок узлов, так что новая матрица смежности B больше не является верхней треугольной. Я хочу восстановить A треугольную матрицу B . У меня может быть матрица как numpy.array pandas.DataFrame объект or, поэтому я ищу решение в этих библиотеках.

Пока мое решение выглядит следующим образом:

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

вот код:

 def sort_nodes(adj_matrix: np.ndarray = None):
    ordered_list = []
    covered_nodes = 0
    while covered_nodes < adj_matrix.shape[0]:
        # sum of the columns
        sum_c = adj_matrix.sum(axis=0)
        # find nodes with no parents: sum should be zero
        parent_inds = list(np.where(sum_c == 0)[0])

        # an assertion to make sure the matrix can be sorted triangular
        assert len(parent_inds) != 0
        
        # update the while condition
        covered_nodes  = len(parent_inds)
        # add to the list
        ordered_list  = parent_inds

        # remove parent edges by set the corresponding row to zero
        adj_matrix[parent_inds, :] = 0
        # eliminate from columns by assigning values so that its sum cannot be zero
        adj_matrix[:, parent_inds] = 10
    return ordered_list
  

есть ли какое-либо решение для этого? функция или более краткий алгоритм. Я также поцарапал поверхность библиотек графов, таких как networkx , но ничего не нашел… Приветствия!

РЕДАКТИРОВАТЬ: 1

Примером такой проблемы является:

 A:
   1  2  3  4
1[[0, 1, 1, 1]
2 [0, 0, 1, 1]
3 [0, 0, 0, 1]
4 [0, 0, 0, 0]]

B:
   2  1  4  3
2[[0, 0, 1, 1]
1 [1, 0, 1, 1]
4 [0, 0, 0, 0]
3 [0, 0, 1, 0]]
  

где A — полная последовательная база данных. (полностью подключен настолько, насколько позволяет ациклическое условие)

Чтобы мое pandas решение работало, добавьте столбец из всех единиц в dataframe (чтобы избежать строки со всеми нулями):

 df = pd.DataFrame([[0,1,1,0],[0,0,0,1],[0,0,1,1],[0,0,0,0]])
df.loc[:, df.shape[1]] = 1
  

Теперь вы можете найти индекс крайнего левого 1 в каждой строке. Чем меньше индекс, тем выше была строка в исходной неперестановленной матрице. Наконец, отсортируйте строки по этой позиции и удалите последний столбец из 1s:

 df = df.reindex(df.idxmax(1) - 1).iloc[:,:-1]
#   0  1  2  3
#0  0  1  1  0
#2  0  0  1  1
#1  0  0  0  1
#3  0  0  0  0