1

次の特性を持つツリー グラフ内のアイテムを効率的にグループ化する方法を見つけたいと考えています。

ツリー グラフについては、横方向に描画すると、次のように複数のレイヤーがあります。

(0,0)--(1,0)--(2,0)
   \ \-(1,1)--(2,1)
    \--(1,2)--/
  1. クラス Node によってモデル化されたノード (x,y) の場合、x はその「レベル」であり、y はその「インデックス」です。任意のエッジでは、このエッジの 2 つのノードに対して順次インデックスのみが許可されるため、(1,2)-(3,2) は禁止されます。
  2. 複数のルートを許可: (0,0) (0,1) ...など。

「項目のグループ化」について: ツリーのデータ ソースには次のようなノードがあるためです。

(3,5)--(4,10)--(5,5)
  \  \-(4,11)-/  /
   \    ....    /
    \--(4,80)--/

上記のようなノード (4,10~80) を 1 つのノードにグループ化したいのですが、これらのノードは同じ特性を共有しています

  1. 共有する親ノードは 1 つだけです
  2. 共有する子ノードは 1 つだけです
  3. また、共通の親 (または共通の子) しかなく、子 (または親) がまったくいない場合にも取り組む必要があります。

Node のサブクラスである特別なクラス CompoundNode を使用します。

Node のスケルトン クラスは次のとおりです。

public class Node
{
    public Node(string id)
    {
        Id = id;
    }

    public string Id { get; set; }

    private readonly List<Node> children = new List<Node>();
    public List<Node> Children { get { return children; } }
    private readonly List<Node> parents = new List<Node>();
    public List<Node> Parents { get { return parents; } }

    protected bool Equals(Node other)
    {
        ....
    }

    public override bool Equals(object obj)
    {
        ....
    }

    public override int GetHashCode()
    {
        return (Id != null ? Id.GetHashCode() : 0);
    }

    public override string ToString()
    {
        ....
    }
}

ありがとう！

編集：

これが私が行った解決策です（ツリーを変更せずに関係を抽出します）、親がゼロまたは子がゼロの状況に取り組みません：

        var relationships = new List<Tuple<string, string, string>>();

        foreach (var middle in nodes)
        {
            if (middle.Children.Count == 1 && middle.Parents.Count == 1)
            {
                var child = middle.Children[0];
                var parent = middle.Parents[0];
                relationships.Add(new Tuple<string, string, string>(parent.Id, middle.Id, child.Id));
            }
        }
        var groups = relationships.GroupBy(t => new { t.Item1, t.Item3 }).Where(a => a.Count() > 1);

        var toGroupedRelations = groups.Cast<IEnumerable<Tuple<string, string, string>>>().ToList();
4

1 に答える 1

0

わかりました - これが最初の試みです。とにかくあなたにいくつかの良い指針を与えるべきです：

var nodes = new List<Node>();

// !! populate your nodes list with all your real nodes first!

// filter to nodes with at most 1 parent and 1 child
// group by a tuple containing the parent (if it exists) and the child (if it exists)
var grouped = nodes.Where(i => i.Children.Count <= 1 && i.Parents.Count <= 1)
    .GroupBy(i => 
        new Tuple<Node, Node>(i.Parents.Count == 0 ? null : i.Parents[0], 
                                i.Children.Count == 0 ? null : i.Children[0]));

// go through your groups - each one should be a cluster of nodes to be merged
foreach (var group in grouped)
{
    // get the first node in the group (which one is arbitrary if we're merging anyway)
    var node = group.First();

    // if this group has a parent
    if (node.Parents.Count == 1)
    {
        // change the parent to only have one child - this one!
        node.Parents[0].Children.Clear();
        node.Parents[0].Children.Add(node);
    }

    // if this group has a child
    if (node.Children.Count == 1)
    {
        // change the child to only have one parent - this one!
        node.Children[0].Parents.Clear();
        node.Children[0].Parents.Add(node);
    }
}
于 2013-11-15T04:59:13.113 に答える