Mostlylucid.Dagre 2.0.1

Mostlylucid.Dagre

A modern, high-performance C# graph layout engine implementing the Sugiyama (layered) algorithm. This is an extensively modernized fork of Dagre.NET (itself a port of dagre.js).

Why fork? The original Dagre.NET was a faithful line-by-line port of dagre.js, inheriting JavaScript idioms like dynamic property bags and object[] arrays. This made it slow, allocation-heavy, and incompatible with modern .NET features like NativeAOT and WebAssembly. Mostlylucid.Dagre rewrites the internals for idiomatic, high-performance .NET while preserving the same Sugiyama layout algorithm.

Features

• Zero dynamic — all property bags replaced with strongly-typed NodeLabel, EdgeLabel, GraphLabel classes
• Zero boxing — no Dictionary<string, object>, no object[] parameter arrays
• AOT-compatible — no Microsoft.CSharp dependency, works with NativeAOT and Blazor WASM
• Multi-target — net6.0, net8.0, net10.0
• 4-8x faster than original Dagre.NET with 5-11x less memory (see benchmarks below)
• Compound graph support — nested subgraphs with automatic boundary layout
• High-level and low-level APIs — simple DagreInputGraph for quick use, full DagreGraph for advanced control

Install

dotnet add package Mostlylucid.Dagre

Usage

High-Level API

using Dagre;

var graph = new DagreInputGraph();

var a = graph.AddNode(tag: "Start", width: 100, height: 40);
var b = graph.AddNode(tag: "Process", width: 120, height: 40);
var c = graph.AddNode(tag: "End", width: 100, height: 40);

graph.AddEdge(a, b);
graph.AddEdge(b, c);

graph.Layout();

// Nodes now have X, Y coordinates
Console.WriteLine($"{a.Tag}: ({a.X}, {a.Y})");
Console.WriteLine($"{b.Tag}: ({b.X}, {b.Y})");
Console.WriteLine($"{c.Tag}: ({c.X}, {c.Y})");

Low-Level API

For full control over the layout graph:

using Dagre;

var g = new DagreGraph { IsDirected = true, IsCompound = false, IsMultigraph = false };

g.SetGraphLabel(new GraphLabel
{
    RankDir = "TB",
    NodeSep = 50,
    RankSep = 50,
    EdgeSep = 10,
    Ranker = "network-simplex"
});

g.SetNode("a", new NodeLabel { Width = 100, Height = 40 });
g.SetNode("b", new NodeLabel { Width = 120, Height = 40 });
g.SetEdge("a", "b", new EdgeLabel { Weight = 1, Minlen = 1 });

DagreLayout.runLayout(g);

var aLabel = g.Node("a");
Console.WriteLine($"a: ({aLabel.X}, {aLabel.Y})");

Layout Options

Compound Graphs

var g = new DagreGraph { IsDirected = true, IsCompound = true };
g.SetGraphLabel(new GraphLabel { RankDir = "TB" });

g.SetNode("group", new NodeLabel());
g.SetNode("a", new NodeLabel { Width = 80, Height = 40 });
g.SetNode("b", new NodeLabel { Width = 80, Height = 40 });

g.SetParent("a", "group");
g.SetParent("b", "group");

g.SetEdge("a", "b", new EdgeLabel());
DagreLayout.runLayout(g);

Performance

Compared to the original Dagre.NET 1.0.0.6 NuGet package, using identical graph construction with BenchmarkDotNet on .NET 10:

The improvements come from eliminating dynamic dispatch, removing boxing allocations, and using strongly-typed data structures throughout the pipeline.

Architecture

The layout pipeline follows the Sugiyama method:

1. Acyclic — reverse edges to eliminate cycles
2. Rank — assign layers via network simplex
3. Order — minimize edge crossings within layers
4. Coordinate Assignment — Brandes-Kopf algorithm for X coordinates
5. Normalize/Denormalize — insert and remove dummy nodes for long edges
6. Edge Routing — compute control points for spline edges

Credits

• dagre — original JavaScript implementation by Chris Pettitt
• Dagre.NET — original C# port by fel88
• Naiad — Mermaid-to-SVG library that uses this layout engine

License

MIT — original license from fel88's Dagre.NET port.