Comment pouvez-vous réorganiser les éléments d'un tableau en fonction de ses dépendances? et détecter également une dépendance cyclique

Question

Étant donné le type:

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

Disons que j'ai un tableau de Field articles:

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

Il est donc clair que nous obtenons nos articles dans l'ordre suivant:

1. Prénom
2. Nom complet
3. Âge
4. LastName
5. DateOfBirth

Ma première question: Quelle est la meilleure façon de réorganiser les éléments dans ma liste/tableau afin que les colonnes dépendantes (FullName & âge) sont placé après les colonnes dont ils dépendent-à-dire quelque chose comme ceci:

1. FirstName
2. la stName
3. FullName
4. DateOfBirth
5. Âge

Alors champs comme Âgetoujours venir après DateOfBirth dont elle dépend.

Ma deuxième question: Y at-il un moyen de détecter dépendances cycliques? à savoir quand
Field1dépend deField2 et
Field2dépend deField3 et
Field3dépendField1

Nous ne sommes pas pris dans un cercle. par exemple. Lorsque vous avez terminé vos études, vous avez besoin de 2 ans d'expérience professionnelle pour trouver un emploi. Mais pour obtenir l'expérience de travail, vous devez d'abord avoir le travail.

Answer 1

Merci pour le conseil Grzenio j'ai trouvé quelque chose de similaire en java à http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm

est inférieure à l'adaptation C#:

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

Et le code pour TopologicalSort.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

Il semble que vous ayez besoin de trier ces éléments dans l'ordre topologique. Il y a des tas de pages sur le web, probablement Wikipedia est un bon endroit pour commencer: http://en.wikipedia.org/wiki/Topological_sort