C# algoritmo para generar jerarquía

Question

Tengo un archivo de texto que se parece a esto:

{ 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" } 

Estoy buscando un algoritmo genérico C# que va a crear una jerarquía de objetos de esta. Una función "jerarquizar", si lo desea, convierte estos datos en una jerarquía de objetos.

¿Alguna idea?

edición ya he analizado el archivo en objetos .NET:

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

Ahora necesito para organizar los objetos en realidad en un gráfico de objetos.

Answer 1

Muchas gracias a Jon y al mquander - ustedes me dio suficiente información para ayudar a solucionar esto de una manera adecuada, genérico.Aquí está mi solución, un solo método de extensión genérica que convierte los objetos en forma de jerarquía:

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

utiliza esta pequeña clase de nodo:

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 lo suficientemente genérico para trabajar para una variedad de problemas, incluyendo mi texto problema con el archivo ¡Hábil!

**** **** ACTUALIZACIÓN: Aquí se explica cómo lo utilizaría:

// 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

¿Está seguro de que ParentID de la última línea es 1? El título dice nieto, pero sería un hijo de "raíz" si estoy leyendo las cosas correctamente.

Answer 3

Hmm ... No entiendo muy bien cómo funciona eso. ¿Cómo pueden 2 y 5 tener padre = 1, posición = 0? ¿Deberían 5 tener el padre 2, 3 o 4?

bien, esta nueva versión pasa a través de los todos los nodos en tres ocasiones:

• carga todos los nodos y las puso en el mapa
• asociar cada nodo con su matriz
• Ordenar hijo de cada nodo por posición

No está bien encapsulado, muy bien la comprobación de errores, etc., pero funciona.

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

archivo de texto de la muestra:

{ 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" } 

Salida:

root 
    child 1 
    child 2 
    child 3 
    grandchild 1 

Answer 4

Una vez que tenga el archivo analizado en ti puede seguir esta blog sobre cómo montar los objetos en una jerarquía utilizando LINQ .

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

resultado:

root 
    child 1 
    child 2 
    grandchild 1 
    child 3 

Answer 6

que asuma que su ejemplo da incorrectamente el ID padre erróneo objeto # 5. Esto debería cubrirlo. Advertencias: se supone que el nodo "más alto" siempre tiene una ID principal de cero. Ignora los nodos que no descienden finalmente del nodo superior. El comportamiento será extraño si se presentan con ID duplicados.

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 7

Aquí es el ejemplo que @baran pedido:

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