Core/Castle.Core/Internal/TopologicalSortAlgo.cs

   1 // Copyright 2004-2007 Castle Project - http://www.castleproject.org/
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 namespace Castle.Core.Internal
  16 {
  17         using System.Diagnostics;
  18
  19         public abstract class TopologicalSortAlgo
  20         {
  21                 public static IVertex[] Sort(IVertex[] graphNodes)
  22                 {
  23                         ColorsSet colors = new ColorsSet(graphNodes);
  24                         TimestampSet discovery = new TimestampSet();
  25                         TimestampSet finish = new TimestampSet();
  26                         LinkedList list = new LinkedList();
  27
  28                         int time = 0;
  29
  30                         foreach(IVertex node in graphNodes)
  31                         {
  32                                 if (colors.ColorOf(node) == VertexColor.White)
  33                                 {
  34                                         Visit(node, colors, discovery, finish, list, ref time);
  35                                 }
  36                         }
  37
  38                         return (IVertex[]) list.ToArray(typeof(IVertex));
  39                 }
  40
  41                 private static void Visit(IVertex node, ColorsSet colors,
  42                                           TimestampSet discovery, TimestampSet finish, LinkedList list, ref int time)
  43                 {
  44                         colors.Set(node, VertexColor.Gray);
  45
  46                         discovery.Register(node, time++);
  47
  48                         foreach(IVertex child in node.Adjacencies)
  49                         {
  50                                 if (colors.ColorOf(child) == VertexColor.White)
  51                                 {
  52                                         Visit(child, colors, discovery, finish, list, ref time);
  53                                 }
  54                         }
  55
  56                         finish.Register(node, time++);
  57
  58 #if DEBUG
  59                         Debug.Assert(discovery.TimeOf(node) < finish.TimeOf(node));
  60 #endif
  61
  62                         list.AddFirst(node);
  63
  64                         colors.Set(node, VertexColor.Black);
  65                 }
  66         }
  67 }