Выравнивание вершин в DAG в древовидной форме (т.е. вертикали без внутренних краев, вертикали, зависящие только от тех, что находятся на следующем уровне и т.д.) довольно просты без алгоритмов рисования графов, таких как Эффективная Сугияма. Однако существует ли простой алгоритм для минимизации пересечения ребер? (Для некоторых графиков невозможно полностью исключить пересечение ребер.) Картина говорит тысячу слов, так же есть алгоритм, который предложил бы что-то без скрещивания края. (по сравнению с этим).
Я принял Senthil, предлагая graphviz/dot - быстрый взгляд на документы подтверждает, что очень легко использовать его как библиотеку или внешний инструмент и выходной формат на удивление легко разобрать. Тем не менее, я решил использовать GraphSharp, так как я уже использую .NET и т.д. (Хотя это определенно не так сильно, как точка). Результат "достаточно хорош" и может быть намного лучше с небольшим маршрутированием и настройкой (размытый текст из-за 3.5 WPF).
Здесь полный код С# (это все код, который ссылается либо на QuickGraph, либо на GraphSharp - да, это было так просто):
internal static class LayoutManager
{
private const string ALGORITHM_NAME = "EfficientSugiyama";
private const bool MINIMIZE_EDGE_LENGTH = true;
private const double VERTEX_DISTANCE = 25;
private const double LAYER_DISTANCE = 25;
private const double MIN_CANVAS_OFFSET = 20;
public static void doLayout(GraphCanvas canvas)
{
// TODO use a background thread
// TODO add comments
canvas.IsEnabled = false;
canvas.Cursor = Cursors.Wait;
var graph = new BidirectionalGraph<GraphNode, LayoutEdge>();
var positions = new Dictionary<GraphNode, Point>();
var sizes = new Dictionary<GraphNode, Size>();
foreach(var node in canvas.nodes)
{
var size = node.RenderSize;
graph.AddVertex(node);
positions.Add(node, new Point(node.left + size.Width / 2, node.top + size.Height / 2));
sizes.Add(node, size);
}
foreach(var edge in canvas.edges)
{
graph.AddEdge(new LayoutEdge(edge));
}
var context = new LayoutContext<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>(graph, positions, sizes, LayoutMode.Simple);
var parameters = new EfficientSugiyamaLayoutParameters();
parameters.VertexDistance = VERTEX_DISTANCE;
parameters.MinimizeEdgeLength = MINIMIZE_EDGE_LENGTH;
parameters.LayerDistance = LAYER_DISTANCE;
var factory = new StandardLayoutAlgorithmFactory<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>();
var algorithm = factory.CreateAlgorithm(ALGORITHM_NAME, context, parameters);
algorithm.Compute();
canvas.deselectAll();
var minx = algorithm.VertexPositions.Select(kvp => kvp.Value.X - (kvp.Key.RenderSize.Width / 2)).Aggregate(Math.Min);
var miny = algorithm.VertexPositions.Select(kvp => kvp.Value.Y - (kvp.Key.RenderSize.Height / 2)).Aggregate(Math.Min);
minx -= MIN_CANVAS_OFFSET;
miny -= MIN_CANVAS_OFFSET;
minx = minx < 0 ? -minx : 0;
miny = miny < 0 ? -miny : 0;
foreach(var kvp in algorithm.VertexPositions)
{
var node = kvp.Key;
var pos = kvp.Value;
node.left = (pos.X - (node.RenderSize.Width / 2)) + minx;
node.top = (pos.Y - (node.RenderSize.Height / 2)) + miny;
}
canvas.Cursor = Cursors.Arrow;
canvas.IsEnabled = true;
}
private sealed class LayoutEdge : IEdge<GraphNode>
{
private readonly ConnectingEdge _edge;
public LayoutEdge(ConnectingEdge edge) { _edge = edge; }
public GraphNode Source { get { return _edge.output.node; } }
public GraphNode Target { get { return _edge.input.node; } }
}
Кажется, что это соответствует размеру счета:
точка - `` иерархическая '' или слоистая чертежи ориентированных графов. алгоритм компоновки нацеливает края в в том же направлении (сверху вниз или слева справа), а затем пытается избежать краевые переходы и уменьшить длину ребер.
https://docs.google.com/viewer?url=http://www.graphviz.org/pdf/dotguide.pdf
Вы можете попробовать использовать Топологическая сортировка. На первом этапе вы можете определить уровни (сверху вниз) макета, выполнив топологическую сортировку и всегда группируя независимые узлы в одном слое. Это всегда будет успешным для ориентированных ациклических графов.
Тогда вы могли бы попытаться выполнить топологический вид каждого слоя (слева направо), принимая во внимание расположение входных и выходных портов и, возможно, смежных уровней. Мое изображение этого шага немного размыто, но я могу себе представить, что это возможно для графиков, подобных вашему примеру.