如何在EF生成的多对多自参考关系中检测参考循环

Question

我有一个对象集合，如下面的示例Foo：

public class Foo
{
public long Id { get; set; }
public IEnumerable<Foo> FooParents { get; set; }
public IEnumerable<Foo> FooChildren { get; set; }
}

这些对象通过属性CCD_ 2和CCD_。

如何有效地检测特定Foo的循环依赖关系？

我知道，如果是一对多，该怎么办，但如果是多对多，我有点困惑。

：(

谢谢！

Answer 1

下面是一个带有一些测试的实现。

这是一个执行Depth-FirstS搜索的通用解决方案行为专门针对你的问题领域。它在soFar哈希集中保留访问节点的历史记录，当遇到重复或指定分支上的路径用完时完成。

重复表示循环关系。

此扩展方法必须提供多个委托。首先是一个键选择器，它为每个项目生成一个唯一的标识符。然后是表示分支的任意数量的轴选择器，对象图在其上扩展。

有趣的扩展方法在这里，

public static bool IsCircular<T, K>(
this T item,
Func<T, K> keySelector, 
params Func<T, IEnumerable<T>>[] axes)
{
var soFar = new HashSet<K>();
soFar.Add(keySelector(item));
return axes.Any(axis =>
axis(item).Any(next => IsCircularOnAxis(
next,
keySelector,
axis,
soFar)));
}
private static bool IsCircularOnAxis<T, K>(
T item,
Func<T, K> keySelector,
Func<T, IEnumerable<T>> axisSelector, 
HashSet<K> soFar)
{
var key = keySelector(item);
if(soFar.Contains(key))
{
return true;
}
soFar.Add(key);
return axisSelector(item).Any(next => 
IsCircularOnAxis(
next,
keySelector,
axisSelector,
soFar));
}

在Foo的这种情况下，扩展方法可以这样调用，

someFoo.IsCircular(
foo => foo.Id,           /*The key selector*/
foo => foo.FooParents,   /*The parent axis selector*/
foo => foo.FooChildren); /*The child axis selector*/

完整的工作示例在这里，并对Foo进行了一些测试。

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
public static void Main()
{
var soloFoo = new Foo
{
Id = 1,
FooParents = Enumerable.Empty<Foo>(),
FooChildren = Enumerable.Empty<Foo>(),
};
Console.WriteLine($"soloFoo isCircular:{soloFoo.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");

var selfParent = new Foo
{
Id = 1,
FooChildren = Enumerable.Empty<Foo>(),
};
selfParent.FooParents = new[] { selfParent };
Console.WriteLine($"selfParent isCircular:{selfParent.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");


var selfChild = new Foo
{
Id = 1,
FooParents = Enumerable.Empty<Foo>(),
};
selfChild.FooChildren = new[] { selfChild };
Console.WriteLine($"selfChild isCircular:{selfChild.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");

var parentFoo = new Foo
{
Id = 1,
FooParents = Enumerable.Empty<Foo>(),
FooChildren = Enumerable.Empty<Foo>(),
};
var childFoo = new Foo
{
Id = 2,
FooParents = Enumerable.Empty<Foo>(),
FooChildren = Enumerable.Empty<Foo>(),
};
var middleFoo = new Foo
{
Id = 3,
FooParents = new[] { parentFoo },
FooChildren = new[] { childFoo },
};
Console.WriteLine($"middleFoo isCircular:{middleFoo.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");

var ringFooA = new Foo
{
Id = 1,
};
var ringFooB = new Foo
{
Id = 2,
FooParents = new[] { ringFooA },
};
var ringFooC = new Foo
{
Id = 3,
FooParents = new[] { ringFooB },
FooChildren = new[] { ringFooA },
};
ringFooA.FooParents = new[] { ringFooC };
ringFooA.FooChildren = new[] { ringFooB };
ringFooB.FooChildren = new[] { ringFooC };
Console.WriteLine($"ringFooA isCircular:{ringFooA.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");
Console.WriteLine($"ringFooB isCircular:{ringFooB.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");
Console.WriteLine($"ringFooC isCircular:{ringFooC.IsCircular(foo => foo.Id, foo => foo.FooParents, foo => foo.FooChildren)}");
}
}
public static class Extensions
{
public static bool IsCircular<T, K>(
this T item,
Func<T, K> keySelector, 
params Func<T, IEnumerable<T>>[] axes)
{
var soFar = new HashSet<K>();
soFar.Add(keySelector(item));
return axes.Any(axis =>
axis(item).Any(next => IsCircularOnAxis(
next,
keySelector,
axis,
soFar)));
}
private static bool IsCircularOnAxis<T, K>(
T item,
Func<T, K> keySelector,
Func<T, IEnumerable<T>> axisSelector, 
HashSet<K> soFar)
{
var key = keySelector(item);
if(soFar.Contains(key))
{
return true;
}
soFar.Add(key);
return axisSelector(item).Any(next => 
IsCircularOnAxis(
next,
keySelector,
axisSelector,
soFar));
}
}
public class Foo
{
public long Id { get; set; }
public IEnumerable<Foo> FooParents { get; set; }
public IEnumerable<Foo> FooChildren { get; set; }
}