Graph1x 1.0.1

Graph1x

A .NET library for creating, mutating, and analyzing graphs, built with modern C# and developed test-first.

API documentation →

Source, benchmarks & full README on GitHub →

Goals

Graph1x aims to cover the standard graph taxonomy under one coherent, strongly-typed API:

• Direction — directed and undirected graphs
• Weight — weighted and unweighted edges (weights via C# generic math, any INumber<T>)
• Cycles — cyclic graphs and DAG-enforcing types that reject cycle-forming edges
• Structure/density — adjacency-list (sparse) and adjacency-matrix (dense) storage behind the same contract
• Special structures — multigraphs (parallel edges) and a standalone hypergraph type

On top of the data structures, the library ships the classic algorithm suite: BFS/DFS, cycle detection, topological sort, connected/strongly connected components, shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall, A*), minimum spanning trees (Kruskal, Prim), and structural queries (degree, density, bipartiteness, transpose).

Status

Graph1x 1.0 is stable. The public API follows Semantic Versioning: breaking changes only in a new major version, additions in minors, fixes in patches — and the API surface is analyzer-locked, so compatibility is enforced by the build, not just by policy. Over 830 unit tests (written test-first, including a shared contract suite every graph type must pass) run on Linux and Windows against .NET 8 and .NET 10. The library is trim/Native-AOT compatible, strong-name signed, and ships Source Link with a symbols package.

How this was built

Graph1x was written by Claude Fable under my direction. I set the scope and decided what to build; I did not author the implementations.

This matters for how you read the guarantees above. The structural ones are real and mechanically enforced: the API surface is analyzer-locked, every graph backend passes the same contract suite, and CI runs the full test suite on both target frameworks. But the tests were generated alongside the code by the same model — that demonstrates internal consistency, not independent verification. The correctness of the algorithm implementations, particularly the centrality measures and the flow algorithms, has not been validated against an outside reference.

If you are evaluating Graph1x for anything load-bearing, review the implementations you depend on. Bug reports and corrections are genuinely welcome — they are the fastest way this library gets trustworthy.

Usage

Edges are lightweight value types; weighted edges accept any numeric type via generic math:

using Graph1x.Edges;

var road = new Edge<string>("Lisbon", "Porto");
var toll = new WeightedEdge<string, decimal>("Lisbon", "Porto", 22.85m);

var (source, target, weight) = toll; // deconstruction

Edge values are ordered pairs — undirected semantics (a-b == b-a) are applied by the graph that stores them, not by the edge itself.

Graphs are mutable adjacency-list structures. Add/Remove follow the .NET collection idiom (bool instead of exceptions), AddEdge auto-adds missing endpoint vertices, and RemoveVertex cascades to incident edges:

using Graph1x;
using Graph1x.Edges;

var graph = new DirectedGraph<string, Edge<string>>();
graph.AddEdge(new Edge<string>("a", "b"));
graph.AddEdge(new Edge<string>("b", "c"));

graph.ContainsEdge("a", "b");   // true
graph.ContainsEdge("b", "a");   // false — direction matters
graph.OutDegree("b");           // 1
graph.RemoveVertex("b");        // also removes a->b and b->c

// Undirected graphs treat endpoints symmetrically and accept custom comparers.
var roads = new UndirectedGraph<string, Edge<string>>(StringComparer.OrdinalIgnoreCase);
roads.AddEdge(new Edge<string>("Lisbon", "Porto"));
roads.ContainsEdge("PORTO", "lisbon"); // true

Self-loops are allowed everywhere except in DAGs (an undirected self-loop counts 2 toward the degree; a directed one counts 1 in + 1 out).

Multigraphs accept parallel edges; DAGs reject anything that would create a cycle:

var flights = new DirectedMultigraph<string, WeightedEdge<string, decimal>>();
flights.AddEdge(new WeightedEdge<string, decimal>("LIS", "OPO", 49.90m));
flights.AddEdge(new WeightedEdge<string, decimal>("LIS", "OPO", 89.90m)); // parallel — allowed
flights.GetEdges("LIS", "OPO");    // both fares

var build = new DirectedAcyclicGraph<string, Edge<string>>();
build.AddEdge(new Edge<string>("compile", "test"));
build.AddEdge(new Edge<string>("test", "package"));
build.AddEdge(new Edge<string>("package", "compile")); // false — would close a cycle

Algorithms live in Graph1x.Algorithms as extension methods. Traversals are lazy iterators (implemented without recursion, so deep graphs cannot overflow the stack):

using Graph1x.Algorithms;

foreach (var v in graph.BreadthFirstSearch("a")) { /* ... */ }
graph.DepthFirstSearch("a");            // pre-order
graph.DepthFirstSearchPostOrder("a");   // post-order

graph.HasCycle();                       // directed or undirected
graph.FindCycle();                      // the cycle's vertices, or null
graph.TopologicalSort();                // Kahn's algorithm; throws GraphCycleException on cycles
graph.FindEulerianCircuit();            // every edge exactly once, or null (Hierholzer)
graph.FindEulerianPath();               // Königsberg says null

Cycle detection understands multigraphs (two parallel undirected edges form a cycle) and self-loops. GraphCycleException carries the offending cycle.

Connectivity queries:

graph.ConnectedComponents();          // direction-agnostic components
graph.IsConnected();                  // at most one component (empty graph: true)
directed.WeaklyConnectedComponents(); // components after forgetting direction
directed.StronglyConnectedComponents(); // Tarjan, iterative; reverse topological order

var condensation = directed.Condense(); // each SCC collapsed to one vertex
condensation.Graph.TopologicalSort();   // the condensation is always a DAG
condensation.ComponentOf("a");          // vertex -> component index
condensation.Members(0);                // component index -> original vertices

Shortest paths default to Dijkstra via the facade; the strategies are swappable behind IShortestPathAlgorithm<,,>:

var route = graph.ShortestPath("LIS", "MAD");            // weighted edges carry the weights
var hops  = graph.ShortestPath("a", "z", _ => 1);        // any edge type + weight selector

route.IsReachable;  // false instead of exceptions for missing routes
route.Distance;     // total weight (throws if unreachable)
route.Path;         // ["LIS", ..., "MAD"]

// Querying many targets from one source? One run, many lookups:
var fromLisbon = graph.ShortestPathsFrom("LIS");
fromLisbon.To("MAD");     // ShortestPathResult, no recomputation
fromLisbon.Distances;     // every reachable vertex at once

// Negative weights? Bellman-Ford (throws NegativeCycleException on negative cycles).
new BellmanFordShortestPath<string, WeightedEdge<string, int>, int>(e => e.Weight)
    .FindPath(graph, "a", "b");

// All pairs at once (Floyd-Warshall), or heuristic-guided search (A*).
new FloydWarshallAllShortestPaths<string, WeightedEdge<string, int>, int>(e => e.Weight)
    .Compute(graph)
    .Between("a", "b");
new AStarShortestPath<Cell, WeightedEdge<Cell, int>, int>(e => e.Weight, Manhattan)
    .FindPath(grid, start, goal);

Dijkstra and A* reject negative weights with NegativeWeightException and point you to Bellman-Ford.

On DAGs, a single topological pass beats both and takes negative weights in stride — plus the longest-path queries that are intractable on general graphs:

dag.DagShortestPathsFrom("compile");    // SingleSourceShortestPaths, negative weights OK
dag.DagLongestPathsFrom("compile");     // same shape, maximizing
dag.CriticalPath();                     // heaviest path anywhere (scheduling/CPM)

These throw GraphCycleException on cyclic input, like TopologicalSort.

Minimum spanning trees (undirected graphs; disconnected input yields a spanning forest):

var forest = network.MinimumSpanningForest();       // Kruskal by default
new PrimMinimumSpanningTree<string, WeightedEdge<string, int>, int>(e => e.Weight)
    .FindMinimumSpanningForest(network);            // or Prim, same interface

Maximum flow (directed networks, non-negative capacities) returns the flow value, per-edge flows, and a minimum cut that certifies optimality:

var result = network.MaximumFlow("source", "sink");   // Edmonds-Karp by default
network.MaximumFlow("s", "t", e => e.Capacity);       // or any capacity selector
new DinicMaximumFlow<string, WeightedEdge<string, int>, int>(e => e.Weight)
    .FindMaximumFlow(network, "s", "t");              // Dinic for large/dense networks

result.FlowValue;           // max flow == min cut capacity
result.EdgeFlows;           // flow per edge (parallel edges listed individually)
result.MinCutEdges;         // the bottleneck edges
result.SourceSideOfMinCut;  // the residual-reachable vertex set

Maximum bipartite matching (undirected bipartite graphs; the partition is derived automatically):

var pairs = graph.MaximumBipartiteMatching(); // Hopcroft-Karp, O(E·√V)

Graphs can be built fluently, and structural queries cover density, degree sequence, bipartiteness, and transpose:

using Graph1x.Builders;

var graph = Graph.DirectedWeighted<string, int>()
    .AddEdge("a", "b", 3)
    .AddEdge("b", "c", 4)
    .Build();                     // typed DirectedGraph<string, WeightedEdge<string, int>>

Graph.Wrap(new DirectedAcyclicGraph<string, Edge<string>>()) // build onto any graph
    .AddVertices("a", "b")
    .Build();

graph.Density();                  // E / V(V-1) directed, 2E / V(V-1) undirected
graph.DegreeSequence();           // descending degrees
graph.IsBipartite();              // 2-colorability (direction ignored)
graph.FindBipartition();          // the two vertex sets, or null
graph.Transpose();                // reversed copy of a directed graph
graph.FindBridges();              // edges whose removal disconnects (undirected)
graph.FindArticulationPoints();   // cut vertices (undirected)
dag.TransitiveClosure();          // u->v for every non-empty path; cycles gain self-loops
dag.TransitiveReduction();        // minimal edge set with the same reachability (DAGs only)

var coloring = graph.ColorVertices();  // DSatur; ColorCount bounds the chromatic number
coloring.ColorOf("a");                 // 0-based color, adjacent vertices always differ

// Set operations return a new graph of the same family (inputs untouched):
graph.Subgraph(["a", "b", "c"]);  // induced: kept vertices + edges between them
first.Union(second);              // all vertices and edges of both (direction must agree)
graph.Complement();               // edge exactly where the original has none (simple graphs)

graph.Diameter();                 // longest shortest path (hops, or pass a weight selector)
graph.Radius();                   // smallest eccentricity
graph.Center();                   // vertices at eccentricity == radius
graph.AveragePathLength();        // mean distance over ordered pairs

Distance metrics require a connected graph (strongly connected when directed) and throw InvalidOperationException otherwise — no sentinel infinities.

Long-running computations (all-pairs paths, centrality, PageRank, flows, closures, metrics, condensation) accept a CancellationToken via additive overloads, checked cooperatively at phase boundaries:

graph.BetweennessCentrality(cancellationToken);
network.MaximumFlow(s, t, e => e.Capacity, cancellationToken);

The per-source analyses — betweenness, closeness, and the distance metrics — are embarrassingly parallel, and overloads taking a ParallelOptions (degree of parallelism plus cancellation token) run them on all cores. The sequential paths stay untouched as the reference implementations:

var options = new ParallelOptions { MaxDegreeOfParallelism = 4 };
graph.BetweennessCentrality(options);   // per-source Brandes passes in parallel
graph.ClosenessCentrality(options);     // bit-identical to the sequential result
graph.Diameter(options);                // also Radius, Center, Periphery, AveragePathLength

Centrality measures answer "which vertices matter":

graph.DegreeCentrality();          // degree / (V-1)
graph.ClosenessCentrality();       // Wasserman-Faust scaled; disconnected graphs fine
graph.BetweennessCentrality();     // Brandes; weighted overload takes a selector
network.PageRank(damping: 0.85);   // directed; ranks sum to 1, dangling nodes handled
graph.EigenvectorCentrality();     // shifted power iteration, bipartite-safe
graph.KatzCentrality(alpha: 0.1);  // stays meaningful on DAGs, where eigenvector degenerates

// Clustering: how close each neighborhood is to a clique (direction ignored).
graph.LocalClusteringCoefficient("a");
graph.ClusteringCoefficients();        // all vertices at once
graph.AverageClusteringCoefficient();
graph.GlobalClusteringCoefficient();   // transitivity: 3·triangles / connected triples

// Maximal cliques: lazy Bron–Kerbosch, so partial enumeration stays cheap.
graph.EnumerateMaximalCliques().Take(10);

For dense graphs, DirectedAdjacencyMatrixGraph and UndirectedAdjacencyMatrixGraph offer O(1) edge lookup behind the exact same IMutableGraph contract (they pass the same contract test suite as the adjacency-list types).

Hypergraphs (edges joining any number of vertices) are a standalone type with their own incidence and connectivity queries:

using Graph1x.Hypergraphs;

var teams = new Hypergraph<string>();
var kickoff = teams.AddHyperedge("ana", "bruno", "carla"); // returns a handle
teams.Degree("ana");             // number of incident hyperedges
teams.AreConnected("ana", "dora");
teams.ConnectedComponents();
teams.RemoveHyperedge(kickoff);

// Expansions bridge hypergraphs into the full algorithm suite:
teams.ToCliqueExpansion();          // co-membership graph (2-section)
teams.ToBipartiteIncidenceGraph();  // lossless vertex/hyperedge bipartite graph

Ready-made structures for tests, demos, and benchmarks come from GraphGenerator (ErdosRenyi(n, p, seed), Complete(n), Grid(w, h), …) — seeded, so results are reproducible. For realistic degree distributions there are BarabasiAlbert(n, m, seed) (preferential attachment, scale-free) and WattsStrogatz(n, k, p, seed) (ring lattice with rewiring, small-world).

Hand out graphs without handing out mutation — live views and immutable snapshots both stay fully algorithm-compatible (directed views keep directed dispatch):

IReadOnlyGraph<string, Edge<string>> view = graph.AsReadOnly(); // live, not castable to IMutableGraph
var snapshot = graph.ToFrozen();                                // deep copy, safe for concurrent readers

Any graph renders to Graphviz DOT for quick visualization (dot -Tsvg):

using Graph1x.Serialization;

var dot = graph.ToDot();                                  // digraph/graph picked automatically
graph.ToDot(new DotExportOptions<string, WeightedEdge<string, int>>
{
    GraphName = "network",
    EdgeLabel = e => e.Weight.ToString(),                 // [label="…"] per edge
});

Mermaid output drops straight into GitHub markdown or docs pages — nodes get safe synthetic ids with the display label attached:

var mermaid = graph.ToMermaid();                          // flowchart TD, --> or --- picked automatically
graph.ToMermaid(new MermaidExportOptions<string, WeightedEdge<string, int>>
{
    Direction = MermaidDirection.LeftToRight,             // flowchart LR
    EdgeLabel = e => e.Weight.ToString(),                 // -->|"…"| per edge
});

GraphML round-trips for persistence and interop with other tools:

var xml = graph.ToGraphMl();                    // weights via GraphMlExportOptions.EdgeWeight
var restored = GraphMl.Parse(xml);              // direction auto-detected from edgedefault
GraphMl.ParseDirectedWeighted(xml);             // typed weighted variants

Arbitrary vertex/edge attributes survive the round-trip — declare them once and the same declaration drives GraphML (typed <key> elements) and JSON (typed properties):

var xml = graph.ToGraphMl(new GraphMlExportOptions<City, Edge<City>>
{
    VertexAttributes =
    [
        GraphAttribute<City>.String("name", c => c.Name),
        GraphAttribute<City>.Int("population", c => c.Population),
    ],
});

var doc = GraphMl.ParseDocument(xml);       // GraphJson.ParseDocument for JSON
doc.Graph;                                  // the structure, as usual
doc.VertexData["Lisbon"]["population"];     // 545000 — typed per the key declaration
doc.EdgeData[0];                            // per-edge attributes, in insertion order

JSON uses the node-link shape shared with NetworkX/D3 ({ "directed": …, "nodes": […], "edges": […] }), written without reflection:

var json = graph.ToJson();                      // weights via GraphJsonExportOptions.EdgeWeight
GraphJson.Parse(json);                          // direction auto-detected
GraphJson.ParseUndirectedWeighted(json);        // typed weighted variants

License

Copyright 2026 Luís Amorim. Licensed under the Apache License 2.0.