C# と VB.NET の質問掲示板

■No20188 (れい さん) に返信

なるほど！簡単ですね。コードにしてみました。

using System;
using System.Collections.Generic;

namespace DetectCycle
{
    class Program
    {
        static void Main()
        {
            var table = new[] {
                        new Field( "AAA", "BBB", 2008, 6 ),
                        new Field( "BBB", "CCC", 2008, 6 ),
                        new Field( "CCC", "AAA", 2008, 6 ),
                        new Field( "AAA", "DDD", 2008, 6 ),
                        new Field( "EEE", "AAA", 2008, 6 ),
                        new Field( "EEE", "CCC", 2008, 6 ),
                        new Field( "EEE", "DDD", 2008, 6 ),
                        new Field( "BBB", "HHH", 2008, 6 ), // new
                        new Field( "HHH", "CCC", 2008, 6 ), // new
                        new Field( "III", "III", 2008, 6 ), // new ループ
                        new Field( "JJJ", "KKK", 2008, 6 ), // new 多重辺
                        new Field( "KKK", "JJJ", 2008, 6 ), // new 多重辺
                        new Field( "BBB", "BBB", 2008, 6 ), // new ループ

                        new Field( "z", "x", 2008, 6 ), // new
                        new Field( "x", "y", 2008, 6 ), // new
                        new Field( "y", "z", 2008, 6 ), // new
            };

            var x = new Graph( table );
            x.FindCycle();

            foreach ( int i in x.GetCycle() )
            {
                Console.WriteLine( i );
            }
            Console.ReadKey();
        }
    }

    public class Graph
    {
        private Field[] f;

        public Graph( Field[] f )
        {
            this.f = f;
        }

        public void FindCycle()
        {
            bool found = false;

            do
            {
                found = false;

                // 全ての点を調べる
                foreach ( var item in this.f )
                {
                    // 有効な辺か？
                    if ( !item.CycleCheck )
                        continue;

                    // 始点を指す有効な辺があるか？ 終点から辺は出ているか？
                    if ( Contains1( item.ParentCode ) && Contains2( item.ChildCode ) )
                    {
                        continue;
                    }

                    // サイクルの一部ではないので、この辺を削除する
                    item.CycleCheck = false;
                    found = true;
                }
            } while ( found );
        }

        // code(頂点)を指す辺(項)があるかどうか判定する
        private bool Contains1( string code )
        {
            foreach ( var item in this.f )
            {
                if ( item.CycleCheck && item.ChildCode == code )
                    return true;
            }
            return false;
        }

        // code(頂点)に繋がる辺(項)があるかどうか判定する
        private bool Contains2( string code )
        {
            foreach ( var item in this.f )
            {
                if ( item.CycleCheck && item.ParentCode == code )
                    return true;
            }
            return false;
        }

        // 見つけたサイクルの辺番号(データベースのrowIndex)を返す
        public List<int> GetCycle()
        {
            List<int> list = new List<int>();

            for (int i = 0; i < this.f.Length; i++)
            {
                if ( this.f[ i ].CycleCheck )
                    list.Add( i );
            }
            return list;
        }
    }

    // データベースの１項目相当
    public class Field
    {
        public string ParentCode { set; get; }
        public string ChildCode { set; get; }
        public int Year { set; get; }
        public int Month { set; get; }
        public bool CycleCheck { set; get; }

        public Field( string p, string c, int y, int m )
        {
            this.ParentCode = p;
            this.ChildCode = c;
            this.Year = y;
            this.Month = m;
            this.CycleCheck = true;
        }

        public override string ToString()
        {
            return string.Format( "{0} {1}", this.ParentCode, this.ChildCode );
        }
    }
}