CycleDetection 2.0.0
This is a fork of Daniel Bradley's C# implementation of the Tarjan cycle detection algorithm. (https://github.com/danielrbradley/CycleDetection)
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.
Install-Package CycleDetection -Version 2.0.0
dotnet add package CycleDetection --version 2.0.0
<PackageReference Include="CycleDetection" Version="2.0.0" />
paket add 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!
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!
Dependencies
-
.NETCoreApp 2.0
- System.Collections.Immutable (>= 1.5.0)
-
.NETFramework 4.0
- No dependencies.
-
.NETFramework 4.5
- System.Collections.Immutable (>= 1.5.0)
-
.NETStandard 1.0
- NETStandard.Library (>= 1.6.1)
- System.Collections.Immutable (>= 1.5.0)
-
.NETStandard 1.1
- NETStandard.Library (>= 1.6.1)
- System.Collections.Immutable (>= 1.5.0)
Used By
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
This package is not used by any popular GitHub repositories.