رسم الرسوم البيانية الموجهات الموجه: تقليل عبور الحافة؟
-
27-09-2019 - |
سؤال
إن وضع الفروسيات في DAG في شكل شجرة (أي verticies مع عدم وجود حواف في الأعلى ، يعتمد Vertic على تلك الموجودة على المستوى التالي ، وما إلى ذلك) بسيطة إلى حد ما دون خوارزميات رسم الرسم البياني مثل Sugiyama. ومع ذلك ، هل هناك خوارزمية بسيطة للقيام بذلك تقلل من عبور الحافة؟ (بالنسبة لبعض الرسوم البيانية ، قد يكون من المستحيل التخلص تمامًا شيء بدون عبور الحواف. (مقارنة بهذا).
تحرير: النتيجة
لقد قبلت Senthil اقتراح GraphViz/DOT - نظرة سريعة على المستندات تؤكد أنه من السهل جدًا ذلك استخدمه كمكتبة أو أداة خارجية, ، و من السهل تحليل تنسيق الإخراج. ومع ذلك ، انتهى بي الأمر إلى اختيار الاستخدام GraphSharp بدلاً من ذلك ، نظرًا لأنني أستخدم بالفعل .NET ، إلخ (على الرغم من أنها بالتأكيد ليست قوية مثل DOT). والنتيجة "جيدة بما يكفي" ، ويمكن أن تصبح أفضل بكثير مع توجيه الحافة الصغيرة والتبديل (النص الضبابي بسبب 3.5 WPF).
ها هي مكتمل 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; } }
}
المحلول
يبدو أن النقطة تناسب الفاتورة:
DOT - `` هرمي "أو رسومات ذات طبقات من الرسوم البيانية الموجهة. تهدف خوارزمية التخطيط إلى الحواف في نفس الاتجاه (من أعلى إلى أسفل ، أو من اليسار إلى اليمين) ثم تحاول تجنب معابر الحافة وتقليل طول الحافة.
https://docs.google.com/viewer؟url=http://www.graphviz.org/pdf/dotguide.pdf
نصائح أخرى
يمكنك محاولة استخدام الفرز الطوبولوجي. في الخطوة الأولى ، يمكنك تحديد المستويات (من أعلى إلى أسفل) التخطيط عن طريق إجراء نوع طوبولوجي ودائمًا تجميع العقد المستقلة في طبقة واحدة. سينجح هذا دائمًا في الرسوم البيانية الموجه.
بعد ذلك ، ربما يمكنك محاولة تنفيذ نوع طوبولوجي من كل طبقة (من اليسار إلى اليمين) أخذ موقع منافذ الإدخال والمخرجات وربما طبقات مجاورة في الاعتبار. صورتي لهذه الخطوة ضبابية بعض الشيء ، لكن يمكنني أن أتخيل أنها قابلة للتنفيذ للرسوم البيانية مثل مثالك.