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

Question

Данный тип:

class Field{ 
    public string Name{get;set;} 
    public string[] DependsOn{get;set;} 
} 

Скажем, у меня есть массив Field пунктов:

List<Field> fields = new List<Field>(); 
fields.Add(new Field() { Name = "FirstName" }); 
fields.Add(new Field() { Name = "FullName", 
         DependsOn = new[] {"FirstName","LastName"}}); 
fields.Add(new Field() { Name = "Age", 
         DependsOn = new[] { "DateOfBirth" } }); 
fields.Add(new Field() { Name = "LastName" }); 
fields.Add(new Field() { Name = "DateOfBirth" }); 

Итак, ясно, мы получаем наши детали в следующем порядке:

1. Первый номер
2. FullName
3. Возраст
4. LastName
5. DateOfBirth

Мой первый вопрос: Каков наилучший способ переставить элементы в моем списке/массив, так что зависимые столбцы (ПолноеИмя & Age) являются помещены после колонн они зависят от т-то вроде этого:

1. FirstName
2. La stName
3. ПолноеИмя
4. DateOfBirth
5. Возраст

Так как поля Возраствсегда приходят после DateOfBirth, который зависит от того.

Мой второй вопрос: Есть ли способ обнаружения циклических зависимостей? то есть, когда
Field1зависит отField2 и
Field2зависит отField3 и
Field3зависит отField1

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

Answer 1

Спасибо за подсказку Grzenio я действительно нашел что-то похожее на Яве в http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm

Ниже С # адаптации:

class Class1 
{ 
    public static void Run() 
    { 
     doTopologicalTest(); 
    } 

    private static void doTopologicalTest() 
    { 
     List<Field> fields = new List<Field>(); 
     fields.Add(new Field() { Name = "FirstName" }); 
     fields.Add(new Field() 
     { 
      Name = "FullName", 
      DependsOn = new[] { "FirstName", "LastName" } 
     }); 
     fields.Add(new Field() 
     { 
      Name = "Age", 
      DependsOn = new[] { "DateOfBirth" } 
     }); 
     fields.Add(new Field() { Name = "LastName" }); 
     fields.Add(new Field() { Name = "DateOfBirth" }); 

     foreach (var field in fields) 
     { 
      Console.WriteLine(field.Name); 
      if(field.DependsOn != null) 
       foreach (var item in field.DependsOn) 
       { 
        Console.WriteLine(" -{0}",item); 
       } 
     } 

     Console.WriteLine("\n...Sorting...\n"); 

     int[] sortOrder = getTopologicalSortOrder(fields); 

     for (int i = 0; i < sortOrder.Length; i++) 
     { 
      var field = fields[sortOrder[i]]; 
      Console.WriteLine(field.Name); 
      if (field.DependsOn != null) 
       foreach (var item in field.DependsOn) 
       { 
        Console.WriteLine(" -{0}", item); 
       } 
     } 

    } 

    private static int[] getTopologicalSortOrder(List<Field> fields) 
    { 
     TopologicalSorter g = new TopologicalSorter(fields.Count); 
     Dictionary<string, int> _indexes = new Dictionary<string, int>(); 

     //add vertices 
     for (int i = 0; i < fields.Count; i++) 
     { 
      _indexes[fields[i].Name.ToLower()] = g.AddVertex(i); 
     } 

     //add edges 
     for (int i = 0; i < fields.Count; i++) 
     { 
      if (fields[i].DependsOn != null) 
      { 
       for (int j = 0; j < fields[i].DependsOn.Length; j++) 
       { 
        g.AddEdge(i, 
         _indexes[fields[i].DependsOn[j].ToLower()]); 
       } 
      } 
     } 

     int[] result = g.Sort(); 
     return result; 

    } 


    class Field 
    { 
     public string Name { get; set; } 
     public string[] DependsOn { get; set; } 
    } 
} 

И код для топологического комплекса.CS

class TopologicalSorter 
{ 
    #region - Private Members - 

    private readonly int[] _vertices; // list of vertices 
    private readonly int[,] _matrix; // adjacency matrix 
    private int _numVerts; // current number of vertices 
    private readonly int[] _sortedArray; 

    #endregion 

    #region - CTors - 

    public TopologicalSorter(int size) 
    { 
     _vertices = new int[size]; 
     _matrix = new int[size, size]; 
     _numVerts = 0; 
     for (int i = 0; i < size; i++) 
      for (int j = 0; j < size; j++) 
       _matrix[i, j] = 0; 
     _sortedArray = new int[size]; // sorted vert labels 
    } 

    #endregion 

    #region - Public Methods - 

    public int AddVertex(int vertex) 
    { 
     _vertices[_numVerts++] = vertex; 
     return _numVerts - 1; 
    } 

    public void AddEdge(int start, int end) 
    { 
     _matrix[start, end] = 1; 
    } 

    public int[] Sort() // toplogical sort 
    { 
     while (_numVerts > 0) // while vertices remain, 
     { 
      // get a vertex with no successors, or -1 
      int currentVertex = noSuccessors(); 
      if (currentVertex == -1) // must be a cycle     
       throw new Exception("ERROR: Graph has cycles"); 

      // insert vertex label in sorted array (start at end) 
      _sortedArray[_numVerts - 1] = _vertices[currentVertex]; 

      deleteVertex(currentVertex); // delete vertex 
     } 

     // vertices all gone; return sortedArray 
     return _sortedArray; 
    } 

    #endregion 

    #region - Private Helper Methods - 

    // returns vert with no successors (or -1 if no such verts) 
    private int noSuccessors() 
    { 
     for (int row = 0; row < _numVerts; row++) 
     { 
      bool isEdge = false; // edge from row to column in adjMat 
      for (int col = 0; col < _numVerts; col++) 
      { 
       if (_matrix[row, col] > 0) // if edge to another, 
       { 
        isEdge = true; 
        break; // this vertex has a successor try another 
       } 
      } 
      if (!isEdge) // if no edges, has no successors 
       return row; 
     } 
     return -1; // no 
    } 

    private void deleteVertex(int delVert) 
    { 
     // if not last vertex, delete from vertexList 
     if (delVert != _numVerts - 1) 
     { 
      for (int j = delVert; j < _numVerts - 1; j++) 
       _vertices[j] = _vertices[j + 1]; 

      for (int row = delVert; row < _numVerts - 1; row++) 
       moveRowUp(row, _numVerts); 

      for (int col = delVert; col < _numVerts - 1; col++) 
       moveColLeft(col, _numVerts - 1); 
     } 
     _numVerts--; // one less vertex 
    } 

    private void moveRowUp(int row, int length) 
    { 
     for (int col = 0; col < length; col++) 
      _matrix[row, col] = _matrix[row + 1, col]; 
    } 

    private void moveColLeft(int col, int length) 
    { 
     for (int row = 0; row < length; row++) 
      _matrix[row, col] = _matrix[row, col + 1]; 
    } 

    #endregion 
} 

....

Answer 2

Похоже, что вам необходимо отсортировать эти товары в топологическом порядке. Есть множество страниц в Интернете, вероятно, Википедия является хорошим местом для начала: http://en.wikipedia.org/wiki/Topological_sort