Noamice's Insight #1 収束する木構造の表現

この記事は？

のあみすが仕事で必要となりそうなプログラムについて書いたり書かなかったりする記事。

収束する木構造

通常の木構造はルートとなる要素から拡散するような構造をとる。従って1対多構造となるようなものとなり、末端は複数の要素になる。要素から拡散する最大数を限定した構造としてn分木と表現することもある。

収束する木構造とは、1対多構造と多対1構造のどちらも持ちつつも、ルート要素と末端要素はかならずそれぞれ1つの要素になる。たとえば構造化プログラムにおけるフローチャートやPERT図などがこの構造を持つ。
既に名前がある構造なのかもしれないが、調べたところそれっぽいものが見つからなかったのでとりあえず今回は収束木(Convergence Tree)と名付けることにする。

制約の洗い出し

ここで、収束木の制約について整理する。

• 単一のルートノードを持つ。
• 単一の末端ノードを持つ。
• ノード数をnとしたとき、1 < nであれば、ルートノードと末端ノードは別のノードでなくてはならない。
• ノードは複数の子を持つことが出来る。
• ノードは複数の親からなることができる。
• ノードは自身の子孫である子ノード以外のノードを子ノードとして持つことが出来ない。

単一のルートノード/末端ノードを持つため、リスト構造にすれば自然にルート/末端が定まる。残りの親子関係については多次元配列ライクな実装にすればうまくいく気がする。

さあコードにしよう

まずインターフェースで考えていく。

/// <summary>
/// ノード1つ、あるいは複数のノードの集約を示す要素1つとしての機能を提供するインターフェース。
/// </summary>
public interface IConvergenceTreeElement
{

}

/// <summary>
/// 収束木としての機能を提供するインターフェース。
/// </summary>
/// <typeparam name="T">ノード</typeparam>
public interface IConvergenceTree<T> : ICollection<T> where T : IConvergenceTreeElement
{

}

/// <summary>
/// 複数ノードを集約する要素のコレクションインターフェース。
/// </summary>
/// <typeparam name="T1"></typeparam>
/// <typeparam name="T2"></typeparam>
public interface IConvergenceTreeClusterCollection<T1, T2> : ICollection<T1> where T1 : IConvergenceTree<T2> where T2 : IConvergenceTreeElement
{

}

/// <summary>
/// ノード1つとしての機能を提供するインターフェース。
/// </summary>
public interface IConvergenceTreeItem : IConvergenceTreeElement
{

}

構造を表現するために必要なインターフェースはこれくらいで済むらしい。

public class ConvergenceTree : List<IElement>, IConvergenceTree<IElement>
{
    public int TotalCount => this.Select(item =>
    {
        switch (item)
        {
            case ConvergenceTreeClusterCollection clusterCollection:
                return clusterCollection.Sum(cluster => cluster.TotalCount);
            default:
                return 1;
        }
    }).Sum();

    public bool ContainsRecursive(IElement item) => this.Any(i =>
    {
        switch (i)
        {
            case ConvergenceTreeClusterCollection clusterCollection:
                return clusterCollection.ContainsRecursive(item);
            default:
                return i.Equals(item);
        }
    });
}

public class ConvergenceTreeItem : IElement, IConvergenceTreeItem
{
    public Guid ID { get; set; }
}

public class ConvergenceTreeClusterCollection : List<ConvergenceTree>, IElement, IConvergenceTreeClusterCollection<ConvergenceTree, IElement>
{
    public int TotalCount => this.Sum(item => item.TotalCount);

    public bool ContainsRecursive(IElement item) => this.Any(i => i.ContainsRecursive(item));
    
    public Guid ID { get; set; }
}

public interface IElement : IConvergenceTreeElement
{
    Guid ID { get; }
}

実装はこれくらいで。細かいロジックについては今回はいったんおいとく。

何がしたいか

お絵描きツールのような何かを作ることになったのだけど、単純にいろんなアイテムを置くのではなく、この収束木のような構造でアイテムを配置する必要があるので、ドメイン層でそのデータ構造を示すのにどんな感じにすればいいか、というお話でした。次回はお絵描き側の記事を書く。