Избегайте появления дочерних узлов на том же или верхнем уровне родительского уровня

Question

Я создаю карту. для этого мне нужно присвоить уровень каждому узлу карты, и мне нужно, чтобы эти уровни были автоматически сгенерированы.

В настоящее время у меня есть связь между узлами. (отношение как у родительских детей) В данном примере всего 23 узла.

Я не хочу, чтобы дети были на том же уровне, что и родительский или выше родительского уровня.

В настоящее время у меня есть две таблицы данных. Сначала содержит идентификаторы узлов, а второй содержит уровни, соответствующие идентификаторам узлов.

Как я могу внести корректировку в код ниже, чтобы любой ребенок не попал на тот же уровень или выше уровня его родителя?

Вывод нижеследующего кода - это координаты x и y узлов.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace coordinatesGeneration 
{ 
    class Program 
    { 
     internal class Node 
     { 
      public Node Parent { get; set; } 
      private Node m_child; 
      public Node Child 
      { 
       get { return m_child; } 
       set 
       { 
        m_child = value; 
        value.Parent = this; 
       } 
      } 
      public int Id { get; set; } 
      public string Title { get; set; } 
     } 


     internal class Program1 
     { 
      static void Main(string[] args) 
      { 
       Dictionary<int, Node> nodes = new Dictionary<int, Node>() 
     { 
     {0, new Node() {Id = 0, Title = "Node1"}}, 
     {1, new Node() {Id = 1, Title = "Node2"}}, 
     {2, new Node() {Id = 2, Title = "Node7"}}, 
     {3, new Node() {Id = 3, Title = "Node3"}}, 
     {4, new Node() {Id = 4, Title = "Node4"}}, 
     {5, new Node() {Id = 5, Title = "Node5"}}, 
     {6, new Node() {Id = 6, Title = "Node6"}}, 
     {7, new Node() {Id = 7, Title = "Node8"}}, 
     {8, new Node() {Id = 8, Title = "Node9"}}, 
     {9, new Node() {Id = 9, Title = "Node10"}}, 
     {10, new Node() {Id = 10, Title = "Node11"}}, 
     {11, new Node() {Id = 11, Title = "Node12"}}, 
     {12, new Node() {Id = 12, Title = "Node13"}}, 
     {13, new Node() {Id = 13, Title = "Node14"}}, 
     {14, new Node() {Id = 14, Title = "Node15"}}, 
     {15, new Node() {Id = 15, Title = "Node16"}}, 
     {16, new Node() {Id = 16, Title = "Node17"}}, 
     {17, new Node() {Id = 17, Title = "Node18"}}, 
     {18, new Node() {Id = 18, Title = "Node19"}}, 
     {19, new Node() {Id = 19, Title = "Node20"}}, 
     {20, new Node() {Id = 20, Title = "Node21"}}, 
     {21, new Node() {Id = 21, Title = "Node22"}}, 
     {22, new Node() {Id = 22, Title = "Node23"}} 


    }; 
      nodes[0].Child = nodes[3]; 
      nodes[1].Child = nodes[3]; 
      nodes[2].Child = nodes[4]; 
      nodes[2].Child = nodes[5]; 
      nodes[3].Child = nodes[6]; 
      nodes[3].Child = nodes[7]; 
      nodes[3].Child = nodes[8]; 
      nodes[3].Child = nodes[9]; 
      nodes[6].Child = nodes[10]; 
      nodes[2].Child = nodes[11]; 
      nodes[2].Child = nodes[12]; 
      nodes[7].Child = nodes[13]; 
      nodes[8].Child = nodes[14]; 
      nodes[4].Child = nodes[15]; 
      nodes[5].Child = nodes[15]; 
      nodes[7].Child = nodes[15]; 
      nodes[12].Child = nodes[16]; 
      nodes[13].Child = nodes[16]; 
      nodes[13].Child = nodes[17]; 
      nodes[14].Child = nodes[18]; 
      nodes[8].Child = nodes[19]; 
      nodes[13].Child = nodes[20]; 
      nodes[14].Child = nodes[20]; 
      nodes[8].Child = nodes[21]; 
      nodes[15].Child = nodes[21]; 
      nodes[18].Child = nodes[22]; 
      nodes[19].Child = nodes[22]; 

      int parentlessNodeCounter = 0; 
      Dictionary<int, List<Node>> nbParentNodesDictionary = new Dictionary<int, List<Node>>(); 
      foreach (KeyValuePair<int, Node> valuePair in nodes) 
      { 
       Node parent = valuePair.Value.Parent; 
       int nbOfParent = 0; 

       if (valuePair.Value.Parent == null) 
        parentlessNodeCounter++; 
       while (parent != null) 
       { 
        nbOfParent++; 
        parent = parent.Parent; 
       } 
       if (valuePair.Value.Parent == null && parentlessNodeCounter > 1) 
        nbOfParent ++; 
       if (!nbParentNodesDictionary.ContainsKey(nbOfParent)) 
       { 
        nbParentNodesDictionary[nbOfParent] = new List<Node>(); 
       } 
       nbParentNodesDictionary[nbOfParent].Add(valuePair.Value); 
      } 

      const int yOffSet = 150;// initial value used for yOffset = 100; 

      foreach (KeyValuePair<int, List<Node>> keyValuePair in nbParentNodesDictionary) 
      { 
       const int xMax = 1000;// initial value used for xMax = 500; 
       int xOffset = xMax/(keyValuePair.Value.Count + 1); 
       int x = 0; 
       foreach (Node node in keyValuePair.Value) 
       { 
        x += xOffset; 
        Console.Write("id:" + node.Id + " title:" + node.Title + " x:" + x + " y:" + yOffSet * keyValuePair.Key); 
       } 
      } 

     } 
    } 
    } 
} 

Answer 1

Как я понимаю, что вы хотите, чтобы вычислить level для данного узла. Я бы предложил не использовать dict, потому что вам это не нужно. Вы можете просто добавить свойство level рассчитать уровень при настройке child. Вот мои основные модификации:

internal class Node 
    { 
     public Node(){ 
     Level = -1; 
     Parents = new List<Node>(); 
     } 
     public List<Node> Parents { get; set; } 
     private Node m_child; 
     public Node Child 
     { 
     get { return m_child; } 
     set 
     { 
      m_child = value; 
      value.Parents.Add(this); 
      m_child.CalculateLevel(); 
     } 
     } 
     public int Id { get; set; } 
     public string Title { get; set; } 
     public int Level {get; private set;} 
     public void CalculateLevel(){ 
     if(Parents.Count() == 0){ 
      this.Level = 0; 
      return; 
     } 
     foreach (var parent in this.Parents) 
     { 
      parent.CalculateLevel(); 
     } 

     this.Level = Parents.Select(p => p.Level).Max() + 1; 
     } 
    } 

Ниже полный код:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace coordinatesGeneration 
{ 
    class Program 
    { 
    internal class Node 
    { 
     public Node(){ 
     Level = -1; 
     Parents = new List<Node>(); 
     } 
     public List<Node> Parents { get; set; } 
     private Node m_child; 
     public Node Child 
     { 
     get { return m_child; } 
     set 
     { 
      m_child = value; 
      value.Parents.Add(this); 
      m_child.CalculateLevel(); 
     } 
     } 
     public int Id { get; set; } 
     public string Title { get; set; } 
     public int Level {get; private set;} 
     public void CalculateLevel(){ 
     if(Parents.Count() == 0){ 
      this.Level = 0; 
      return; 
     } 
     foreach (var parent in this.Parents) 
     { 
      parent.CalculateLevel(); 
     } 

     this.Level = Parents.Select(p => p.Level).Max() + 1; 
     } 
    } 


    internal class Program1 
    { 
     static void Main(string[] args) 
     { 
     Node[] nodes = new Node[] 
     { 
      new Node() {Id = 0, Title = "Node1"}, 
      new Node() {Id = 1, Title = "Node2"}, 
      new Node() {Id = 2, Title = "Node7"}, 
      new Node() {Id = 3, Title = "Node3"}, 
      new Node() {Id = 4, Title = "Node4"}, 
      new Node() {Id = 5, Title = "Node5"}, 
      new Node() {Id = 6, Title = "Node6"}, 
      new Node() {Id = 7, Title = "Node8"}, 
      new Node() {Id = 8, Title = "Node9"}, 
      new Node() {Id = 9, Title = "Node10"}, 
      new Node() {Id = 10, Title = "Node11"}, 
      new Node() {Id = 11, Title = "Node12"}, 
      new Node() {Id = 12, Title = "Node13"}, 
      new Node() {Id = 13, Title = "Node14"}, 
      new Node() {Id = 14, Title = "Node15"}, 
      new Node() {Id = 15, Title = "Node16"}, 
      new Node() {Id = 16, Title = "Node17"}, 
      new Node() {Id = 17, Title = "Node18"}, 
      new Node() {Id = 18, Title = "Node19"}, 
      new Node() {Id = 19, Title = "Node20"}, 
      new Node() {Id = 20, Title = "Node21"}, 
      new Node() {Id = 21, Title = "Node22"}, 
      new Node() {Id = 22, Title = "Node23"} 


     }; 
     nodes[0].Child = nodes[3]; 
     nodes[1].Child = nodes[3]; 
     nodes[2].Child = nodes[4]; 
     nodes[2].Child = nodes[5]; 
     nodes[3].Child = nodes[6]; 
     nodes[3].Child = nodes[7]; 
     nodes[3].Child = nodes[8]; 
     nodes[3].Child = nodes[9]; 
     nodes[6].Child = nodes[10]; 
     nodes[2].Child = nodes[11]; 
     nodes[2].Child = nodes[12]; 
     nodes[7].Child = nodes[13]; 
     nodes[8].Child = nodes[14]; 
     nodes[4].Child = nodes[15]; 
     nodes[5].Child = nodes[15]; 
     nodes[7].Child = nodes[15]; 
     nodes[12].Child = nodes[16]; 
     nodes[13].Child = nodes[16]; 
     nodes[13].Child = nodes[17]; 
     nodes[14].Child = nodes[18]; 
     nodes[8].Child = nodes[19]; 
     nodes[13].Child = nodes[20]; 
     nodes[14].Child = nodes[20]; 
     nodes[8].Child = nodes[21]; 
     nodes[15].Child = nodes[21]; 
     nodes[18].Child = nodes[22]; 
     nodes[19].Child = nodes[22]; 

     foreach(var n in nodes){ 
      Console.WriteLine(n.Title + " (Level: " + n.Level + ") > PARENTS: " + (n.Parents.Count() != 0 ? n.Parents.Count() + " (" + (n.Parents.Count() == 1 ? (n.Parents[0].Title + " @ " + n.Parents[0].Level) : n.Parents.Select(p => p.Title + " @ " + p.Level).Aggregate((c,next) => c + ", " + next)) + ")" : "Root")); 
     } 

     } 
    } 
    } 
} 

Приведенный выше код будет производить следующий вывод.

Так вот как я бы вычислить level. Пожалуйста, дайте мне знать, если вам нужно что-нибудь еще!

ПРИМЕЧАНИЕ: Я не обрабатывал каждый случай. Так что это сломается, если вы попытаетесь установить null в качестве дочернего.

Вы также можете просто петлю вокруг каждого узла и вызвать его метод CalculateLevel как после инициализации и не требуют при установке Child.

foreach(var n in nodes){ 
    n.CalculateLevel(); 
} 

Надеюсь, это поможет!

Answer 2

Это делается ваш подход .. так что вы не должны изменить существующий код ..

public class Example 
{ 
    public static void Main() 
    { 
     List<Node> nodes = new List<Node> 
     { 
      new Node {Id = 0, Title = "Node1"}, 
      new Node {Id = 1, Title = "Node2"}, 
      new Node {Id = 2, Title = "Node7"}, 
      new Node {Id = 3, Title = "Node3"}, 
      new Node {Id = 4, Title = "Node4"}, 
      new Node {Id = 5, Title = "Node5"}, 
      new Node {Id = 6, Title = "Node6"}, 
      new Node {Id = 7, Title = "Node8"}, 
      new Node {Id = 8, Title = "Node9"}, 
      new Node {Id = 9, Title = "Node10"}, 
      new Node {Id = 10, Title = "Node11"}, 
      new Node {Id = 11, Title = "Node12"}, 
      new Node {Id = 12, Title = "Node13"}, 
      new Node {Id = 13, Title = "Node14"}, 
      new Node {Id = 14, Title = "Node15"}, 
      new Node {Id = 15, Title = "Node16"}, 
      new Node {Id = 16, Title = "Node17"}, 
      new Node {Id = 17, Title = "Node18"}, 
      new Node {Id = 18, Title = "Node19"}, 
      new Node {Id = 19, Title = "Node20"}, 
      new Node {Id = 20, Title = "Node21"}, 
      new Node {Id = 21, Title = "Node22"}, 
      new Node {Id = 22, Title = "Node23"} 
     }; 
     nodes[0].AddChild(nodes[3]); 
     nodes[1].AddChild(nodes[3]); 
     nodes[2].AddChild(nodes[4]); 
     nodes[2].AddChild(nodes[5]); 
     nodes[3].AddChild(nodes[6]); 
     nodes[3].AddChild(nodes[7]); 
     nodes[3].AddChild(nodes[8]); 
     nodes[3].AddChild(nodes[9]); 
     nodes[6].AddChild(nodes[10]); 
     nodes[2].AddChild(nodes[11]); 
     nodes[2].AddChild(nodes[12]); 
     nodes[7].AddChild(nodes[13]); 
     nodes[8].AddChild(nodes[14]); 
     nodes[4].AddChild(nodes[15]); 
     nodes[5].AddChild(nodes[15]); 
     nodes[7].AddChild(nodes[15]); 
     nodes[12].AddChild(nodes[16]); 
     nodes[13].AddChild(nodes[16]); 
     nodes[13].AddChild(nodes[17]); 
     nodes[14].AddChild(nodes[18]); 
     nodes[8].AddChild(nodes[19]); 
     nodes[13].AddChild(nodes[20]); 
     nodes[14].AddChild(nodes[20]); 
     nodes[8].AddChild(nodes[21]); 
     nodes[15].AddChild(nodes[21]); 
     nodes[18].AddChild(nodes[22]); 
     nodes[19].AddChild(nodes[22]); 

     //Get all nodes by level 
     //if any node does not have a parent it is by default in level 0 

     var rootNodes = nodes.Where(i => i.IsRootElement); 

     foreach (var rootNode in rootNodes) 
     { 
      PrintElementRecurcively(rootNode, null,0); 
     } 


     Console.ReadKey(); 
    } 

    static void PrintElementRecurcively(Node nodeToPrint,Node parentNode,int depth) 
    {     
      System.Console.Write(string.Join("", Enumerable.Repeat("-", (depth*2)))); 
      System.Console.WriteLine("Node Id:{0} Level:{1}  ParentId:{2}", nodeToPrint.Id, depth, 
       nodeToPrint.Parents == null ? "Unknown" : parentNode.Id.ToString()); 

      if (nodeToPrint.Childs==null) 
      { 
       return; 
      } 

      foreach (var rootNode in nodeToPrint.Childs) 
      { 
       PrintElementRecurcively(rootNode, nodeToPrint, depth+1); 
      } 
    } 
} 

internal class Node 
{ 
    public List<Node> Parents { get;private set; }   
    public List<Node> Childs{get;private set;}   

    public int Id { get; set; } 
    public string Title { get; set; } 

    public void AddChild(Node newChild) 
    { 
     if (Childs == null) 
     { 
      Childs = new List<Node>(); 
     } 
     Childs.Add(newChild); 

     if (newChild.Parents==null) 
     { 
      newChild.Parents = new List<Node>(); 
     } 
     newChild.Parents.Add(this);    
    } 

    public Boolean IsRootElement 
    { 
     get 
     { 
      return Parents == null;    
     } 
    } 

    //public int Level 
    //{ 
    // get 
    // { 
    //  if(Parents==null) 
    //  { 
    //   return 0; 
    //  } 

    //  //If you have multiple parents with different level 
    //  //then it's impossible to assign that node a fixed level 
    //  //you need to took one stategy 
    //  // return Parents.Min(i => i.Level)+1; 
    //  //return Convert.ToInt32(Math.Floor(Parents.Average(i => i.Level)))+1; 
    //  return Parents.Max(i => i.Level)+1; 
    // } 
    //} 



}