DemonScript: Работа с графами


Введение

Граф является одним из базовых типов DemonScript. Графы состоят из узлов (объектов). Любая пара узлов может быть соединена направленным ребром одного из заданных типов (отношений). С каждым ребром связывается нечёткое логическое значение, означающее степень истинности отношения между двумя объектами.

Типы возможных рёбер объявляются при помощи оператора edges, который должен стоять выше каких либо функций по работе с графами. Объявленные типы рёбер доступны в любом графе скрипта. Имя ребра должно начинаться с символа @. Существует предопределённое ребро @isa. Соответствующее ему отношение X.@isa.Y означает, что X является экземпляром класса Y или его подмножеством для абстрактных классов: Барбос isa собака, собака isa животное.

Узлы графа могут иметь имена или быть безымянными. Именованные узлы объявляются при помощи оператора nodes. Он может встречаться в любом месте скрипта произвольное число раз и объявляемые в нём узлы добавляются в текущий граф. Имя узла должно начинаться с символа доллара $.

edges @in                          // объявляем типы рёбер 
nodes $a, $b                       // граф состоит из двух узлов
nodes $c                           // в граф добавился третий узел

В DemonScript существует предопределённая переменная GRAPH. Она является текущим графом с которым работают функции задания или чтения рёбер X.E.Y.

out GRAPH.type()                   // тип переменной > graph
out GRAPH.nodes()                  // число узлов    = 3

$a.@in.$b = True                   // определяем ребро графа GRAPH

out GRAPH                          // выводим граф на экран
Последний оператор out выведет: GRAPH { $a{ @in:[$b]}, $b {},$c {} }. Существует несколько различных форматов, в которых может быть выведена структура графа. Они будут рассмотрены ниже.


Базовые операции с узлами

Цикл for позволяет перебирать узлы графа, удовлетворяющие определённому условию. Между оператором for и оператором in находится переменная X (её объявлять не надо). Затем, между in и двоеточием ":" ставится произвольное логическое выражение. Оператор for перебирает узлы графа для которых выражение для текущего графа истинно. Выведем, например, все узлы графа:

for X in True:
   out X                           //> $a $b $c
В качестве условия, идущего после ключевого слова in взята всегда истинная константа True, поэтому и получился цикл по всем узлам (оператор out выведет $a,$b,$c). В следующем примере выводятся объекты, которые находятся в объекте $b (это пока единственный узел $a):
for X in X.@in.$b:
   out X                           //> $a 

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

if exists(X, X.@in.$b):
   out X                           //> $a 
else
   out "Not exists"
Как и в случае с циклом for, переменную, стоящую в exists, объявлять не надо. Аналогично работает функция forall(X, COND), которая возвращает True, если условие COND, зависящее от X, выполняется для всех узлов графа.

Если необходимо вывести все объекты, связанные ребром @in, независимо от его логического значения (отличного от неопределённого Undef), то используется функция X.is_edge(E, Y):

for Z in Z.is_edge(@in, $b) :
   out Z, Z.@in.$b             // узел и значение ребра

Аналогично, например, получается список всех выходящих из узла $a узлов по ребру @in с логическим значением ребер False:

for Z in $a.@in.Z  == False :
   out Z                       // входящие узлы

Стоит помнить, что если в условии стоит значение ребра X.E.Y или функция X.is_edge(E, Y), то цикл for работает достаточно быстро (как для входящих, так и для исходящих рёбер). Однако, для произвольного условия, чтобы выяснить его истинность, перебираются все узлы графа. Поэтому в случае больших графов это может занять некоторое время.


Путь на графе

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

edges @in                          // типы рёбер       
nodes $a, $b, $c, $d               // объявляем узлы

$c.@in.$d = True                   // с внутри d
[$a, $b].@in.$c = True             // a и b внутри с
В квадратных скобках перечислены два узла, каждый из которых соединяется с узлом $c ребром @in, имеющим истинное значение. Этот граф в виде структуры и графической диаграммы приведен ниже. Последний рисунок схематически изображает вложенные друг в друга ящики:

   graph {
      $a { @in:[$c] },
      $b { @in:[$c] },
      $c { @in:[$d] },
      $d {}
   }

Перемещаясь по рёбрам, из одного узла можно попасть в другой. Для выявления наличия пути по графу служит функция path, возвращающая логическое значение:
out $a.path(@in, $d)               // есть ли путь из $a в $d > True
out $a.path(@in, $b)               // есть ли путь из $a в $b > Undef
Первая строка возвращает True (истина), потому что, "поднимаясь" из $a, мы попадаем в $d. Рёбра $a и $b не связаны путём, поэтому вторая функция возвращает Undef (неопределено). Эта же функция вернёт False, если путь существует, но одно из его рёбер имеет значение False. Таким образом, это трёхзначная логическая функция.

Аналогично, при помощи функции X.common(E, Y) можно выяснить, существует ли общий узел, в которой можно попасть, двигаясь из узлов X, Y по рёбрам типа E. На древесном графе, подобном приведенному выше, это означает, что X, Y имеют общего предка:

out $a.common(@in, $d)             // есть ли предок у $a и $d > True
out $a.common(@in, $b)             // есть ли предок у $a и $b > True

Существует множество других встроенных функций по работе с графами. Более подробная информация содержится в этом документе и в справочнике.

Создание графов

DemonScript позволяет работать с несколькими графами. Создавать графы можно двумя способами: при помощи конструктора GRAPH() и метода .copy(). В первом случае создаётся пустой граф, а во втором создаётся граф, в который копируются все узлы и рёбра того объекта, у которого вызван метод .copy(). В качестве аргумента в конструктор и метод .copy() можно передавать строку (тестовое имя графа), которая будет появляться при выводе графа оператором out. Это имя можно получить как строку при помощи метода A.name(). Этот же метод позволяет переименовать граф: A.name("new A").

edges @in
nodes $a, $b                       // эти узлы попали в GRAPH

var A = GRAPH.copy("A")            // это копия, содержащая $a,$b
var B = GRAPH("B")                 // создаём пустой граф
var C = B.copy("C")                // это копия пустого графа B

out A,B,C
В результате будет выведено:
   A { $a {}, $b {} }
   B { }
   C { }

Каждому графу, который создаётся при помощи конструктора, присваивается уникальное целое число (номер класса). Копия графа, созданная по .copy() унаследует номер класса родительского графа. Все графы одного класса имеют одинаковые узлы (но, возможно, различные рёбра). У графов разных классов имена узлов не должны пересекаться. Выше граф A принадлежит одному классу, а графы B,C к другому, т.к. B создан конструтором, а A - его копия.

Установим граф B в качестве текущего. Для этого его необходимо присвоить в переменную GRAPH

GRAPH = B                          // текущим будет граф B
nodes $c, $d                       // в него добавляем два узла

GRAPH = C                          // теперь текущий граф С
nodes $e                           // добавляем узел в него и все графы его класса
$e.@in.$d = True                   // задаём ребро

out A, B, C
Вывод графов приводит к следующему результату:
   
   A { $a {},   $b {}        }
   B { $c {},   $d {}, $e {} }
   C { $c {},   $d {}, $e { @in:[$d] }}
В граф B явным образом были добавлены два узла $c,$d. Тем не менее он также "приобрёл" узел $e, который вставлялся в его копию C, т.к. у них общий класс графа.

Граф A все эти манипуляции с графми B и С не заметил, так как принадлежит к другому классу. Номер класса можно получить при помощи функции class_id:

out A.class_id()                   //> 1
out B.class_id(), C.class_id()     //> 2,2

Таким образом, все графы разбиваются на классы, каждый из которых характеризуется уникальным номером. Графы одного класса имеют одинаковые узлы. Добавление в любой граф данного класса узлов приводит к добавлению этих же узлов во все графы этого класса. Модификация рёбер графов одного или разных классов происходит независимым образом.


Ссылки на графы

При присвоении переменных типа graph не происходит копирования данных, а передаётся лишь ссылка ("указатель") на эти данные. Это быстрая операция. Рассмотрим подробнее, что при этом происходит.

Создадим две переменные типа graph, которые будут хранить независимые копии графа GRAPH:

edges @in
nodes $a, $b, $c                   // эти узлы попали в GRAPH


var A = GRAPH.copy("A")            // одна   копия графа GRAPH
var B = GRAPH.copy("B")            // вторая копия графа GRAPH
Сделаем текущим граф B и поменяем в нём ребро:
GRAPH = B                          // текущий граф ссылается на B
$b.@in.$c = True                   // меняем ребро в графе B

out A, B, GRAPH
Граф A - исходный и содержит одно ребро, а B - граф с двумя рёбрами. Одно он унаследовал у исходного графа по copy(), а второе было добавлено после этого:
   A     { $a{ @in:[$b] },  $b{},           $c{} }
   B     { $a{ @in:[$b] },  $b{ @in:[$c] }, $c{} }
   GRAPH { $a{ @in:[$b] },  $b{ @in:[$c] }, $c{} }

Если теперь сделать текущим граф A:

GRAPH = A
out GRAPH
то при выводе GRAPH снова будет с одним ребром:
  A     { $a{ @in:[$b] },  $b{},           $c{} }
Заметим, что так как он ссылается теперь на A, то и имя у него изменяется с GRAPH на A.

Таким образом, при простом присваивании графов: G1=G2 происходит запоминание в переменной G1 ссылки на данные графа G2. Любые изменения с этими данными "почувствуют" обе переменные G1,G2. Если же присвоение делать при помощи метода copy(), то данные становятся независимыми, и их изменение в одном графе другой не "почувствует" (за исключением добавления узлов, так как это графы одного класса).


Связывание графов

Создадим граф, узлы которого будут хранить классы абстрактных смыслов container, box и cat:

edges @isa, @in

var Sen = GRAPH("Sen")             // создаём пустой граф без узлов
GRAPH = Sen                        // делаем его текущим

nodes $container, $box             // определяем его узлы
$box.@isa.$container = True        // добавляем ребро isa

nodes $cat                         // добавляем ещё один узел
Граф Sen создаётся при помощи конструктора GRAPH(). Отношение @isa отмечает, что класс всех ящиков $box является подмножеством класса всех контейнеров $container.

Создадим ещё один граф G. Его узлы будут означать конкретные экземпляры абстрактных классов. Пусть, например, в сознании системы находятся два ящика:

var G = GRAPH("G")                 // создаём пустой граф
GRAPH = G                          // делаем его текущим
nodes $box1, $box2                 // и определяем его узлы

$box1.@in.$box2 = True             // ящик box1 находится в ящике box2

Объявим эти два ящика экземплярами класса $box:

$box1.@isa.Sen=>$box = True
$box2.@isa.Sen=>$box = True
Узел Sen=>$box означает узел $box в графе Sen. Так, выше между узлом $box1 графа G проведено ребро типа @isa в узел $box внешнего графа Sen. Таким образом, конструкция:
   переменная_графа => имя_узла
даёт доступ к узлу графа, который сейчас не активен (на который не ссылается GRAPH).

Задание двух однотипных рёбер к одному и тому же узлу можно также проделать более лаконичным образом:

[$box1, $box2].@in.Sen=>$box = True


Работа со связанными графами

По рёбрам связанных графов можно "путешествовать" из одного графа в другой. Например, определим демона, который выясняет, является ли данный объект сознания X членом класса Y:

def isa(X,Y): return X.path(@isa, Y) == True

out isa($box1, Sen=>$container)    //> True
out isa($box1, Sen=>$box)          //> True
out isa($box1, Sen=>$cat)          //> Undef
Так как демон состоит из одной команды, для его описания не обязательны фигурные скобки (но необходимо поставить двоеточие). Он вызывает для текущего графа функцию path от узла X к узлу Y по рёбрам isa. При вызове этого демона в качестве узла Y выступают узлы графа Sen, по которому продолжается поиск пути. В частности, так как истинно $box1.@isa.Sen=>$box и $box.@isa.$container (в графе Sen), то мы получаем, что истинно и $box1.@isa.Sen=>$box.

Связывание графов не оказывает влияния на конструкцию for ... in. В частности, для текущего примера следующий код выведет только два узла:

for Z in True:
   out Z                           //> $box1, $box2
Заметим, что для любого узла доступен метод X.isa(Y), который работает как введенный выше демон.