Javascript график раскладка алгоритм

Question

TL; DR

Мне нужно установить макет графа программно, хотя код JavaScript.

Объяснение

У меня есть график в следующем формате:

var graph = { 
    "nodes": [ 
     {"x": 0, "y": 0}, 
     {"x": 0, "y": 0}, 
     {"x": 0, "y": 0}, 
     {"x": 0, "y": 0}, 
    ], 
    "edges": [ 
     {"source": 0, "target": 1}, 
     {"source": 1, "target": 2}, 
     {"source": 1, "target": 3}, 
     {"source": 3, "target": 2}, 
    ] 
}; 

Все эти узлы имеют значение 0X и Y. Если мы нарисуем это на холсте, график, очевидно, не будет выглядеть хорошо.

Я хочу применить алгоритм к этой структуре данных так, чтобы значения всех узлов были отрегулированы автоматически (с минимальными пересечениями кромок).

Существующие решения

Я попытался силы направленной макет D3.js и некоторых аналогичных решений. Но они требуют слишком много итераций, и большинство моих графиков имеют> 50 узлов с большим количеством ребер.

Алгоритм, который я ищу, должен создать макет в минимальной сложности и времени (или он должен быть по крайней мере быстрее, чем итеративные).

Matlab имеет три типа двигателей типа для своего biograph. LayoutTypeValue может быть либо hierarchical, radial и equilibrium. Радиальный, похоже, хорошая идея.

Спасибо.

Answer 1

Если это связано с коммерческим сценарием, вы можете взглянуть на библиотеку рисования и компоновки графических объектов Javascript yFiles for HTML.

Насколько я знаю, он предоставляет самые полные и самые универсальные автоматические варианты компоновки графиков, доступные для Javascript. Они доступны через хороший Javascript API и не чувствуют себя как черное окно командной строки, например, как предложение emscripten из комментариев.

См. this extensive interactive automatic layout demo, в котором показаны многие варианты автоматической компоновки.

Большинство (но не все со всеми настройками) алгоритмов очень хорошо работают с графиками такого размера (несколько сотен элементов).

(не исчерпывающий) перечень доступных макетов является

• иерархической
• древовидной
• сила направленного
• круговую
• шар
• ортогональны
• радиальных
• различных выделенный край маршрутизации только реализации

Раскрытие: Я работаю в компании, которая создает эту библиотеку, но я не представляю мой работодатель на SO. Это мой собственный комментарий и мнение.