C#-Algorithmus zur Erzeugung einer Hierarchie

Question

Ich habe eine Textdatei, die wie folgt aussieht:

{ Id = 1, ParentId = 0, Position = 0, Title = "root" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }

Ich bin auf der Suche nach einem generischen C#-Algorithmus, der daraus eine Objekthierarchie erstellt. Eine "Hierarchize"-Funktion, wenn Sie so wollen, die diese Daten in eine Objekthierarchie verwandelt.

Irgendwelche Ideen?

editar Ich habe die Datei bereits in .NET-Objekte geparst:

class Node
{
    public int Id { get; }
    public int ParentId { get; }
    public int Position { get; }
    public string Title { get; }
}

Jetzt muss ich die Objekte tatsächlich in einem Objektdiagramm anordnen.

Answer 1

Vielen Dank an Jon und mquander - ihr habt mir genug Informationen gegeben, um das Problem auf eine angemessene, allgemeine Weise zu lösen. Hier ist meine Lösung, eine einzige generische Erweiterungsmethode, die Objekte in eine Hierarchieform umwandelt:

public static IEnumerable<Node<T>> Hierarchize<T, TKey, TOrderKey>(
    this IEnumerable<T> elements, 
    TKey topMostKey, 
    Func<T, TKey> keySelector, 
    Func<T, TKey> parentKeySelector, 
    Func<T, TOrderKey> orderingKeySelector)
{
    var families = elements.ToLookup(parentKeySelector);
    var childrenFetcher = default(Func<TKey, IEnumerable<Node<T>>>);
    childrenFetcher = parentId => families[parentId]
        .OrderBy(orderingKeySelector)
        .Select(x => new Node<T>(x, childrenFetcher(keySelector(x))));

    return childrenFetcher(topMostKey);
}

Verwendet diese kleine Knotenklasse:

public class Node<T>
{
    public T Value { get; private set; }
    public IList<Node<T>> Children { get; private set; }

    public Node(T value, IEnumerable<Node<T>> children)
    {
        this.Value = value;
        this.Children = new List<Node<T>>(children);
    }
}

Es ist allgemein genug, um bei einer Vielzahl von Problemen zu funktionieren, auch bei meinem Textdateiproblem. Raffiniert!

****UPDATE****: So verwenden Sie es:

// Given some example data:
var items = new[] 
{
   new Foo() 
   {
      Id = 1,
      ParentId = -1, // Indicates no parent
      Position = 0
   },
   new Foo() 
   {
      Id = 2,
      ParentId = 1,
      Position = 0
   },
   new Foo() 
   {
      Id = 3,
      ParentId = 1,
      Position = 1
   }
};

// Turn it into a hierarchy! 
// We'll get back a list of Node<T> containing the root nodes.
// Each node will have a list of child nodes.
var hierarchy = items.Hierarchize(
    -1, // The "root level" key. We're using -1 to indicate root level.
    f => f.Id, // The ID property on your object
    f => f.ParentId, // The property on your object that points to its parent
    f => f.Position, // The property on your object that specifies the order within its parent
    );

Answer 2

Hmm ... Ich verstehe nicht ganz, wie das funktioniert. Wie können 2 und 5 beide parent=1, position=0 haben? Sollte 5 ein Elternteil 2, 3 oder 4 haben?

Okay, diese neue Version geht dreimal durch alle Knotenpunkte:

• Laden Sie alle Knoten und legen Sie sie in die Karte ein
• Verbinden Sie jeden Knoten mit seinem Elternteil
• Sortierung der untergeordneten Knoten nach Position

Es ist nicht gut gekapselt, hat eine schöne Fehlerprüfung usw. - aber es funktioniert.

using System;
using System.Collections.Generic;
using System.IO;

public class Node
{
    private static readonly char[] Braces = "{}".ToCharArray();
    private static readonly char[] StringTrim = "\" ".ToCharArray();

    public Node Parent { get; set; }
    public int ParentId { get; private set; }
    public int Id { get; private set; }
    public string Title { get; private set; }
    public int Position { get; private set; }
    private readonly List<Node> children = new List<Node>();
    public List<Node> Children { get { return children; } }

    public static Node FromLine(string line)
    {
        Node node = new Node();
        line = line.Trim(Braces);
        string[] bits = line.Split(',');
        foreach (string bit in bits)
        {
            string[] keyValue = bit.Split('=');
            string key = keyValue[0].Trim();
            string value = keyValue[1].Trim();
            switch (key)
            {
                case "Id":
                    node.Id = int.Parse(value);
                    break;
                case "ParentId":
                    node.ParentId = int.Parse(value);
                    break;
                case "Position":
                    node.Position = int.Parse(value);
                    break;
                case "Title":
                    node.Title = value.Trim(StringTrim);
                    break;
                default:
                    throw new ArgumentException("Bad line: " + line);
            }
        }
        return node;
    }

    public void Dump()
    {
        int depth = 0;
        Node node = this;
        while (node.Parent != null)
        {
            depth++;
            node = node.Parent;
        }
        Console.WriteLine(new string(' ', depth * 2) + Title);
        foreach (Node child in Children)
        {
            child.Dump();
        }
    }
}

class Test
{       
    static void Main(string[] args)
    {
        var dictionary = new Dictionary<int, Node>();

        using (TextReader reader = File.OpenText("test.txt"))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
            {
                Node node = Node.FromLine(line);
                dictionary[node.Id] = node;
            }
        }
        foreach (Node node in dictionary.Values)
        {
            if (node.ParentId != 0)
            {
                node.Parent = dictionary[node.ParentId];
                node.Parent.Children.Add(node);
            }
        }

        foreach (Node node in dictionary.Values)
        {
            node.Children.Sort((n1, n2) =>
                               n1.Position.CompareTo(n2.Position));
        }

        Node root = dictionary[1];
        root.Dump();
    }
}

Beispiel-Textdatei:

{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 1, ParentId = 0, Position = 0, Title = "root" }

Ausgabe:

root
  child 1
  child 2
  child 3
    grandchild 1

Answer 3

Sobald Sie die Datei geparst haben, können Sie wie folgt vorgehen Blog wie die Objekte mit Hilfe von LINQ zu einer Hierarchie zusammengesetzt werden können.

Answer 4

class Node {
    public int Id { get;set;  }
    public int ParentId { get;set;  }
    public int Position { get;set;  }
    public string Title { get;set;  }
    public IEnumerable<Node> Children { get; set; }

    public override string ToString() { return ToString(0); }
    public string ToString(int depth) {
        return "\n" + new string(' ', depth * 2) + Title + (
            Children.Count() == 0 ? "" :
            string.Join("", Children
                .Select(node => node.ToString(depth + 1))
                .ToArray()
            );
    }
}
class Program {
    static void Main(string[] args) {
        var data = new[] {
            new Node{ Id = 1, ParentId = 0, Position = 0, Title = "root" },
            new Node{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
            new Node{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
            new Node{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
            new Node{ Id = 5, ParentId = 3, Position = 0, Title = "grandchild 1" }
        };
        Func<Node, Node> transform = null;
        transform = node => new Node {
            Title = node.Title,
            Id = node.Id,
            ParentId = node.ParentId,
            Position = node.Position,
            Children = (
                from child in data
                where child.ParentId == node.Id
                orderby child.Position
                select transform(child))
        };
        Console.WriteLine(transform(data[0]));
    }
}

Ergebnis:

root
  child 1
  child 2
    grandchild 1
  child 3

Answer 5

Ich nehme an, dass Ihr Beispiel fälschlicherweise die falsche übergeordnete ID für Objekt Nr. 5 angibt. Das sollte das Problem lösen. Vorbehalte: Es wird davon ausgegangen, dass der "oberste" Knoten immer eine übergeordnete ID von Null hat. Ignoriert alle Knoten, die nicht von dem obersten Knoten abstammen. Das Verhalten ist merkwürdig, wenn doppelte IDs vorhanden sind.

public class FlatObj
{
    public int Id;
    public int ParentId;
    public int Position;
    public string Title;
}

public class Node
{
    public int ID;
    public string Title;
    public IList<Node> Children;

    public Node(FlatObject baseObject, IList<Node> children)
    {
        this.ID = baseObject.Id;
        this.Title = baseObject.Title;
        this.Children = children;
    }
}

public static Node CreateHierarchy(IEnumerable<FlatObject> objects)
{
    var families = objects.ToLookup(x => x.ParentId);
    var topmost = families[0].Single();

    Func<int, IList<Node>> Children = null;

    Children = (parentID) => families[parentID]
        .OrderBy(x => x.Position)
        .Select(x => new Node(x, Children(x.Id))).ToList();

    return new Node(topmost, Children(topmost.Id));
}

public static void Test()
{
    List<FlatObj> objects = new List<FlatObj> {
    new FlatObj { Id = 1, ParentId = 0, Position = 0, Title = "root" },
    new FlatObj { Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
    new FlatObj { Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
    new FlatObj { Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
    new FlatObj { Id = 5, ParentId = 2, Position = 0, Title = "grandchild" }};

    var nodes = CreateHierarchy(objects);
}