Блог

У меня есть список списков (всего 10 элементов), и я пытаюсь вычислить количество сильно связанных компонентов на графике (но не беспокойтесь об этом).

Вот как выглядит мой список:

 df_reversed_back =[[9, 7],
 [8, 9],
 [7, 8],
 [6, 9],
 [6, 4],
 [5, 6],
 [4, 5],
 [3, 5],
 [3, 1],
 [2, 3],
 [1, 2]]
  

где первый элемент внутреннего списка — это вершина номер один [9], а второй элемент — вторая вершина [7].

Моя проблема в том, что при вызовах рекурсии я добавляю список к списку, который существует вне функции.

 all_components = []
SSC = []
explored= []
#c)modification of DFS
def DFS_2_Path(graph,node):
    #global SSC
    global all_components
    explored.append(node)
    print('Node:',node)
    #index = [ind for ind,vertex  in enumerate(df_reverse) if vertex[0] == node]
    for second_vert in graph:
        print('Second_vert:',second_vert)
        print('Second_vert[0] == node:',second_vert[0] == node)
        if second_vert[0] == node:
            print('second_vert[1] not in explored :',second_vert[1] not in explored)
            if second_vert[1] not in explored:
                print('SSC was:',SSC)
                SSC.append(second_vert[1])
                print('SSC is:',SSC)
                print('---------------------------------')
                print('NEXT ITERATION OF THE INNER LOOP')
                print('-------------------------------------')
                DFS_2_Path(graph,second_vert[1])
            if second_vert[1] in explored and len(SSC)> 0 :#check if second vert is not explored and if it's not a new SSC
                print('SSC was:',SSC)
                SSC.append(second_vert[1])
                print('SSC is:',SSC)

                all_components.append(SSC)
                print('All_components is :',all_components)
                SSC[:] = []

    print('All_components was:',all_components)


for i in range(max(df_reversed_back[0]),0,-1):
    if i not in explored:
        s = i
        DFS_2_Path(df_reversed_back,i)
  

Как вы видите, я хочу добавить SSC ко всем_компонентам.
Результат должен быть: all_components = [[7, 8, 9], [4, 5, 6], [1, 2, 3]]

Но в конце я получаю: all_components =[[], [], []]

Можете ли вы сказать мне, где я допустил ошибку?

Вы уничтожаете содержимое SSC , когда делаете это:

 all_components.append(SSC)
print('All_components is :',all_components)
SSC[:] = []
  

Это эффективно добавляет ссылку на SSC на all_components , а затем удаляет содержимое массива, на который указывает глобальная переменная.

Возможно, лучший способ — создать новый SSC, когда это необходимо, включив его в качестве параметра в функцию.

Вы можете заставить свою функцию читать:

 def DFS_2_Path(graph,node, SSC=None):
    if SSC == None:
        SSC = []
  

Затем, когда вы вызываете его рекурсивно, передайте его в рекурсию с:

 DFS_2_Path(graph,second_vert[1], SSC)
  

Это позволит каждому рекурсивному пути получить свой собственный SSC массив, и в качестве бонуса вам не понадобится глобальная переменная.

Ваша проблема здесь:

             all_components.append(SSC)
            print('All_components is :',all_components)
            SSC[:] = []
  

Вы создаете SSC элемент all_components , но сразу же очищаете его. Это оставляет all_components в виде списка, содержащего пустой список. Затем вы продолжаете использовать основной список (SSC) для манипуляций. Вы можете увидеть это в своем выводе:

 SSC was: [1, 2]
SSC is: [1, 2, 3]
All_components is : [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Second_vert: [1, 2]
Second_vert[0] == node: False
All_components was: [[], [], []]
All_components was: [[], [], []]
  

Каждый элемент является просто ссылкой на оригинал SSC : вы видите его как триплеты, являющиеся либо пустыми, либо конечным компонентом.

Я подозреваю, что вы хотели, чтобы был добавлен снимок (копия) SSC :

             all_components.append(SSC[:])
            print('All_components is :',all_components)
            SSC[:] = []
  

Вывод:

 ...
All_components was: [[7, 8, 9], [4, 5, 6], [1, 2, 3]]