|
siokoshouです。だめだねぇ、バグってますねぇｗ
直してみました。今度こそ、一筆書きアルゴリズムのはずです。
using System;
using System.Collections.Generic;
using System.Linq;
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();
Console.WriteLine();
foreach ( int i in x.GetCycle() )
{
Console.WriteLine( i );
}
Console.ReadKey();
}
}
public class Graph
{
private List<int> cycle = new List<int>();
private Field[] f;
public Graph( Field[] f )
{
this.f = f;
}
public void FindCycle()
{
// 全ての点を調べる
for ( int i = 0; i < f.Length; i++ )
{
List<Pair> list = new List<Pair>();
var pair = new Pair( i, this.f[ i ] );
list.Add( pair );
// ループ？
if ( pair.Field.ParentCode == pair.Field.ChildCode )
{
// サイクルを見つけた
FoundCycle( list );
continue;
}
InnerFindCycle( list );
}
}
// 経路探索ループ
private void InnerFindCycle( List<Pair> list )
{
Pair last = list.Last();
foreach ( var item in Find( last.Field.ChildCode, list ) )
{
// ループ？
if ( item.Field.ParentCode == item.Field.ChildCode )
{
// 途中の経路でループを見つけた。この道は無視する。
continue;
}
// 辺の終点が最初の始点と一致する？
if ( item.Field.ChildCode == list[ 0 ].Field.ParentCode )
{
// サイクルを見つけた
list.Add( item );
FoundCycle( list );
list.RemoveAt( list.Count - 1 );
continue;
}
// 辺の終点がリスト中の最初以外の始点と一致した場合、この道はサイクルに接続しているサイクルではない道
if ( list.Skip( 1 ).Where( p => p.Field.ParentCode == item.Field.ChildCode ).Any() )
continue;
// どちらでもない場合、続きの道を調べる
list.Add( item );
InnerFindCycle( list ); // 再帰
list.RemoveAt( list.Count - 1 );
}
}
// データベースから次の辺を探す処理
private IEnumerable<Pair> Find( string code, List<Pair> list )
{
return this.f.Select( ( e, index ) => new Pair( index, e ) )
.Where( p => p.Field.ParentCode == code )
.Where( p => !list.Any( l => l.Field.ParentCode == p.Field.ParentCode && l.Field.ChildCode == p.Field.ChildCode ) );
}
// サイクルを見つけたときの処理
private void FoundCycle( List<Pair> list )
{
List<int> tmp = new List<int>();
foreach ( var item in list )
{
int n = item.Index;
if ( !this.cycle.Contains<int>( n ) )
{
this.cycle.Add( n );
}
this.cycle.Sort();
}
foreach ( var item in list )
{
Console.WriteLine( item );
}
Console.WriteLine();
}
public int[] GetCycle()
{
return this.cycle.ToArray();
}
}
// 一時保存用のデータ構造
public struct Pair
{
public int Index;
public Field Field;
public Pair( int i, Field f )
{
this.Index = i;
this.Field = f;
}
public override string ToString()
{
return string.Format( "{0,2} {1}", this.Index, this.Field );
}
}
// データベースの１項目相当
public class Field
{
public string ParentCode { set; get; }
public string ChildCode { set; get; }
public int Year { set; get; }
public int Month { set; get; }
public Field( string p, string c, int y, int m )
{
this.ParentCode = p;
this.ChildCode = c;
this.Year = y;
this.Month = m;
}
public override string ToString()
{
return string.Format( "{0} {1}", this.ParentCode, this.ChildCode );
}
}
}
|
