Graffs 0.1.0

Graffs

A high-performance directed graph library for .NET 8.

Features

• Graph Implementations: Adjacency list, adjacency matrix, and compact CSR format
• Topological Sorting: Kahn's algorithm and DFS-based sorting with cycle detection
• Cycle Detection: Johnson's algorithm for finding all elementary cycles
• Connectivity Analysis: Strongly connected components (Tarjan's) and weakly connected components (Union-Find)
• Path Finding: BFS shortest path and DFS all simple paths
• Graph Slicing: Dependency chain analysis and parallel execution level partitioning
• Fluent Builders: Easy graph construction with GraphBuilder<T> and DependencyGraphBuilder<T>

Installation

dotnet add package Graffs --version 0.1.0

Core Concepts

Nodes and Node Identity

Graffs graphs are generic over node type (TNode). Nodes can be any type that is non-null and properly implements equality (via Equals and GetHashCode). The graph uses node equality to identify and distinguish nodes.

Simple nodes - Use primitive types like string or int directly as node identifiers:

// Strings as node keys
var graph = new GraphBuilder<string>()
    .AddEdge("A", "B")
    .AddEdge("B", "C")
    .Build();

// Integers as node keys
var graph = new GraphBuilder<int>()
    .AddEdge(1, 2)
    .AddEdge(2, 3)
    .Build();

Rich nodes - Use custom types implementing IGraphNode<TKey> for nodes that carry additional data:

// IGraphNode<TKey> provides a standard way to expose node identity
public interface IGraphNode<out TKey> where TKey : notnull
{
    TKey Id { get; }              // Unique identifier for this node
    string? DisplayName { get; }  // Optional human-readable name
}

// Example: A task node with metadata
public class TaskNode : IGraphNode<string>
{
    public string Id { get; }
    public string? DisplayName { get; }
    public TimeSpan EstimatedDuration { get; }

    public TaskNode(string id, string? displayName = null, TimeSpan? duration = null)
    {
        Id = id;
        DisplayName = displayName;
        EstimatedDuration = duration ?? TimeSpan.Zero;
    }

    // Important: Override Equals/GetHashCode based on Id for graph operations
    public override bool Equals(object? obj) => obj is TaskNode other && Id == other.Id;
    public override int GetHashCode() => Id.GetHashCode();
}

// Use rich nodes in a graph
var compile = new TaskNode("compile", "Compile Source", TimeSpan.FromMinutes(2));
var test = new TaskNode("test", "Run Tests", TimeSpan.FromMinutes(5));
var deploy = new TaskNode("deploy", "Deploy App", TimeSpan.FromMinutes(1));

var graph = new DependencyGraphBuilder<TaskNode>()
    .DependsOn(test, compile)    // test depends on compile
    .DependsOn(deploy, test)     // deploy depends on test
    .Build();

Note: IGraphNode<TKey> is optional. It provides a standardized interface for node identification and display, which can be useful for debugging, logging, or when building tooling around graphs. Your nodes work with Graffs as long as they implement proper equality semantics.

Quick Start

using Graffs;
using Graffs.Builders;
using Graffs.Algorithms;

// Build a dependency graph using string keys
var graph = new DependencyGraphBuilder<string>()
    .DependsOn("C", "A")  // C depends on A (edge: A → C)
    .DependsOn("C", "B")  // C depends on B (edge: B → C)
    .DependsOn("D", "C")  // D depends on C (edge: C → D)
    .Build();

// Topological sort - returns nodes in dependency order
var result = TopologicalSort.KahnSort(graph);
// Result: [A, B, C, D] or [B, A, C, D] (dependencies come before dependents)

// Check for cycles
bool hasCycles = CycleDetection.HasCycles(graph);

// Find strongly connected components
var sccResult = ConnectivityAnalysis.FindStronglyConnectedComponents(graph);

Graph Implementations

Algorithms

Topological Sort

// Kahn's algorithm (BFS-based)
var result = TopologicalSort.KahnSort(graph);

// DFS-based with cycle detection
var result = TopologicalSort.DfsSort(graph);

// Stable sort with custom ordering
var result = TopologicalSort.StableSort(graph, StringComparer.Ordinal);

Cycle Detection

// Quick check
bool hasCycles = CycleDetection.HasCycles(graph);

// Find all cycles
var result = CycleDetection.FindAllCycles(graph);
foreach (var cycle in result.Cycles)
{
    Console.WriteLine(cycle.ToPathString());
}

Connectivity Analysis

// Strongly connected components
var scc = ConnectivityAnalysis.FindStronglyConnectedComponents(graph);

// Weakly connected components
var wcc = ConnectivityAnalysis.FindWeaklyConnectedComponents(graph);

// Reachability
var reachable = ConnectivityAnalysis.FindReachableNodes(graph, startNode);

Path Finding

// Shortest path
var path = PathFinding.FindShortestPath(graph, source, target);

// All simple paths
var paths = PathFinding.FindAllSimplePaths(graph, source, target, maxPaths: 100);

Graph Slicing

// Analyze dependency structure for parallel execution
var slicing = GraphSlicer.AnalyzeDependencyStructure(graph);
foreach (var level in slicing.Levels)
{
    // Nodes at each level can be processed in parallel
    Console.WriteLine($"Level {level.LevelIndex}: {string.Join(", ", level.Nodes)}");
}

License

MIT License - see LICENSE for details.