grandalf

Grandalf is a pure-Python package for computing graph layouts. It implements two well-known drawing algorithms — the Sugiyama hierarchical layout (the same style of layered layout used by dot/graphviz) and a force-driven energy-minimization layout — and hands back the (x, y) coordinates for nodes and the routing for edges. It deliberately does not draw anything itself: no GTK, Qt, or other graphics toolkit dependency is pulled in, so it can sit underneath whatever rendering surface a project already uses.

The library keeps its own graph model (Vertex, Edge, Graph, graph_core) rather than depending on a heavier graph library, though it ships an optional networkx bridge (grandalf.utils.nx) for converting graphs in both directions. A bundled dot-file parser (built on pyparsing, with an optional ply-based path) lets it ingest existing graphviz .dot graphs directly.

At roughly 1,500 lines total — with the Sugiyama layout in under 600 and the energy-minimization layout in about 250 — the codebase favors being easy to read and hack over being feature-complete or fast, which makes it a reasonable base for experimenting with or extending layout algorithms rather than a drop-in replacement for graphviz at scale.

What You Get

• A minimal graph model (Vertex, Edge, Graph, graph_core) with disjoint-set component tracking, shortest-path (BFS) and Dijkstra search, and Tarjan-based cycle/feedback-edge detection
• SugiyamaLayout — the layered hierarchical layout algorithm (as used by graphviz’s dot), including dummy-vertex insertion for long edges and barycenter-based crossing reduction across multiple ordering rounds
• DigcoLayout — an alternative energy-minimization layout that places nodes by optimizing a stress/energy function instead of heuristics, useful when Sugiyama’s layered structure doesn’t fit
• Edge routing helpers (route_with_lines, route_with_splines) that convert layout waypoints into polylines or NURBS-smoothed bezier curves for rendering
• A networkx interop module for converting graphs to/from networkx.MultiDiGraph, and a pyparsing-based dot-file parser for loading existing graphviz graphs

Common Use Cases

• Computing layout coordinates for a custom graph-visualization UI (e.g. rendering control-flow graphs, dependency graphs, or state machines) without adopting a full graphviz toolchain
• Prototyping or teaching graph-drawing algorithms, since the Sugiyama and energy-minimization implementations are short enough to read end-to-end and modify
• Loading and re-laying-out existing graphviz .dot files programmatically in Python
• Bridging networkx graph objects into a layout-ready structure to get node positions for a custom renderer

Under The Hood

Architecture The codebase separates graph modeling from graph drawing cleanly: graphs.py defines the connectivity model (vertex_core/edge_core hold adjacency and degree bookkeeping; Vertex/Edge add data and pickling support; graph_core is a single connected component with BFS path-finding, Dijkstra, and Tarjan strongly-connected-component/feedback-edge detection; Graph is a disjoint-set wrapper managing multiple graph_core components as vertices/edges are added or removed). layouts.py then builds on that model without ever mutating the underlying topology permanently — the Sugiyama algorithm attaches transient per-vertex attributes (rank, dummy flag, position, barycenter) via _sugiyama_vertex_attr and inserts DummyVertex placeholders for edges spanning multiple ranks, all kept inside the layout object. routing.py is a separate, optional final stage that turns computed waypoints into renderable line/spline paths. This layering means swapping in a different layout algorithm (as DigcoLayout demonstrates) doesn’t require touching the graph model or routing code.

Tech Stack Pure Python 3 with a minimal dependency footprint: pyparsing is a hard requirement (used by the dot-file parser in utils/dot.py), while numpy and ply are optional extras (pip install grandalf[full]) for the constrained/energy layout and an alternative dot parser. Packaging is done via a classic setup.py (no pyproject.toml), and CI is configured through a long-dormant .travis.yml targeting Python 3.6–3.8 — the actual supported-version story is now stale relative to the 2024 last commit.

Code Quality The project has a real pytest suite (roughly 760 lines across ten test files covering the graph model, both layout algorithms, cycle detection, dot parsing, routing, and networkx interop), plus a conftest.py with a library of toy graph fixtures drawn from published layout papers. Error handling favors explicit ValueError/assert checks when graph invariants would be violated (e.g. removing an edge that would disconnect a component) rather than silently succeeding. There are no type hints, no linter/formatter configuration, and no modern CI — the Travis setup is effectively defunct, so quality signal comes mostly from the test suite itself rather than tooling.

API Design The public surface is small and consistent: construct Vertex/Edge objects, assemble a Graph, hand a graph_core to SugiyamaLayout or DigcoLayout, call init_all() then draw(), and read .view.xy off each vertex. Getting a usable layout takes only a handful of lines, as the README’s own worked example shows, though the vertex .view protocol (any object exposing .w/.h/.xy) is documented only informally and requires reading the source to fully understand its contract with the dummy-vertex and routing machinery.