C# алгоритм генерации иерархии

Question

У меня есть текстовый файл, который выглядит следующим образом:

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

Я ищу родовой C# алгоритма, который будет создавать иерархию объектов из этого. Функция «Иерархия», если хотите, превращает эти данные в иерархию объектов.

Любые идеи?

редактировать Я уже разобран файл в объекты .NET:

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

Теперь мне нужно на самом деле расположить объекты в графе объектов.

Answer 1

Большое спасибо Jon и mquander - вы, ребята, дали мне достаточно информации, чтобы помочь мне решить это правильным, общим образом.Вот мое решение, один общий метод расширения, который преобразует объекты в виде иерархии:

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

использует этот небольшой класс узла:

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

Это достаточно универсальное для работы по целому ряду проблем, в том числе моего текста файл. Острота!

**** **** UPDATE: Вот как вы бы использовать:

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

Вы уверены, что ParentID последней строки - 1? Название гласит внук, но это будет ребенок «root», если я правильно прочитаю.

Answer 3

Хм ... Я не совсем понимаю, как это работает. Как 2 и 5 имеют родительский = 1, положение = 0? Должен ли 5 ​​иметь родительский 2, 3 или 4?

Хорошо, эта новая версия проходит через все узлы три раза:

• нагрузки все узлы и поместить их в карту
• Associate каждый узел с его родителем
• Сортировать ребенок каждого узла по положению

Неплохо инкапсулированный, хорошо проверяющий ошибки и т. д. - но он работает.

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

текстовый файл Пример:

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

Выход:

root 
    child 1 
    child 2 
    child 3 
    grandchild 1 

Answer 4

После того как вы файл разобрана вы можете следовать этому blog о том, как собрать объекты в иерархии с помощью 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])); 
    } 
} 

результат:

root 
    child 1 
    child 2 
    grandchild 1 
    child 3 

Answer 6

Я предполагаю, что ваш пример неправильно дает неправильный родительский идентификатор на объект # 5. Это должно покрыть его. Предостережения: Предполагается, что «самый верхний» узел всегда имеет родительский идентификатор нуля. Игнорирует любые узлы, которые в конечном счете не спускаются с самого верхнего узла. Поведение будет нечетным, если оно будет представлено с повторяющимися идентификаторами.

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

Вот пример, который @baran попросил:

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