Размещение вершин в DAG в виде дерева (то есть вершин без ребер сверху, вершин, зависящих только от вершин следующего уровня и т. Д.) Довольно просто без алгоритмов рисования графа, таких как Efficient Sugiyama.Однако существует ли простой алгоритм для этого, который минимизирует пересечение ребер?(Для некоторых графиков может быть невозможно полностью исключить пересечение ребер.) Изображение говорит тысячу слов, поэтому существует алгоритм, который бы предлагал что-то без пересечения ребер .( по сравнению с этим ).
РЕДАКТИРОВАТЬ: Результат
Я согласился с предложением Сентила graphviz / dot - быстрый просмотр документов подтверждает, что это очень легко использовать его в качестве библиотеки или внешнего инструмента , а формат вывода удивительно легко проанализировать .Тем не менее, я решил использовать GraphSharp вместо этого, так как я уже использую .NET и т. Д. (Хотя он определенно не такой мощный, как точка).Результат «достаточно хороший», и его можно было бы сделать намного лучше с небольшой реберной маршрутизацией и настройкой (размытый текст из-за 3.5 WPF ).
Автоматически уложен-out graph http://public.blu.livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif
Вот код complete C # (это весь код, который ссылается на 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; } }
}