>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь

20. Ориентированные Графы

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

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

Матрица смежности удобна для определения различных свойств графа, таких как степень по входящим ребрам (количество ребер, входящих в данную вершину), степень по исходящим ребрам, ближайшие соседи, и замыкание (тоесть проведение явных соединений с любым узлом, достижимым по какому-либо пути из каждого). Например:
   from=: 3 7 2 5 5 7 1 5 5 5 2 6 1 2 3 7 7 4 7 2 7 4
     to=: 5 6 0 2 6 2 7 6 0 7 3 3 2 1 7 0 4 2 3 0 0 3

   $ arcs=: from,.to
22 2
               
   |: arcs { nodes=: 'ABCDEFGH'         Для отображения транспонировано
DHCFFHBFFFCGBCDHHEHCHE
FGACGCHGAHDDCBHAECDAAD

   CM=: #. e.~ [: i. [ , [              Матрица смежности из ребер
   ]cm=: (>:>./,arcs) CM arcs
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1
1 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1
0 0 1 1 0 0 0 0
1 0 1 0 0 0 1 1
0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 0

   (+/cm);(+/"1 cm);  (+/+/cm);(#arcs);(#~.arcs)
+---------------+---------------+--+--+--+
|3 1 4 4 1 1 2 3|0 2 3 2 2 4 1 5|19|22|19|
+---------------+---------------+--+--+--+
Выше рассчитаны: степень каждого узла по входящим ребрам, степень по исходящим и полная степень всех узлов; далее следуют: полное число ребер и число различных ребер. Узлам можно поставить в соответствие булевский вектор b , тогда внутреннее произведение b +./ . *. cm дает (в том-же представлении) узлы, достижимые из тех, которые были заданы в этом векторе изначально. Ближайшее окружение некоторого количества узлов (включая начальные точки) можно получить функцией imfam :
   imfam=: [ +. +./ . *.
   (b=: 1 0 0 0 0 0 0 1) imfam cm
1 0 1 1 1 0 1 1
>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь