c# - 避免子节点出现在父级的同一级或上级

Question

我正在构建 map 。为此，我需要为 map 的每个节点分配一个级别，并且我需要自动生成这些级别。

目前我有节点之间的关系。 (亲子关系)在给定的示例中，共有 23 个节点。

我不希望任何子级与父级处于同一级别或高于父级。

我目前有两个数据表。第一个包含节点 ID，第二个包含与节点 ID 对应的级别。

我如何在下面的代码中进行任何调整，以使任何子级都不会达到或超过其父级的级别？

以下代码的输出是节点的 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，因为你不需要。您可以在设置 child 时添加属性 level 来计算级别。以下是我的主要修改:

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

      }
    }
  }
}

以上代码将产生以下输出。

这就是我计算级别的方式。如果您还需要什么，请告诉我!

NOTE: I have not handled every case. So it would break if you try to set null as child.

您也可以只循环每个节点并调用它的 CalculateLevel 方法，就像在初始化之后一样，不要在设置 Child 时调用。

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

希望这对您有所帮助!