スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

マルチパラダイム時代におけるデータ構造 第21回 ー 自由な木とグラフは本当に閉じているのか問題

 この記事は、「マルチパラダイム時代におけるデータ構造 第20回 ー 閉じている?閉じていない?それが問題だ」の続きです。前回は、閉路があるグラフについて解説しました。今回は、閉じていない木が表すデータ構造と、グラフの閉路判定問題について解説します。
 グラフも結構使用するのですが、プログラミングではもっと広く使われているデータ構造があります。それは、木構造(きこうぞう)です。閉じていないグラフを木構造と呼び、プログラミングで広く使用しています。より正確にいうと、プログラミングでは、今回紹介する木構造を自由木と呼んでおり、他にも色々な木構造が存在します。
 それがわかれば話は簡単。さくっと実装してみましょう♪

using System;
using DataStructure;

namespace Test
{
    class FreeTreeTest<T> : IDataFreeManagerTest<T>
    {
        //指定したデータが選択可能か否か判定する。
        protected override bool CanSelect(
            IDataManager<T> target,
            int count,
            T value )
        {
            bool result = false;
            var temp = ( FreeTree<T> ) target;
            if ( temp.Count == 0 ) return false;
            try {
                T returnValue = temp.Select( count - 1 );
                result = returnValue.Equals( value );
            } catch ( IndexOutOfRangeException ) {
            }
            return result;
        }

        //グラフが閉じてしまうデータを発生させるテスト。
        private void FreeTreeInsertDataHasClosedTest( )
        {
            int init = 0;
            int value = init;
            FreeTree<int> g = new FreeTree<int>( value++ );
            g.Insert( value++ );
            var n1 = g.GetNode( 0 );
            n1.Insert( value++ );
            ArgumentException ae = null;
            try {
                var n2 = n1.GetNode( 1 );
                n2.Insert( init );
            } catch ( ArgumentException e ) {
                ae = e;
            }
            if ( ae == null )
                throw new TestException(
                    "FreeTreeInsertDataHasClosedTest",
                    "閉路を生む値を許可しないでください。" );
        }

        //グラフが閉じないデータを発生させるテスト。
        private void FreeTreeInsertDataHasNotClosedTest( )
        {
            int init = 0;
            int value = init;
            FreeTree<int> g = new FreeTree<int>( value++ );
            g.Insert( value++ );
            var n1 = g.GetNode( 0 );
            n1.Insert( value++ );
            ArgumentException ae = null;
            try {
                var n2 = n1.GetNode( 1 );
                n2.Insert( value++ );
            } catch ( ArgumentException e ) {
                ae = e;
            }
            if ( ae != null )
                throw new TestException(
                    "FreeTreeInsertDataHasNotClosedTest",
                    "閉路を生まない値は許可してください。" );
        }

        //全てのテストを実行する。
        public void AllTestExecute(
            Func<FreeTree<T>> initFunc,
            T one,
            T two,
            T selectRightValue )
        {
            this.OneDataLifeCycleTest( initFunc(), one );
            this.TwoDataLifeCycleTest( initFunc(), one, two );
            this.OneDataLifeCycleToIndexTest( initFunc(), one );
            this.TwoDataLifeCycleToIndexTest( initFunc(), one, two );
            this.FreeTreeInsertDataHasClosedTest();
            this.FreeTreeInsertDataHasNotClosedTest();
        }
    }
}

using System;

namespace DataStructure
{
    //自由木:閉路のないグラフ。
    public class FreeTree<T> : Graph<T>
    {
        //値を指定してインスタンスを生成する。
        public FreeTree( T value ) 
            : base( value ) { }

        //値を発生させる。
        public override void Insert( T value )
        {
            var newNode = new FreeTree<T>( value );
            this.Node.Insert( newNode );
            if ( newNode.HasClosed() )
                throw new ArgumentException(
                    "閉路を生む値は指定できません。" );
        }

        //任意の位置へ値を発生させる。
        public override void Insert( T value, int index )
        {
            var newNode = new FreeTree<T>( value );
            this.Node.Insert( newNode, index );
            if ( newNode.HasClosed() )
                throw new ArgumentException( 
                    "閉路を生む値は指定できません。" );
        }
    }
}

発想は簡単です。発生した後閉じていれば木ではないので例外を発生させるだけです。これで、終了!といいたいところですが、残念ながらテストは失敗します。理由は2つあります。1つめの理由、新しく発生したノードが、発生させたノードを知らないからです。グラフをたどれないのは大きな問題です。2つめの理由は、自分以外の値が重複しているか知らないからです。1つめの理由と関係していますが、発生させるノードにかかわらず、閉じているか否かは決まるはずなので、これもまた問題です。
 2つの問題をまとめると、「グラフの全ノード辿れない場合がある」という事になります。この問題を解決するには、データ発生時に隣接ノードを追加し、個々のノードを識別するためにIDを付与する必要があります。ただし、新たに発生したノードに、隣接ノードの情報を設定すると、無限ループになる可能性が生じます。何故ならば、どこのノードをすでに訪問したのか考えないと、同じノードを何度も訪問してしまい、アルゴリズムが終了しなくなるからです。
 初心者にとって、グラフの閉路判定は難しいので、テストを用意し慎重にプログラミングしましょう。

using System;
using DataStructure;

namespace Test
{
    class GraphTest<T> : IDataFreeManagerTest<T>
    {
        //関係のないプログラムは省略

        //グラフが閉じている場合のテスト。
        private void GraphHasClosedTest( )
        {
            int init = 0;
            int value = init;
            Graph<int>[ ] objs = new Graph<int>[ 3 ];
            Graph<int> g = new Graph<int>( value++ );
            objs[ 0 ] = g;
            g.Insert( value++ );
            var n1 = g.GetNode( 0 );
            objs[ 1 ] = n1;
            n1.Insert( value++ );
            var n2 = n1.GetNode( 1 );
            objs[ 2 ] = n2;
            n2.Insert( init );
            for ( int i = 0 ; i < objs.Length ; ++i ) {
                if ( !objs[ i ].HasClosed() )
                    throw new TestException(
                        "GraphHasClosedTest",
                        "閉じているグラフを判別できませんでした。" );
            }
        }

        //グラフが閉じていない場合のテスト。
        private void GraphHasNotClosedTest( )
        {
            int init = 0;
            int value = init;
            Graph<int>[ ] objs = new Graph<int>[ 3 ];
            Graph<int> g = new Graph<int>( value++ );
            objs[ 0 ] = g;
            g.Insert( value++ );
            var n1 = g.GetNode( 0 );
            objs[ 1 ] = n1;
            n1.Insert( value++ );
            var n2 = n1.GetNode( 1 );
            objs[ 2 ] = n2;
            n2.Insert( value++ );
            for ( int i = 0 ; i < objs.Length ; ++i ) {
                if ( objs[ i ].HasClosed() )
                    throw new TestException(
                        "GraphHasNotClosedTest",
                        "閉じていないグラフを判別できませんでした。" );
            }
        }
}

このテストにパスするには、無限ループを避けるために、すでに訪問したノードをチェックしつつ処理を行う事を意識しつつ実装します。
 極力シンプルに実装すると、グラフはこんな具合になります・・・

using System;
using System.Text;

namespace DataStructure
{
    //ネットワーク形状のデータ構造グラフ。
    public class Graph<T> : IDataFreeManager<T>
    {
        //関係のない部分は省略

        //ノードの識別子。
        private int _id;
        public int ID
        {
            get { return this._id; }
            protected set { this._id = value; }
        }

        //ノードの識別子と値を指定してインスタンスを生成する。
        protected Graph( T value, int id )
        {
            this.Value = value;
            this.ID = id;
            this._elemets = new ConsCell<Graph<T>>();
        }

        //ノードの値と識別子および、
        //隣接ノードを指定してインスタンスを生成する。
        protected Graph( T value, int id, Graph<T> next )
        {
            this.Value = value;
            this.ID = id;
            this._elemets = new ConsCell<Graph<T>>();
            this._elemets.Insert( next );
        }

        //新しい隣接ノードを発生させる。
        public virtual void Insert( T value )
        {
            var newNode = new Graph<T>(
                        value,
                        this.ID + 1,
                        this );
            this._elemets.Insert( newNode );
        }

        //任意の位置へ新しい隣接ノードを発生させる。
        public virtual void Insert( T value, int index )
        {
            var newNode = new Graph<T>(
                       value,
                       this.ID + 1,
                       this );
            this._elemets.Insert( newNode, index );
        }

        //対象となるノードが既に探索済みか否かを判定する。
        private bool IsVisit(
            int targetID, IDataFreeManager<int> searchNode )
        {
            for ( int i = 0 ; i < searchNode.Count ; ++i ) {
                int n = searchNode.Select( i );
                if ( n == targetID )
                    return true;

            }
            return false;
        }

        //グラフが閉じているか否かを判定する。
        public bool HasClosed( )
        {
            var values = new ConsCell<T>();
            var searchNode = new ConsCell<int>();
            return this.HasClosed( values, searchNode );
        }

        //グラフが閉じているか否かを判定する。
        //※既に存在する要素があれば閉じている。
        private bool HasClosed(
            ConsCell<T> values,
            ConsCell<int> searchNode )
        {
            //要素が重複しているか判定&要素の追加
            for ( int i = 0 ; i < values.Count ; ++i ) {
                var n = values.Select( i );
                if ( this.Value.Equals( n ) )
                    return true;
            }
            values.Insert( this.Value );
            //入れ子で判定
            searchNode.Insert( this.ID );
            for ( int i = 0 ; i < this._elemets.Count ; ++i ) {
                var n = this._elemets.Select( i );
                if ( !this.IsVisit( n.ID, searchNode ) ) {
                    bool hit = n.HasClosed( values, searchNode );
                    if ( hit ) return true;
                }
            }
            return false;
        }
    }
}

もちろんグラフを親としている自由木の実装も変更します。

using System;

namespace DataStructure
{
    //自由木:閉路のないグラフ。
    public class FreeTree<T> : Graph<T>
    {
        //値を指定してインスタンスを生成する。
        public FreeTree( T value )
            : base( value ) { }

        //ノードの値と識別子および、
        //隣接ノードを指定してインスタンスを生成する。
        protected FreeTree( T value, int id, Graph<T> next )
            : base( value, id, next ) { }

        //値を発生させる。
        public override void Insert( T value )
        {
            var newNode = new FreeTree<T>(
                        value,
                        this.ID + 1,
                        this );
            this.Node.Insert( newNode );
            if ( newNode.HasClosed() )
                throw new ArgumentException(
                    "閉路を生む値は指定できません。" );
        }

        //任意の位置へ値を発生させる。
        public override void Insert( T value, int index )
        {
            var newNode = new FreeTree<T>(
                        value,
                        this.ID + 1,
                        this );
            this.Node.Insert( newNode, index );
            if ( newNode.HasClosed() )
                throw new ArgumentException(
                    "閉路を生む値は指定できません。" );
        }
    }
}

ちょっと難しいと思いますが、ステップ実行してみると理解できると思います。
 今回は、無限ループの回避法についての解説が主でした。実は無限ループはよく遭遇する危険なので、今回得た知識は色々な場面で役に立つと思います。データ構造の話題は、木構造が登場すると断然面白くなります。続きをお楽しみに♪
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。