CycleDetection 2.0.0

.NET Core 2.0 .NET Standard 1.0 .NET Framework 4.0
dotnet add package CycleDetection --version 2.0.0
NuGet\Install-Package CycleDetection -Version 2.0.0
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="CycleDetection" Version="2.0.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add CycleDetection --version 2.0.0
#r "nuget: CycleDetection, 2.0.0"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. Copy this into the interactive tool or source code of the script to reference the package.
// Install CycleDetection as a Cake Addin
#addin nuget:?package=CycleDetection&version=2.0.0

// Install CycleDetection as a Cake Tool
#tool nuget:?package=CycleDetection&version=2.0.0

This is a fork of Daniel Bradley's C# implementation of the Tarjan cycle detection algorithm.

IOW: You can use this library to sort dependencies and even handle cyclic references. e.g. to compile stuff in the right order.

I found it to be quite useful but I didn't like how one had to manually setup the dependency vertices. (It also supports custom comparers now.)

So I moved the original code into the Core sub namespace and wrote a class that allows to setup dependencies using a simple lambda expression.

The easiest way to use it is to install the nuget package.

This example shows a case in which A depends on B, B depends on C but C depends on A. Thus creating a cyclic dependency. There's also D which depends on B.

// A→B
// ↑ ↓
// └─C

var graph = new[]
{
  new{Value ="D", DependsOn = "B"},
  new{Value ="A", DependsOn = "B"},
  new{Value ="B", DependsOn = "C"},
  new{Value ="C", DependsOn = "A"},
};

var components = graph.DetectCyclesUsingKey(
    s => s.Value,
    s => s.DependsOn);

Assert.AreEqual(2, components.Count); // 1 cycle + D
Assert.AreEqual(1, components.IndependentComponents().Count()); // only D is outside the cycle
Assert.AreEqual(1, components.Cycles().Count()); // 1 cycle
Assert.AreEqual(3, components[0].Count); // the cycle has 3 components
Assert.AreEqual("D", components[1].Single().Value); // D is after the cycle, because it depends on it

I also added a way to merge cyclic dependencies into a single entity. Which is probably not that interesting for most. However, I use it to have a merged assembly from every cycle of interconnected Jars when I compile them using IKVMC. And have that merged assembly name as the reference for the other Jar-assemblies.

var mergedGraph = components.MergeCyclicDependencies((cycle, getMerged) => new
                  {
                    Value = cycle.Contents.OrderBy(t => t.Value)
                                          .Aggregate("", (r, c) => r + "-" + c.Value).TrimStart('-'),
                    DependsOn = (from d in cycle.Dependencies
                                 select (getMerged(d) ?? d.Single()).Value).SingleOrDefault()
                  });

Result

{ Value = "A-B-C", DependsOn = null } -> the name reflects all included items
{ Value = "D", DependsOn = "A-B-C" } -> D now references the new name (thx to "getMerged")

Original Readme:

Just decided to put together a c# project for an implementation of the Tarjan cycle detection algorithm as I can't seem to find any out there already.

The original code for this was posted on stackoverflow by user623879.

Hope this is useful!

Product Versions
.NET net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows net7.0 net7.0-android net7.0-ios net7.0-maccatalyst net7.0-macos net7.0-tvos net7.0-windows
.NET Core netcoreapp1.0 netcoreapp1.1 netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1
.NET Standard netstandard1.0 netstandard1.1 netstandard1.2 netstandard1.3 netstandard1.4 netstandard1.5 netstandard1.6 netstandard2.0 netstandard2.1
.NET Framework net40 net403 net45 net451 net452 net46 net461 net462 net463 net47 net471 net472 net48
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen30 tizen40 tizen60
Universal Windows Platform uap uap10.0
Windows Phone wp8 wp81 wpa81
Windows Store netcore netcore45 netcore451
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.

NuGet packages (1)

Showing the top 1 NuGet packages that depend on CycleDetection:

Package Downloads
TngTech.ArchUnitNET

C# Version of ArchUnit (see: archunit.org)

GitHub repositories (1)

Showing the top 1 popular GitHub repositories that depend on CycleDetection:

Repository Stars
TNG/ArchUnitNET
A C# architecture test library to specify and assert architecture rules in C# for automated testing.
Version Downloads Last updated
2.0.0 664,280 3/8/2019
1.0.1.1 12,050 11/18/2013
1.0.0 1,024 11/14/2013