C# algoritmo per la generazione gerarchia

Question

Ho un file di testo che assomiglia a questo:

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

Sto cercando un algoritmo generico C# che creerà una gerarchia di oggetti da questo. Una funzione "Gerarchizza", se lo desideri, trasforma questi dati in una gerarchia di oggetti.

Qualche idea?

modificare Ho già analizzato il file in oggetti .NET:

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

Ora ho bisogno di organizzare in realtà gli oggetti in un oggetto grafico.

Answer 1

Molte grazie a Jon e per mquander - voi ragazzi mi ha dato abbastanza informazioni per aiutarmi a risolvere questo in un corretto modo generico.Ecco la mia soluzione, un unico metodo di estensione generico che converte gli oggetti in forma gerarchia:

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

utilizza questa piccola classe 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); 
    } 
} 

E 'sufficientemente generico per lavorare per una serie di problemi, tra cui il mio testo problema di file. Nifty!

**** **** UPDATE: Ecco come ci si utilizza:

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

Sei sicuro che il ParentID dell'ultima riga è 1? Il titolo dice nipote, ma sarebbe un figlio di "root" se sto leggendo le cose correttamente.

Answer 3

Hmm ... Non vedo come funziona. In che modo 2 e 5 hanno entrambi parent = 1, position = 0? Dovrebbero avere 5 genitori 2, 3 o 4?

Va bene, questa nuova versione passa attraverso i tutti i nodi per tre volte:

• carico tutti i nodi e li mise in una mappa
• Associate ogni nodo con il suo genitore
• Ordina bambino di ogni nodo per posizione

Non è ben incapsulato, controlla bene gli errori, ecc., ma funziona.

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

Esempio file di testo:

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

uscita:

root 
    child 1 
    child 2 
    child 3 
    grandchild 1 

Answer 4

Una volta ottenuto il file analizzato nel Puoi seguire questa blog su come assemblare gli oggetti in una gerarchia utilizzando 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])); 
    } 
} 

risultato:

root 
    child 1 
    child 2 
    grandchild 1 
    child 3 

Answer 6

Suppongo che il vostro esempio dà erroneamente l'ID genitore sbagliato di opporsi 5 #. Questo dovrebbe coprirlo. Avvertenze: presuppone che il nodo "più in alto" abbia sempre un ID padre pari a zero. Ignora tutti i nodi che alla fine non discendono dal nodo più in alto. Il comportamento sarà dispari se presentato con ID duplicati.

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

Ecco l'esempio che @baran chiesto:

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