Алгоритм построения ориентированного ациклического графа? - PullRequest
Новая
       65

Алгоритм построения ориентированного ациклического графа?

0 голосов
/ 25 февраля 2019

Я пытаюсь найти подход к визуализации DAG чистым, строгим, основанным на сетке способом и очень коротким.

Я бы хотел сделать что-то похожее на это: 

                   ┌───────────┐      ┌───────────┐
               ┌───│     b     │─────▶│     d     │
               │   └───────────┘      └───────────┘
               │                                   
┌───────────┐  │   ┌───────────┐      ┌───────────┐
│     a     │◀─┼──▶│     c     │──┬──▶│     e     │
└───────────┘  │   └───────────┘  │   └───────────┘
               │                  │                
               │                  │   ┌───────────┐
               └──────────────────┴──▶│     f     │
                                      └───────────┘

Это графическое представление следующих зависимостей: d(b), b(a), e(c), f(c), c(a).(box(depends on)).

Я тщательно исследовал графики «направленной силы», но это кажется ненужным, поскольку у меня есть пара ограничений, они должны быть строго на сетке, и это не является строго иерархическим.

Альтернативные подходы, для которых мне не удалось найти адекватную документацию по разработке алгоритма компоновки, включают в себя различные подходы к «компоновке дерева», «компоновке процесса», «компоновке решений» (см. здесь )

Моя конечная цель - создать механизм раскладки для d3 (или аналогичного), который выложит что-то интерактивное:

example of layout from sketch.app mock-up

Моя лучшая рабочая теория на данный момент такова:

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

  2. Начните размещать вещи в столбцах, располагайте вещи с самыми длинными цепями дальше вправо, а меньшие или без цепей слева.

  3. Есличто-тов столбце есть зависимость в том же столбце, переместите все столбец влево и позвольте зависимому элементу занять его место.

  4. Нарисуйте линии, это должно быть легко, если алгоритм учитывает толькоширокие «позиции сетки», а не абсолютные значения пикселей, должно быть легко нарисовать соединительную линию от A1 (ячейка a) до B1 (ячейка c); 


                  A                   B                  C                

                            │                  │                          

                            │                  │                          
                                ┌───────────┐      ┌───────────┐          
  0                         ├───│     b     │──┼──▶│     d     │          
                            │   └───────────┘      └───────────┘          
        ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─│─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 
             ┌───────────┐  │   ┌───────────┐      ┌───────────┐          
  1          │     a     │◀─┼──▶│     c     │──┼──▶│     e     │          
             └───────────┘  │   └───────────┘  │   └───────────┘          
        ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─│─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 
                            │                  │   ┌───────────┐          
  2                         ├──────────────────┼──▶│     f     │          
                                                   └───────────┘          
                            │                  │                          

                            │                  │

Мой подход в основном обоснован?Есть ли что-то, чего мне не хватает, как подойти к этому?Какое чтение кто-нибудь может порекомендовать при написании механизмов компоновки, подобных этому?

...