Язык для описания графов

[yurikhan]

Хочу человеческий синтаксис для описания графов.

Что у нас сейчас есть: Graph description languages.

• Половина из них основана на XML, что хорошо для инструментов, но плохо для написания руками.

• DOT спроектирован математиками и из-за этого тоже излишне многословен. Мы можем определить в графе дефолтные свойства вершин и рёбер, и это позволяет немного экономить. Но если у нас в графе два типа рёбер, то один можно сделать дефолтным, а второй приходится выписывать каждый раз:

  digraph G {
    edge [arrowhead=empty] # inheritance
  
    Derived -> Base
  
    Aggregate -> Part [arrowtail=odiamond, arrowhead=open] # aggregation
  }

  Или можно определить подграф и рёбра второго типа определять в нём, что плохо для локальности (часто хочется описывать рёбра, относящиеся к одной вершине, рядом):

  digraph G {
    subgraph {
      edge [arrowhead=empty] # inheritance
      Derived -> Base
    }
    subgraph {
      edge [arrowtail=odiamond, arrowhead=open] # aggregation
      Aggregate -> Part
    }
  }

Как надо:

• Есть классы вершин и рёбер. Все общие свойства вершин или рёбер одного класса описываются в определении класса. Важно, что определения классов можно вынести в библиотеки и подключать их, когда надо.

• Минимальное определение вершины состоит из имени класса вершины и имени вершины, на отдельной строке, через пробел. Далее опционально индивидуальные свойства вершины. (Тут решить между синтаксисом со скобками и разделителями или просто indentation-based.) Имя может быть одним словом или произвольной строкой в кавычках.

• Минимальное определение ребра состоит из имени начальной вершины, имени класса ребра и имени конечной вершины, также на отдельной строке через пробел, также с опциональным блоком свойств.

Пример:

node.class [shape=box]
node.interface [shape=circle]
edge.is-a [arrowhead=empty]
edge.implements [arrowhead=empty, style=dashed]
edge.has-a [arrowtail=odiamond, arrowhead=open]
edge.owns-a [arrowtail=diamond, arrowhead=open]

interface IThing

class Base

class Derived
Derived is-a Base
Derived implements IThing

class Part

class Aggregate
Aggregate has-a Part

Буду в отпуске, сяду и напишу парсер этого и конвертор в DOT.

Stretch goal: какой-нибудь способ указать, что одни «node1 relation node2» отображать рёбрами, а другие — вложением в кластер-подграф. Типа nginx deployed-on cache-server.

Comments

[vissarion.livejournal.com]

Чувствую, не будешь ты в отпуске писать парсер
В доте же перечислением это делается.

digraph ethane {
     //class
     node [shape=box]
       Base
       Derived
       Aggregate
       Part
     // interface
     node [shape=circle]
       IThing
     // is-a
     edge [arrowhead=empty]
       Base -> Derived
     // implements
     edge [arrowhead=empty, style=dashed]
       Derived -> IThing
     // has-a
     edge [arrowtail=odiamond, arrowhead=open]
       Aggregate -> Part
 }

[yurikhan]

Я же говорю, так локальность нарушается.

Ты предлагаешь сначала выписать все классы и интерфейсы, потом все наследования, потом все агрегации; в общем случае — группировать всё по классу вершины и ребра.

Это работает, если у нас куча времени и наша цель — нарисовать знакомую систему в статью в журнал. У меня такой цели нет никогда, моя цель — за разумное время изучить незнакомую систему или догнать изменения в когда-то знакомой. Я хочу добавлять класс и сразу следом за ним все его ассоциации с уже известными сущностями.

Подкорректировал пример, чтобы эту группировку было видно.

[vissarion.livejournal.com]

Сортировка стейтментов - это недостаточный повод чтобы писать новый язык.
Когда отпуск ?

[yurikhan]

А какой повод достаточный?

[vissarion.livejournal.com]

Когда качественный скачок или меньше писанины в N раз.
А тут строчкой выше - строчкой ниже - какая разница.

[yurikhan]

Сортировка строк dot-файла в процессе написания этого файла — это сортировка вставками. O(n²) в среднем и худшем, и каждая операция — думательная.

Вот когда мне не приходится думать над размещением связей внутри файла и вообще над взаимодействием строк, особенно если файл больше одного экрана — это и есть качественный скачок. Управлять инструментом vs быть одним целым с инструментом.