Use Linq to define circular dependency, string properties
Imagine an object like this
public class ContentType
{
public string Alias { get; set;}
public string ParentAlias { get; set;}
}
And a flat collection of these objects
List<ContentType> contentTypes...;
How can I use the linq related syntax query to determine if a circular reference exists in a collection.
//Example
ContentType #50
Alias: Truck
ParentAlias: Vehicle
ContentType #90
Alias: Vehicle
ParentAlias: Truck
It would be a circular dependency that would break the code that creates content types (it would get stuck in an endless loop traversing parent hierarchies ..)
Therefore, before handling the parent / child content types, I would like to first determine if there is a circular dependency in the collection and stop the operation if found.
source to share
So, we'll start with two helper methods. First we need a method that gives all the ancestors for an element when that element is given and a delegate that gets the parent of the element:
public static IEnumerable<T> Ancestors<T>(T item, Func<T, T> parentSelector)
{
while (item != null)
{
item = parentSelector(item);
yield return item;
}
}
We'll also write a method to determine if the sequence repeats, keeping all previously received elements and seeing if there is every new element in this set:
public static bool Repeats<T>(
this IEnumerable<T> sequence,
IEqualityComparer<T> comparer = null)
{
comparer = comparer ?? EqualityComparer<T>.Default;
var set = new HashSet<T>(comparer);
foreach (var item in sequence)
if (!set.Add(item))
return true;
return false;
}
From here, we can determine if any sequence contains loops by calculating the ancestors of each element and determining if any of those collections is repeated:
public static bool ContainsCycles<T>(IEnumerable<T> sequence,
Func<T, T> parentSelector,
IEqualityComparer<T> comparer = null)
{
comparer = comparer ?? EqualityComparer<T>.Default;
return sequence.Any(item => Ancestors(item, parentSelector).Repeats(comparer));
}
All that's left is to write a method that calculates the parent of each element, since this is not an operation that your class already supports, which can be done by simply creating a search from an alias for the element and then using that:
IEnumerable<ContentType> types = CreateContentTypes();
var lookup = types.ToDictionary(type => type.Alias);
bool anyCycles = ContainsCycles(types, type => lookup[type.ParentAlias]);
In terms of performance and potential improvements, if you are dealing with especially large trees / subtrees, you can cache the results of intermediate computations. For example, if we have node A, and parent B and grandparent C, which is the root, then when doing a computation to determine if A is in a loop, we also need to determine if B is in a loop. If we already determined if B was previously in the loop and cached it, we could skip this step. if we didn't, then we could cache it when we execute the loop calculator for A, and then we don't need to do it again when you check B later.
This complicates the code in a fair bit, so unless you have a particularly large / deep graph, you can avoid wasting time caching these intermediate results and just re-calculate them for each element:
public static bool IsInCycle<T>(
this IEnumerable<T> sequence,
HashSet<T> itemsNotInASequence,
IEqualityComparer<T> comparer = null)
{
comparer = comparer ?? EqualityComparer<T>.Default;
var set = new HashSet<T>(comparer);
foreach (var item in sequence)
{
if (itemsNotInASequence.Contains(item))
return false;
else if (!set.Add(item))
return true;
}
itemsNotInASequence.UnionWith(set);
return false;
}
public static bool ContainsCycles<T>(IEnumerable<T> sequence,
Func<T, T> parentSelector,
IEqualityComparer<T> comparer = null)
{
comparer = comparer ?? EqualityComparer<T>.Default;
var itemsNotInASequence = new HashSet<T>(comparer);
return sequence.All(item => Ancestors(item, parentSelector)
.IsInCycle(itemsNotInASequence));
}
source to share