Использование словарей для представления графов эффективно: поиск смежных узлов выполняется быстрой операцией хеширования. Но для некоторых приложений более оправданными могут оказаться другие представления. Например, для моделирования узлов в сети могут также использоваться классы, как и для двоичных деревьев в более раннем примере. Узлы, реализованные в виде классов, могут содержать дополнительную информацию, полезную при более сложном поиске. Они могут также участвовать в иерархиях наследования и приобретать дополнительные особенности поведения. Для иллюстрации этой идеи в примере 18.19 показана альтернативная реализация поиска на графе — используемый алгоритм ближе всего к gsearchl.
Пример 18.19. PP4E\Dstruct\Classics\graph.py
"конструирует граф из объектов, способных выполнять поиск"
class Graph:
def __init__(self, label, extra=None):
self.name = label # узлы = объекты экземпляров
self.data = extra # граф = связанные объекты
self.arcs = []
def __repr__(self): return self.name
def search(self, goal):
Graph.solns = []
self.generate([self], goal)
Graph.solns.sort(key=lambda x: len(x))
return Graph.solns
def generate(self, path, goal):
if self == goal: # класс == цель
Graph.solns.append(path) # или self.solns: то же самое else:
for arc in self.arcs:
if arc not in path:
arc.generate(path + [arc], goal)
В этой версии графы представляются как сеть вложенных объектов экземпляров класса. Каждый узел в графе содержит список объектов узлов, к которым он ведет (arcs) и в котором он умеет выполнять поиск. Метод generate выполняет обход объектов в графе. Но на этот раз переходы прямо доступны в списке arcs каждого узла — нет необходимости индексировать (или передавать) словарь, чтобы найти связанные объекты.
Для проверки в примере 18.20 представлен модуль, который снова строит контрольный граф, на этот раз с помощью связанных экземпляров класса Graph. Обратите внимание на вызов функции exec в коде самотестирования: он выполняет динамически создаваемые строки, чтобы осуществить семь присваиваний (A=Graph(‘A’), B=Graph(‘B’) и так далее).
Пример 18.20. PP4E\Dstruct\Classics\gtestobj1.py
"создает граф на основе класса и выполняет контрольный поиск"
from graph import Graph
# этот фрагмент не работает внутри инструкции def в 3.1: B — не определено
for name in "ABCDEFG": # создать сначала объект
exec("%s = Graph(‘%s’)" % (name, name)) # метка = имя переменной
A.arcs = [B, E, G]
B.arcs = [C] # теперь настроить связи:
C.arcs = [D, E] # вложенный список экземпляра
D.arcs = [F]
E.arcs = [C, F, G]
G.arcs = [A]
A.search(G)
for (start, stop) in [(E,D), (A,G), (G,F), (B,A), (D,A)]: print(start.search(stop))
Этот сценарий выполняет тот же самый обход графа, но на этот раз всю работу выполняют методы объектов:
C:\…\PP4E\Dstruct\Classics> python gtestobj1.py
[[E, C, D], [E, G, A, B, C, D]]
[[A, G], [A, E, G], [A, B, C, E, G]]
[[G, A, E, F], [G, A, B, C, D, F], [G, A, B, C, E, F], [G, A, E, C, D, F]] [[B, C, E, G, A]] []
Результат получается такой же, как при использовании функций, но имена узлов выводятся без кавычек: узлы в списках путей теперь являются экземплярами класса Graph, а метод __repr__ класса подавляет вывод кавычек. Перед тем как двинуться дальше, рассмотрим еще один сценарий проверки графов, представленный в примере 18.21, — набросайте узлы и дуги на бумаге, если проследить пути вам труднее, чем интерпретатору Python.
Пример 18.21. PP4E\Dstruct\Classics\gtestobj2.py
from graph import Graph
S = Graph(‘s’)
P = Graph(‘p’) # граф spam
A = Graph(‘a’) # создать объекты узлов
M = Graph(‘m‘)
S.arcs = [P, M] # S ведет к P и M
P.arcs = [S, M, A] # дуги: встроенные объекты
A.arcs = [M]
print(S.search(M)) # найти все пути из S в M
Этот сценарий находит в графе три пути между узлами S и M. Мы лишь слегка коснулись здесь этой академической, но весьма полезной области знаний. Поэкспериментируйте с графами самостоятельно и поищите в других книгах дополнительные темы, связанные с ними (например, по иск в шири ну и по пер вому наи луч ше му сов па де нию):
C:\…\PP4E\Dstruct\Classics> python gtestobj2.py [[s, m], [s, p, m], [s, p, a, m]]
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
