Python - [p-cycles] ** небольшой код для большой работы
Primary tabs
Итак, сегодня я продемонстрирую как была решена задача нахождения p-cycles (п-циклов) в WDM сетях (магистральных, оптических).
План таков:
-- для начала определимся что такое эти p-cycles, и каков алгоритм их нахождения, после подробно рассмотрим код на Питоне, который по-своему решает данную задачу. Заметка эта длинная, не для слабонервных и, возможно, будет создаваться в несколько присестов. Итак, поехали, под кат.
Статья требует базового знания Python. Но можно насладиться и без этакого знания.
------ Часть 1: P-cycles. ------
Всё наш рассуждение будет отталкиваться от данного рисунка:
Итак, мне суждено было заняться разработкой алгоритма построения п-циклов (модное название, которое сейчас в неких Российских кругах выдаётся за нечто особое), по сути, как я понял, p-cycle - это сокращение от protection cycle (цикл защиты). То есть, любой цикл на графе, иллюстрирующим топологию рассматриваемой сети, можно назвать p-cycle. Ха, тут я расслабился, построю любой цикл - и назову его "П")) Но стало мне интересно, какой же смысл вкладывают в это слово спецы?
Итак, в WDM ячеистых сетях, которые перетаскивают огромные потоки данных, и выполненные на основе дорогостоющего оптоволокна необходимо создать резервные мощности. Вот для такой задачи и созданы p-циклы. Дело в том, что при обрыве линий связи очень сложно переконфигурировать всю систему, это довольно долго - строить новые маршруты, поэтому нужна система которая практически мгновенно отреагирует. И тут, строим по принципу FDDI защитное кольцо. На рисунке красные узлы и красные соединения как раз и показывают наш защитный цикл. И если произойдёт обрыв (это также показано на рисунке), то достаточно просто замкнуть на себя (выходы на входы - loopback) конечные узлы, между которыми был обрыв. И тогда при обрые, если узел 1 пошлёт сообщение узлу 7 через узел 5, то сообщение дойдёт до узла 5, там "развернётся" пойдёт по кольцу обратно и дойдёт до узла 7, при этом нам никак не пришлось переконфигурировать маршруты на всех узлах - для глобальных сетей это удобно - Правда?
Итак, самый наверное малоэффективный, но и самый надёжный p-cycle - это Гамильтонов цикл ( цикл, содержащий все вершины ровно один раз), но это дорого. Что же делать? А давайте некоторые узлы обойдём. Эти узлы на рисунке синенькие. Ведь, скажем, если у узла 6 оборвётся линия связи с узлом 7, то остаётся связь с узлом 2, что нас вполне устраивает, а узел 2 состоит в нашем цикле. Вот на таких соображениях и основаны разные пути оптимизации p-cycle. По этому поводу есть много публикаций и диссертаций. Я не берусь за рассказ и реализацию многих методов которые я встречал. Моей задачей было построить что-то более эффективное чем гамильтонов цикл, и без всяких критериев оптимизации, об этом я и расскажу далее.
------ Часть 2: Алгоритм поиска p-cycle-ов------
Смотрим на наш рисунок, в предлагаемом мною алгоритме для начала нужно выделить случайный отправной узел - пусть 1. После чего создаём список всех смежных с ним узлов, и выбираем первый попавшийся узел, который имеет общий смежный узел с исходным узлом. Этот общий помечается как трансграничный, а выбранный, становится новым исходным и всё повторяется - это в двух словах весь алгоритм.
-------Часть 3: реализация на Python ----------
Сначала приведу весь код - не пугайтесь если он непонятен и без подробных комментариев, они будут чуть дальше, а пока тот код, который лежит у меня))) Просто для начала окиньте всё взглядом.
"""
This module find p-cycles in Graph
"""
import random
#-----------------------------------------------------------------------------
def takeTestMatrix(n=10):
GMatrix = [[(random.randint(0, 1) if j != i else 0)
for j in range(i + 1)] for i in range(n)]
for i in range(n):
for j in range(i + 1, n):
GMatrix[i].append(GMatrix[j][i])
return GMatrix
#-----------------------------------------------------------------------------
#-----------------------------------------------------------------------------
def MakeP_Cycle(GMatrix):
"""functioin to search p_cycle in graf
parametr GMatrix - target graf - it should be matrix nXn
function returns list of nodes witch contains p_cycle or take interrapt"""
N = len(GMatrix)
FreeNodesSet = {i for i in range(N)}
TransNodedSet = set()
p_cycle = []
#take first node
FirstNode = random.randint(0, N - 1)
FreeNodesSet.remove(FirstNode)
p_cycle.append(FirstNode)
#-----------------------------------------
def EndingFind(currentNode):
"""
check, if current node have direct link to first node
- then return ending p-cycle,
else it check if node have link to first node throught transnode
- return p-cycle,
else return FIND_ERROR interrupt
"""
if GMatrix[currentNode][FirstNode] == 1:
p_cycle.append(FirstNode)
return
buf1 = {node for node in range(N) if GMatrix[FirstNode][node] == 1}
buf2 = {node for node in range(N) if GMatrix[currentNode][node] == 1}
if buf1 & buf2:
buf = buf1 & buf2
currentNode = [node for node in buf if node in TransNodedSet]
if currentNode:
p_cycle.append(currentNode[0])
p_cycle.append(FirstNode)
TransNodedSet.remove(currentNode[0])
return
else:
p_cycle.append('ERROR')
return
#-----------------------------------------
def addNextNode(currentNode):
"""find and add to p_cycle next node"""
print('call addNextNode')
CurrLikeNodes = [node for node in range(N) if
(node in FreeNodesSet) & (GMatrix[currentNode][node]
== 1)]
if len(CurrLikeNodes) == 0:
EndingFind(currentNode)
return
for i in range(len(CurrLikeNodes)):
takenTransNode = CurrLikeNodes[i] # take node wich can be transnode
#find nodes has direct link to takentransnode and sit in CurrLikeNodes list:
buf = [node for node in CurrLikeNodes if (node !=
takenTransNode) & (GMatrix[node][takenTransNode] == 1)]
if buf:
FreeNodesSet.remove(takenTransNode)
TransNodedSet.add(takenTransNode)
currentNode = random.choice(buf)
FreeNodesSet.remove(currentNode)
p_cycle.append(currentNode)
print('--debug: ', currentNode)
break
else:
currentNode = random.choice(CurrLikeNodes)
FreeNodesSet.remove(currentNode)
p_cycle.append(currentNode)
print('--debug: ', currentNode)
addNextNode(currentNode)
#-----------------------------------------
addNextNode(FirstNode)
print('--debug: ', FreeNodesSet)
print('--debug: ', TransNodedSet)
print('--debug: p-cycle ', p_cycle)
return (p_cycle, FreeNodesSet, TransNodedSet)
#------------------------------------------------------------------------------
if __name__ == '__main__':
#initialize test graf
n = 10
GMatrix = takeTestMatrix(n)
#end init GMatrix
#ptint test matrix:
for i in range(n):
print(GMatrix[i])
#test func
#testM = [[0,1,0,0,1],[1,0,1,0,1],[0,1,0,1,0],[0,0,1,0,1],[1,1,0,1,0]]
p_c = MakeP_Cycle(GMatrix)
print('result:')
print(p_c)
Итак, начнём с самого первого и простого кусочка - это генерация тестовой матрицы. Дело в том, что код работает с матрицой смежности, а так как у меня невзвешанный двунаправленный граф, то надо сгенерировать симметричную матрицу смежности с нулями на главное диагонали.
Итак, вот эта функция:
#----------------------------------------------------------------------------- def takeTestMatrix(n=10): GMatrix = [[(random.randint(0, 1) if j != i else 0) for j in range(i + 1)] for i in range(n)] #этим одним выражением формируем нижнетреугольную матрицу for i in range(n): #а эти циклы служат для дублирования элементов и формирования for j in range(i + 1, n): # полной квадратной матрицы GMatrix[i].append(GMatrix[j][i]) #просто добавляя элементы return GMatrix #-----------------------------------------------------------------------------
Рассмотрим чуть подробнее выражение генерации нижнетреугольной матрицы, оно мне нравится за лаконичность и показыает удобство использование генераторов списков:
GMatrix = [[(random.randint(0, 1) if j != i else 0) for j in range(i + 1)] for i in range(n)]
Здесь два вложенных генератора списков, внешний генерирует список списков, и перебирает строки от 0 до n, а внутренний генерирует уже внутренние списки - как бы строки, из случайных числе, выбраных из двух вариков - 1 или 0, при этом проверяется, если это диагональ, то ставится 0.
Далее, сама функция нахождения p-cycl-ов:
#-----------------------------------------------------------------------------
def MakeP_Cycle(GMatrix):
"""functioin to search p_cycle in graf
parametr GMatrix - target graf - it should be matrix nXn
function returns list of nodes witch contains p_cycle or take interrapt"""
N = len(GMatrix) #храним количество узлов
FreeNodesSet = {i for i in range(N)} #создаём и инициализируем с помощью генератора множеств множество
#неиспользованных узлов
TransNodedSet = set() #множество трансграничных узлов
p_cycle = [] #список, п-цикл
#take first node
FirstNode = random.randint(0, N - 1) #выбираем случайный стартовый узел
FreeNodesSet.remove(FirstNode) #соотвественно изменяем наши множества
p_cycle.append(FirstNode)
#-----------------------------------------
def EndingFind(currentNode): #функция окончания поиска, пока можно её порсто порсмотреть
"""
check, if current node have direct link to first node
- then return ending p-cycle,
else it check if node have link to first node throught transnode
- return p-cycle,
else return FIND_ERROR interrupt
"""
if GMatrix[currentNode][FirstNode] == 1:
p_cycle.append(FirstNode)
return
buf1 = {node for node in range(N) if GMatrix[FirstNode][node] == 1}
buf2 = {node for node in range(N) if GMatrix[currentNode][node] == 1}
if buf1 & buf2:
buf = buf1 & buf2
currentNode = [node for node in buf if node in TransNodedSet]
if currentNode:
p_cycle.append(currentNode[0])
p_cycle.append(FirstNode)
TransNodedSet.remove(currentNode[0])
return
else:
p_cycle.append('ERROR')
return
#-----------------------------------------
def addNextNode(currentNode): # самая главная рекурсивная функция, её объвление, обсудим позже
"""find and add to p_cycle next node"""
print('call addNextNode')
CurrLikeNodes = [node for node in range(N) if
(node in FreeNodesSet) & (GMatrix[currentNode][node]
== 1)]
if len(CurrLikeNodes) == 0:
EndingFind(currentNode)
return
for i in range(len(CurrLikeNodes)):
takenTransNode = CurrLikeNodes[i] # take node wich can be transnode
#find nodes has direct link to takentransnode and sit in CurrLikeNodes list:
buf = [node for node in CurrLikeNodes if (node !=
takenTransNode) & (GMatrix[node][takenTransNode] == 1)]
if buf:
FreeNodesSet.remove(takenTransNode)
TransNodedSet.add(takenTransNode)
currentNode = random.choice(buf)
FreeNodesSet.remove(currentNode)
p_cycle.append(currentNode)
print('--debug: ', currentNode)
break
else:
currentNode = random.choice(CurrLikeNodes)
FreeNodesSet.remove(currentNode)
p_cycle.append(currentNode)
print('--debug: ', currentNode)
addNextNode(currentNode)
#-----------------------------------------
addNextNode(FirstNode) # вызов главной рекурсивной функции, что мы выше объявили, для первого узла.
print('--debug: ', FreeNodesSet)
print('--debug: ', TransNodedSet)
print('--debug: p-cycle ', p_cycle)
return (p_cycle, FreeNodesSet, TransNodedSet)
#------------------------------------------------------------------------------
Итак, в общем ознакомившесь с кодом алгоритма приступим к разбору основной рекурсивной функции:
Она ищет следующий подходящий узел для включения в п-цикл. Листинг ниже.
- Сначала она создаёт список узлов смежных с исходным (исходный передаётся в аргументе) - это список CurrLikeNodes. Посмотрите, опеть сделано одним генератором списков - одна строчка, на С++ убил бы много тараканов на клавиатуре))) Тут просто, перебираем все номера узлов и включаем их в список если эти номера есть в множестве свободных (незадействованных) узлов, а также они смежны с исходным
- Потом, учитываем что список дальнейших подходящих узлов может быть пуст и тогда нам нужно вызвать процедуру корректного завершени работы алгоритма. Но не в этом соль, потом помечаем один первый узел как трансграничный и смотим, а правда ли это, если ли ещё узлы которые смежны как с нашим исходным так и с помеченныйм (опять генерируем список), и если этот список не пуст, то преобразуем наши множества и случайным образом выбираем следующий узел из списка подходящих.
-- Обратите внимание, что если мы нашли трансграничные узлы, то цикл for завершится с помощью команды break - это значит, что следующий блок else, относящийся к for не будет выполняться, а если мы не найдём трансграничных узлов, то в этом случае цикл завершится щтатно и блок else выполнится. Таким образом без всяких флагов и проверок, лаконично определили. бы ли ли найдены трансграничные узлы и соотвествено отреагировали. - Потом вызываем нашу рекурентную функцию уже для свежевыбранного исходного узла.
А теперь листинг данной функции:
#-----------------------------------------
def addNextNode(currentNode):
"""find and add to p_cycle next node"""
print('call addNextNode')
CurrLikeNodes = [node for node in range(N) if
(node in FreeNodesSet) & (GMatrix[currentNode][node]
== 1)] # формируем список смежных узлов исходному
if len(CurrLikeNodes) == 0: #если список удовлетворяемых узлов пуст
EndingFind(currentNode) #вызываем функцию завершения (о ней потом)
return
for i in range(len(CurrLikeNodes)): #ищем трансграничные узлы
takenTransNode = CurrLikeNodes[i] # take node wich can be transnode
#find nodes has direct link to takentransnode and sit in CurrLikeNodes list:
buf = [node for node in CurrLikeNodes if (node !=
takenTransNode) & (GMatrix[node][takenTransNode] == 1)] #смотрим список узлов, которые делают
#вышевыбранный трансграничным
if buf: #если список не пуст значит:
FreeNodesSet.remove(takenTransNode) #выбранный трансграничным узел действительно такой
#вырезаем его из множества свободных
TransNodedSet.add(takenTransNode) #помещаем в множество трансграничных
currentNode = random.choice(buf) #случайно выбираем следующий исходный узел
FreeNodesSet.remove(currentNode) #ну и добавляем в п-цикл с вырезание из свободных
p_cycle.append(currentNode)
print('--debug: ', currentNode)
break
else: #этот else относится к циклу
currentNode = random.choice(CurrLikeNodes) #если не нашли трансграничных, тупо берём из списка смеж.
FreeNodesSet.remove(currentNode)
p_cycle.append(currentNode)
print('--debug: ', currentNode)
addNextNode(currentNode) #рекурсивный вызов
#-----------------------------------------
Функция завершения не представляет особого интереса, она просто выполняет проверку того, что п-цикл получился замкнут и замыкает его, либо ищет как его замкнуть использую трансграничные узлы))) Вот реализация поиска узла, через которого можно замкнуть п-цикл довольно интересна, она создаёт множества и оперирует ими, и код получился очень маленький, а по сути он совершает большую работу. Для реализации этого на C++ я бы убил не просто тучу жуков на клавиатуре, а целое полчище)))
--
Just Fun!!!
- Log in to post comments
- 3992 reads