Ctrl →

AnnaLischen · Апрель 28, 2015 21:18:33

Пытаюсь справиться с теорией графов. Написала алгоритм, нарисовала граф и блок схему (вариант проще: https://www.dropbox.com/s/e6ymisumg9mhccl/Block2.png?dl=0), но что-то не так. Я неправильно возвращаю результат.
Что пытаюсь сделать: установить кратчайший путь между вершиной и циклическим графом, при условии, что эта вершина либо уже в циклическом графе, либо соединена с ним напрямую, то есть через вершину, принадлежащую циклу, либо через другие вершины, которые таким же образом могут быть связаны с графом и находятся в списке вершин, которые с графом связываться могут.

По-моему, я неверно расставила return. Что не так? Как правильно?

Вот мой код, версия в который раз исправленная и дополненная:

arrWhatToConnect = ['F', 'G', 'N', 'X2', 'X3', 'K3', 'K1', 'K2', 'E']
#THERE IS NO X8!!!!!
arrWithWhatToConnect = [['A', 'B', 'C', 'D', 'E'], ['Z', 'P', 'L', 'Y']]
arrAllConnections = [['F', 'G'], ['G', 'F'], ['G', 'N'], ['N', 'G'], ['N', 'E'], ['E', 'N'], ['E', 'D'], ['D', 'E'], ['D', 'C'], ['C', 'D'], ['C', 'B'], ['B', 'C'], ['B', 'A'], ['A', 'B'], ['A', 'E'], ['E', 'A'], ['B', 'X8'], ['X8', 'B'], ['X8', 'X3'], ['X3', 'X8'], ['X3', 'X2'], ['X2', 'X3'], ['C', 'T'], ['T', 'C'], ['T', 'T1'], ['T1', 'T'], ['T1', 'Y'], ['Y', 'T1'], ['Y', 'L'], ['L', 'Y'],['L', 'P'], ['P', 'L'], ['P', 'Z'], ['Z', 'P'], ['Z', 'Y'], ['Y', 'Z'], ['L', 'K3'], ['K3', 'L'], ['Z', 'K1'], ['K1', 'Z'], ['K1', 'K2'], ['K2', 'K1']]
nullFirstConnect = []
#arrAllConnections = (sorted(item for item in arrAllConnections))
arrAllConnections = [list(i) for i in set(map(tuple, arrAllConnections))]
print(arrAllConnections, 'REMOVED?')
def visited(itemNext, arrConnect):
    return itemNext in arrConnect
def connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConnections, item, olderItems, mainItemOfConnection):
        arrAllConDel = arrAllConnections
        #print('CONTENTS OF TRUNCATED ARR CONNECTIONS', arrAllConDel)
        arrConnected = []
        arrVisited = []
        for cycle in arrWithWhatToConnect:
            print('ARRCONNECTED', arrConnected)
            if item in cycle:
                arrConnected.extend(cycle)
                arrConnected.extend(olderItems)
                print('My item in cycle', item, cycle, arrConnected, mainItemOfConnection)
                return set(arrConnected)
                #print('My item in cycle', item, cycle, arrConnected, mainItemOfConnection)
            #return set(arrConnected)
            else:
                if item in arrWhatToConnect:
                    #print('Not in cycle', item)
                    #print('GOING TO CHECK ELSEWHERE!')
                    olderItems.extend(item)
                    olderItems.extend(olderItems)
                    for connection in arrAllConnections:
                        item1 = connection[0]
                        item2 = connection[1]
                        if item in connection:
                            if item == item1:
                                #print('connection is', connection, 'item', item, 'item1', item1, 'item2', item2)
                                if item2 not in arrConnected:
                                        del arrAllConDel[arrAllConnections.index(connection)]
                                        connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConDel, item2, olderItems, mainItemOfConnection)
                                        return arrConnected
                                        #how to send previous item, so to let program know that it should be not just ring, but ring + item?
                            elif item == item2:
                                if item1 not in arrConnected:
                                            del arrAllConDel[arrAllConnections.index(connection)]
                                            connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConDel, item1, olderItems, mainItemOfConnection)
                                            return arrConnected
for item in arrWhatToConnect:
    print(item)
    print('CONNECTED CONNECTED CONNECTED', connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConnections, item, nullFirstConnect, item))

Отредактировано AnnaLischen (Апрель 28, 2015 21:38:14)

terabayt · Апрель 28, 2015 23:25:12

очень сложно читать код!
давайте так: вы опишите каждую строку, хорошо опишите
и тогда или вы сами поймете или мы вам поможем

————————————————
-*- Simple is better than complex -*-

Отредактировано terabayt (Апрель 28, 2015 23:25:25)

AnnaLischen · Апрель 28, 2015 23:58:31

Спасибо!!! Я просто в ужасе, работаю одна. Спасибо большое за ответ и возможность обсудить.
Начну с массивов:

arrWhatToConnect = ['F', 'G', 'N', 'X2', 'X3', 'K3', 'K1', 'K2', 'E']

Первый массив, массив разрешенных элементов, это те элементы, которые могут устанавливать соединение с циклами и/или через которые можно устанавливать соединение.
Пример (см картинка): вершина G может устанавливать соединение с циклом A,B,C,D,E через вершины G и N (и вершину E из цикла). То же справедливо для двух последних. Результатами для них будут массивы:

['A', 'B', 'C', 'D', 'E', 'N', 'G', 'F']; ['A', 'B', 'C', 'D', 'E', 'N', 'G'];['A', 'B', 'C', 'D', 'E', 'N']

соответственно. Но, для вершин X3, X2 такое решение невозможно, так как вершина X8 не входит ни в массив циклического графа, ни в массив “разрешённых элементов.”

Второй массив это массив массивов, где каждый подмассив содержит вершины отдельного циклического графа:

arrWithWhatToConnect = [['A', 'B', 'C', 'D', 'E'], ['Z', 'P', 'L', 'Y']]

Третий массив содержит попарные связи между вершинами

arrAllConnections = [['F', 'G'], ['G', 'F'], ['G', 'N'], ['N', 'G'], ['N', 'E'], ['E', 'N'], ['E', 'D'], ['D', 'E'], ['D', 'C'], ['C', 'D'], ['C', 'B'], ['B', 'C'], ['B', 'A'], ['A', 'B'], ['A', 'E'], ['E', 'A'], ['B', 'X8'], ['X8', 'B'], ['X8', 'X3'], ['X3', 'X8'], ['X3', 'X2'], ['X2', 'X3'], ['C', 'T'], ['T', 'C'], ['T', 'T1'], ['T1', 'T'], ['T1', 'Y'], ['Y', 'T1'], ['Y', 'L'], ['L', 'Y'],['L', 'P'], ['P', 'L'], ['P', 'Z'], ['Z', 'P'], ['Z', 'Y'], ['Y', 'Z'], ['L', 'K3'], ['K3', 'L'], ['Z', 'K1'], ['K1', 'Z'], ['K1', 'K2'], ['K2', 'K1']]

Так как фактически он дважды описывает одну и ту же связь я добавила эту строчку кода:

arrAllConnections = [list(i) for i in set(map(tuple, arrAllConnections))]

Таким образом сократив дубли.

Далее в самом низу, я начинаю работу с функцией, я перебираю вершины одну за другой, так как хочу получить все возможные результаты. И для каждой вершины вызываю функцию:

for item in arrWhatToConnect:
    print(item)
    print('CONNECTED CONNECTED CONNECTED', connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConnections, item, nullFirstConnect, item))

Собственно функция:

def connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConnections, item, olderItems, mainItemOfConnection):

принимает на вход массив циклов, массив разрешённых элементов (кстати, может содержать вершину из цикла), массив пар-связей между вершинами, элемент, который соединяется, массив предыдущих элементов (он используется в рекурсии, так он пуст, туда я складываю элементы удовлетворяющие условиям, но не связанные непосредственно с циклом, в случае вершины F в последний заход рекурсии он будет содержать F, G, N, а item будет E), наконец главный элемент/вершина ради которого/ой всё затевалось (в случае для вершины F это будет F)
Далее, открываем массив циклов:

for cycle in arrWithWhatToConnect:

Проверим не содержится ли наш элемент уже в цикле:

if item in cycle:
                arrConnected.extend(cycle)
                arrConnected.extend(olderItems)
                print('My item in cycle', item, cycle, arrConnected, mainItemOfConnection)
                return set(arrConnected)

Если да, то мы получим просто цикл (его должно вернуть, а массив предыдущих элементов - olderItems - пуст). Если нет - то пойдёт рекурсия до тех пор пока мы не найдём вершину из цикла через которую связан нециклический хвост вершин. Либо до тех пор пока не оборвётся цепочка (как в примере с Х2, Х3, Х8).
Если не в цикле:

else:

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

if item in arrWhatToConnect:

Если да, то продолжаем, теперь, надо ли добавить на этом уровне строчку:

else return None?

Далее ищем соседа с помощью массива пар-связей между вершинами:

for connection in arrAllConnections:

проходим вершины, вытаскиваем участников пары (их всегда два):

item1 = connection[0]
item2 = connection[1]

Это необходимо, чтобы мы могли сравнить наш элемент, узнать на какой он позиции и выбрать следующим элемент с противоположной позиции:

if item == item1:
                                #print('connection is', connection, 'item', item, 'item1', item1, 'item2', item2)
                                if item2 not in arrConnected:
                                        del arrAllConDel[arrAllConnections.index(connection)]
                                        connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConDel, item2, olderItems, mainItemOfConnection)
                                        return arrConnected
                                        #how to send previous item, so to let program know that it should be not just ring, but ring + item?
                            elif item == item2:
                                if item1 not in arrConnected:
                                            del arrAllConDel[arrAllConnections.index(connection)]
                                            connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConDel, item1, olderItems, mainItemOfConnection)
                                            return arrConnected

Так как у вершины может быть несколько соседей, то строка

if item2 not in arrConnected:

по идее должна проверить, нету ли в массиве arrConnected, который результат, в который уровнем выше мы добавили предыдущие элементы:

else:
                if item in arrWhatToConnect:
                    #print('Not in cycle', item)
                    #print('GOING TO CHECK ELSEWHERE!')
                    olderItems.extend(item)
                    olderItems.extend(olderItems)

Но на практике отчего-то не работает. Если наш новый элемент, элемент-сосед не прошёл по условию то цикл for просто даст соседа из следующей пары. Если же прошёл - будет рекурсия:

connect(arrWithWhatToConnect, arrWhatToConnect, arrAllConDel, item1, olderItems, mainItemOfConnection)

Вот здесь я ещё иным образом пыталась избавиться от уже пройденных пар:

del arrAllConDel[arrAllConnections.index(connection)]

удаляя пары из копии массива arrAllConnections, но и это не сработало. Хотя я кажется вижу ошибку в индексе. Главное, это то, что я передаю новый элемент и вызываю функцию внутри себя.

Отредактировано AnnaLischen (Апрель 28, 2015 23:59:11)

kamisama · Апрель 29, 2015 01:05:37

Что делает connect? Соединяет вершины только? Тебе известно про списки смежности?

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

Другими словами надо найти расстояние между вершиной графа A и циклическим графом B, являющимся подграфом графа A, да? Если вершина находится в графе B, то расстояние будет равно нулю?
Граф направленный?

AnnaLischen · Апрель 29, 2015 02:53:24

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

Отредактировано AnnaLischen (Апрель 29, 2015 03:11:05)

kamisama · Апрель 29, 2015 08:30:53

Ах да, путь. А по остальным вопросам?
С путем такой же вопрос почти: другими словами надо найти путь между вершиной графа A и циклическим графом B, являющимся подграфом графа A, да? Если вершина находится в графе B, то путь будет равен нулю (пустому списку)?
Или, как вы уже говорите, надо найти до любого ближайшего цикла?
Граф же статически задается, что подразумевается под словом “соединить”?

kamisama · Апрель 29, 2015 08:41:27

не проще разве задавать граф примерно так:

GRAPH = {
    'F' : ['G']
    'G' : ['F', 'N']
    'N' : ['G', 'E']
    'E' : ['N', 'D', 'A']
    ...
}

?

py.user.next · Апрель 29, 2015 09:08:49

Надо составить матрицу смежности и её анализировать.

AnnaLischen
Первый массив, массив разрешенных элементов, это те элементы, которые могут устанавливать соединение с циклами и/или через которые можно устанавливать соединение.

Это можно в матрице отразить, удалив ненужные вершины или их рёбра.

AnnaLischen
Третий массив содержит попарные связи между вершинами

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

AnnaLischen · Апрель 29, 2015 09:34:10

@kamisama это один из способов записи, именно способ записи, как мне кажется, не должен влиять на саму функцию

@py.user.next с моей точки зрения звучит довольно сложно, как это сделать я себе плохо представляю. А вы можете сказать что-то по моему коду? Я бы очень хотела именно его отладить. Как мне кажется, я нашла решение проблемы, но оно “почти работает”, убрать бы это почти))

py.user.next
Надо составить матрицу смежности и её анализировать.

py.user.next
Это можно в матрице отразить, удалив ненужные вершины или их рёбра

Но всё равно надо сначала понять какие рёбра и вершины можно и нужно удалять, кроме того, мне надо получить на выходе несколько массивов, т. е. для каждого разрешённого элемента (да, можно по очереди удалять те вершины и рёбра, которые соединены последовательно, но к циклу может быть привязан ещё какой-то “хвост” с другой стороны цикла, его простраивать заново?)

py.user.next
Лучше двумерный массив нулей и единиц обрабатывать, так как там не только легко найти для одной вершины все связи, но и поменять конфигурацию. Если простые линии не интересуют, их можно обнулить, чтобы они не участвовали в поиске.

Почему лучше?

kamisama · Апрель 29, 2015 10:28:00

AnnaLischen
Такой записью намного проще делать рекурсивный обход и функция займет несколько строк. А твой код лучше выкинуть и забыть как страшный сон.
Нужна еще постановка задачи в строгом виде — что дано и что найти. Ты почему-то в этом игнорируешь.
py.user.next говорит о матрице, но он это кажется неправильно говорит. Для матрицы алгоритм будет сложнее

Python-сообщество

Уведомления

#1 Апрель 28, 2015 21:18:33

Помогите, пожалуйста, с рекурсией

#2 Апрель 28, 2015 23:25:12

Помогите, пожалуйста, с рекурсией

#3 Апрель 28, 2015 23:58:31

Помогите, пожалуйста, с рекурсией

#4 Апрель 29, 2015 01:05:37

Помогите, пожалуйста, с рекурсией

#5 Апрель 29, 2015 02:53:24

Помогите, пожалуйста, с рекурсией

#6 Апрель 29, 2015 08:30:53

Помогите, пожалуйста, с рекурсией

#7 Апрель 29, 2015 08:41:27

Помогите, пожалуйста, с рекурсией

#8 Апрель 29, 2015 09:08:49

Помогите, пожалуйста, с рекурсией

#9 Апрель 29, 2015 09:34:10

Помогите, пожалуйста, с рекурсией

#10 Апрель 29, 2015 10:28:00

Помогите, пожалуйста, с рекурсией

Board footer