Skip to content

Caveat1.ja

houzkin edited this page Nov 12, 2026 · 3 revisions

留意点

循環のある階層構造をラップする

以下のコードで、layerAとlayerCが循環した状態で、それぞれのラッパーノードをルートとしてラップしています。

var layerA = new NamedLayer() { Name = "A" };
var layerB = new NamedLayer() { Name = "B" };
var layerC = new NamedLayer() { Name = "C" };
var layerD = new NamedLayer() { Name = "D" };

layerA.ChildLayers.Add(layerB);
layerA.ChildLayers.Add(layerC);
layerA.ChildLayers.Add(layerD);
layerC.ChildLayers.Add(layerA);//cycle

var wrpr1 = layerA.AsValuedTreeNode(x => x.ChildLayers, x => x);
Console.WriteLine(wrpr1.ToTreeDiagram(x => x.Value.Name));
Console.WriteLine($"PreOrder: {string.Join(',', wrpr1.PreOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"PostOrder: {string.Join(',', wrpr1.PostOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"LevelOrder: {string.Join(',', wrpr1.LevelOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"InOrder: {string.Join(',', wrpr1.InOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"Leafs: {string.Join(',', wrpr1.Leafs().Select(x => x.Value.Name))}");
Console.WriteLine($"Upstream: {string.Join(',', wrpr1.Upstream().Select(x => x.Value.Name))}");
/*
A
├ B
├ C
└ D

PreOrder: A,B,C,D
PostOrder: B,A,C,D   <- Discrepancy with the tree diagram
LevelOrder: A,B,C,D
InOrder: B,A,C,D
Leafs: B,A,D   <- Discrepancy with the tree diagram
Upstream: A
*/

var wrpr2C = layerC.AsValuedTreeNode(x => x.ChildLayers, x => x);
Console.WriteLine(wrpr2C.ToTreeDiagram(x => x.Value.Name));
Console.WriteLine($"PreOrder: {string.Join(',', wrpr2C.PreOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"PostOrder: {string.Join(',', wrpr2C.PostOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"LevelOrder: {string.Join(',', wrpr2C.LevelOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"InOrder: {string.Join(',', wrpr2C.InOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"Leafs: {string.Join(',', wrpr2C.Leafs().Select(x => x.Value.Name))}");
Console.WriteLine($"Upstream: {string.Join(',', wrpr2C.Upstream().Select(x => x.Value.Name))}");
/*
C
└ A
  ├ B
  └ D

PreOrder: C,A,B,D
PostOrder: B,C,D,A   <- Discrepancy with the tree diagram
LevelOrder: C,A,B,D
InOrder: B,A,C,D   <- Discrepancy with the tree diagram
Leafs: B,C,D   <- Discrepancy with the tree diagram
Upstream: C
*/

ノードの列挙において、重複するノードは除外されるので無限ループは発生しません。
しかし、PostOrder、InOrder、Leafsでの列挙の結果は、ツリー表示と異なっています。
ToTreeDiagramメソッドは内部でPreOrderを使って列挙しており、各メソッド内の走査でどちらのノードへ先にアクセスしたかに起因しています。

また、以下のようにChildrenプロパティからのアクセスや、layerAのラッパーを起点とする列挙によって、除外されていた位置のラッパーにアクセスできます。

Console.WriteLine(string.Join(",",
    wrpr2C.LevelOrder().First(x => x.Value.Name == "A")
    .Children.Select(x => x.Value.Name)));
//B,C,D

var wrpr2A = wrpr2C.LevelOrder().First(x=>x.Value.Name == "A");
Console.WriteLine(wrpr2A.ToTreeDiagram(x => x.Value.Name));
Console.WriteLine($"PreOrder: {string.Join(',', wrpr2A.PreOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"PostOrder: {string.Join(',', wrpr2A.PostOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"LevelOrder: {string.Join(',', wrpr2A.LevelOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"InOrder: {string.Join(',', wrpr2A.InOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"Leafs: {string.Join(',', wrpr2A.Leafs().Select(x => x.Value.Name))}");
Console.WriteLine($"Upstream: {string.Join(',', wrpr2A.Upstream().Select(x => x.Value.Name))}");
/*
A
├ B
├ C
└ D

PreOrder: A,B,C,D
PostOrder: B,A,C,D   <- Discrepancy with the tree diagram
LevelOrder: A,B,C,D
InOrder: B,A,C,D
Leafs: B,A,D   <- Discrepancy with the tree diagram
Upstream: A,C   <- Discrepancy with the tree diagram
*/

対処法としては、Convert()で変換またはToNodeMap().AssembleTree()によって再構築することが考えられます。

var newWrpr1 = wrpr1
  .Convert(x => new NamedLayer() { Name = x.Value.Name }, (p, c) => p.ChildLayers.Add(c))
  .AsValuedTreeNode(x => x.ChildLayers, x => x);

Console.WriteLine(newWrpr1.ToTreeDiagram(x => x.Value.Name));
Console.WriteLine($"PreOrder: {string.Join(',', newWrpr1.PreOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"PostOrder: {string.Join(',', newWrpr1.PostOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"LevelOrder: {string.Join(',', newWrpr1.LevelOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"InOrder: {string.Join(',', newWrpr1.InOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"Leafs: {string.Join(',', newWrpr1.Leafs().Select(x => x.Value.Name))}");
Console.WriteLine($"Upstream: {string.Join(',', newWrpr1.Upstream().Select(x => x.Value.Name))}");
/*
A
├ B
├ C
└ D

PreOrder: A,B,C,D
PostOrder: B,C,D,A
LevelOrder: A,B,C,D
InOrder: B,A,C,D
Leafs: B,C,D
Upstream: A
*/

var newWrpr2C = wrpr2C
  .ToNodeMap(x => x.Value.Name)
  .AssembleTree(x => new NamedLayer() { Name = x }, (p, c) => p.ChildLayers.Add(c))
  .AsValuedTreeNode(x => x.ChildLayers, x => x);

Console.WriteLine(newWrpr2C.ToTreeDiagram(x => x.Value.Name));
Console.WriteLine($"PreOrder: {string.Join(',', newWrpr2C.PreOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"PostOrder: {string.Join(',', newWrpr2C.PostOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"LevelOrder: {string.Join(',', newWrpr2C.LevelOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"InOrder: {string.Join(',', newWrpr2C.InOrder().Select(x => x.Value.Name))}");
Console.WriteLine($"Leafs: {string.Join(',', newWrpr2C.Leafs().Select(x => x.Value.Name))}");
Console.WriteLine($"Upstream: {string.Join(',', newWrpr2C.Upstream().Select(x => x.Value.Name))}");
/*
C
└ A
  ├ B
  └ D

PreOrder: C,A,B,D
PostOrder: B,D,A,C
LevelOrder: C,A,B,D
InOrder: B,A,D,C
Leafs: B,D
Upstream: C
*/

ConvertとToNodeMapメソッドは内部でLevelOrderを使用しています。

TreeNodeで循環を実演

TreeNodeBase系譜のノードは追加時にCanAddChildNodeメソッドにて循環と重複のチェックを行っています。
このメソッドをオーバーライドする場合は、必ず基底クラスのメソッドを呼び出してください。
呼び出さなかった場合、循環と重複を許容してしまい、親ノードと子ノードの相互参照が破綻する可能性があります。

public class LoopNode : NamedNode {
	protected override bool CanAddChildNode(NamedNode child) {
		if (child is null) return false;
		else return true;
	}
}
var nodeA = new LoopNode() { Name = "A" };
var nodeB = new LoopNode() { Name = "B" };
var nodeC = new LoopNode() { Name = "C" };
var nodeD = new LoopNode() { Name = "D" };

nodeA.AddChild(nodeB)
  .AddChild(nodeC)
  .AddChild(nodeD);

nodeC.AddChild(nodeA);

Console.WriteLine(nodeA.ToTreeDiagram(x => x.Name));
/*
A
├ B
├ C
└ D
*/
Console.WriteLine(nodeC.ToTreeDiagram(x => x.Name));
/*
C
└ A
  ├ B
  └ D
*/

Clone this wiki locally