I have a collection:
List<VPair<Item, List<Item>> dependencyHierarchy;
The first item in pair is some object (item) and the second one is a collection of the same type objects that the first one depends on. I want to get a List<Item>
in order of dependency, so there are not items that depend on the first element and so on (no cycled dependency!).
Input:
Item4 depends on Item3 and Item5 Item3 depends on Item1 Item1 does not depend on any one Item2 depends on Item4 Item5 does not depend on any one
Result:
Item1 Item5 Item3 Item4 Item2
Thank you.
SOLUTION:
Topological Sorting (thanks to Loïc Février for idea)
and
example on C#, example on Java (thanks to xcud for great examples)
Perfect example to use a topological sort:
http://en.wikipedia.org/wiki/Topological_sorting
It will give you exactly what you need.
You can either use Kahn's algorithm:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
...or you can use Depth-first search:
L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
if n has a temporary mark then
stop (not a DAG)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
remove temporary mark from n
mark n with a permanent mark
add n to head of L
Having struggled with this for a while, here's my attempt at a Linq style TSort extension method:
public static IEnumerable<T> TSort<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false )
{
var sorted = new List<T>();
var visited = new HashSet<T>();
foreach( var item in source )
Visit( item, visited, sorted, dependencies, throwOnCycle );
return sorted;
}
private static void Visit<T>( T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle )
{
if( !visited.Contains( item ) )
{
visited.Add( item );
foreach( var dep in dependencies( item ) )
Visit( dep, visited, sorted, dependencies, throwOnCycle );
sorted.Add( item );
}
else
{
if( throwOnCycle && !sorted.Contains( item ) )
throw new Exception( "Cyclic dependency found" );
}
}
There's a nuget for that.
For those of us who prefer not to re-invent the wheel: use nuget to install the QuickGraph .NET library, which includes multiple graph algorithms including topological sort.
To use it, you need to create an instance of AdjacencyGraph<,>
such as AdjacencyGraph<String, SEdge<String>>
. Then, if you include the appropriate extensions:
using QuickGraph.Algorithms;
You can call:
var sorted = myGraph.TopologicalSort();
To get a list of sorted nodes.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With