Directed Acyclic Graph

• 渡る者の途絶えた橋 （東方算程譚）

理解するために自分なりに書き下してみるテストです。
ライブラリにしてみました。

DirectedAcyclicGraph.cs

public static class DirectedAcyclicGraph
{
  public static bool IsDAG<TItem>(List<Tuple<TItem, TItem>> deps)
  {
    // 作業用にリストをコピー
    var workDeps = deps.Select(s => s).ToList();

    while (true)
    {
      // 表示
      OutList(workDeps);

      // 入口 / 出口セットの作成
      var parent = new List<TItem>();
      var child = new List<TItem>();
      foreach (var item in workDeps)
      {
        parent.Add(item.Item1);
        child.Add(item.Item2);
      }

      // 片方にしかない要素を抽出
      var dif = parent.Where(pItem => !child.Contains(pItem)).Concat(child.Where(cItem => !parent.Contains(cItem))).ToList();

      if (dif == null || dif.Count == 0)
      {
        break;
      }

      // 入口 / 出口のいずれかが dif にある場合はリストから取り除く
      workDeps = workDeps.Where(s => !dif.Contains(s.Item1) && !dif.Contains(s.Item2)).ToList();
    }

    if (workDeps == null || workDeps.Count == 0)
    {
      return true;
    }
    else
    {
      return false;
    }
  }

  private static void OutList<TItem>(List<Tuple<TItem, TItem>> deps)
  {
    foreach (var item in deps)
    {
      Console.WriteLine("{0} -> {1}", item.Item1, item.Item2);
    }
    Console.WriteLine();
  }
}

使い方はこんな感じで。

class Program
{
  static void Main(string[] args)
  {
    if (args == null || args.Length == 0 || String.IsNullOrEmpty(args[0]))
    {
      args = new[] { "1" };
    }
    var deps = GetSample(args[0]);
    if (DirectedAcyclicGraph.IsDAG(deps))
    {
      Console.WriteLine("DAG!!");
    }
    else
    {
      Console.WriteLine("cyclic!!");
    }
    Console.ReadLine();
  }

  static List<Tuple<char, char>> GetSample(string pattern)
  {
    var deps = new List<Tuple<char, char>>();
    switch (pattern)
    {
      case "1":
        deps.Add(Tuple.Create('A', 'B'));
        deps.Add(Tuple.Create('B', 'C'));
        deps.Add(Tuple.Create('A', 'C'));
        deps.Add(Tuple.Create('A', 'D'));
        deps.Add(Tuple.Create('C', 'D'));
        break;
      case "2":
        deps.Add(Tuple.Create('A', 'B'));
        deps.Add(Tuple.Create('A', 'C'));
        deps.Add(Tuple.Create('B', 'C'));
        deps.Add(Tuple.Create('B', 'D'));
        deps.Add(Tuple.Create('D', 'A'));
        deps.Add(Tuple.Create('D', 'C'));
        break;
      case "3":
        deps.Add(Tuple.Create('A', 'B'));
        deps.Add(Tuple.Create('B', 'C'));
        deps.Add(Tuple.Create('C', 'D'));
        deps.Add(Tuple.Create('D', 'E'));
        deps.Add(Tuple.Create('E', 'F'));
        deps.Add(Tuple.Create('F', 'G'));
        deps.Add(Tuple.Create('G', 'H'));
        deps.Add(Tuple.Create('H', 'F'));
        break;
      default:
        throw new ArgumentException("パラメータ不正");
    }
    return deps;
  }
}