C # Algorithmus zum Erzeugen von Hierarchie

Question

Ich habe eine Textdatei bekam 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 suche nach einem generischen C # Algorithmus, der eine Objekthierarchie daraus schaffen. A „Hierarchize“ -Funktion, wenn man will, dass verwandelt diese Daten in eine Objekthierarchie.

Irgendwelche Ideen?

Bearbeiten Ich habe bereits die Datei in .NET-Objekte analysiert:

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

Jetzt muss ich eigentlich die Objekte in einem Objektdiagramm anordnen.

Answer 1

Vielen Dank an Jon und mquander - ihr seid gab mir genügend Informationen, um mir zu helfen dieses Problem lösen in einem richtigen, generische Art und Weise. Hier ist meine Lösung, eine einzige generische Erweiterungsmethode, die Objekte in Hierarchie Form 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);
}

Nutzt 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 genug generisches für eine Vielzahl von Problemen zu arbeiten, einschließlich meiner Textdatei Problem. Nifty!

**** UPDATE ****: Hier ist, wie Sie es verwenden würde:

// 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 sehe nicht, wie das funktioniert. Wie kann 2 und 5 haben beide Eltern = 1, Position = 0? Sollte 5 haben Elternteil 2, 3 oder 4?

Okay, diese neue Version geht durch die alle Knoten dreimal:

• Laden alle Knoten und legte sie in die eine Karte
• Verknüpfen Sie jeden Knoten mit dem übergeordneten
• Sortieren jedes Kind-Knoten von Position

Es ist nicht gut gekapselt, schön Fehler usw. überprüft - 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();
    }
}

Beispieltextdatei:

{ 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 in Ihnen analysiert kann diese folgen Blog , wie die Objekte in eine Hierarchie montieren mit LINQ.

Answer 4

Ich gehe davon aus, dass Ihr Beispiel falsch die falschen Eltern ID gibt 5 # zu widersprechen. Dies sollte es abdecken. Caveats: Setzt die „oberste“ Knoten immer eine übergeordnete ID von Null hat. Ignoriert alle Knoten, die nicht letztendlich von dem obersten Knoten abstammen. Verhalten wird seltsam sein, wenn mit doppelter IDs dargestellt.

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);
}

Answer 5

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 6

Sind Sie sicher, die letzte Zeile des ParentID ist 1? Der Titel sagt Enkelkind, aber es wäre ein Kind von „root“ sein, wenn ich die Dinge richtig zu lesen bin.

Answer 7

Hier ist das Beispiel, das für @baran gefragt:

var lHierarchicalMenuItems = lMenuItemsFromDB.Hierarchize(0, aItem => aItem.Id, aItem => aItem.ParentId, aItem => aItem.Position);