上流から下流へ

今、家系図が与えられているものとする。遺伝子型データのシミュレーションをするとする。家系図の上流のサンプルの遺伝子型を決めたあとに、下流のサンプルの遺伝子型を決める必要がある。

次のようにすることにする。
サンプル総数　N
家系図は、int tree = new int[N][2] (i=0,1,2,...,N-1)
で与えるものとし、

tree[i][0]はサンプルiの母親のID、tree[i][1]はサンプルiの父親のIDとする。
家系図内に親IDの指定がない場合は、母集団からランダムに選ばれた個人が適合するとする。
親指定がないサンプルは、初めにデータ作成できる。
以降は、指定親がある限りは、その親のデータ作成が終わっていれば、データ作成できる。
そのための順番をとりだす。同順位の場合は、どちらのデータを先に作ってもよい。

	public static int[] pedigreeOrder(int[][] tr){
		//親子関係を見て、上流からの順番を与える
		int[] ret = new int[tr.length];

		double min=0;
		double max=1;
		boolean check=false;
		while(!check){
			update(tr,ret);
			for(int i=0;i<ret.length;i++){
				System.out.print(ret[i]+"\t");
			}
			System.out.println();
			check=checkOrder(tr,ret);
		}



		return ret;
	}
	public static void update(int[][] tr, int[] order){
		for(int i=0;i<tr.length;i++){
			if(tr[i][0]!=na){
				if(order[i]<=order[tr[i][0]]){
					order[i]=order[tr[i][0]]+1;
				}

			}
			if(tr[i][1]!=na){
				if(order[i]<=order[tr[i][1]]){
					order[i]=order[tr[i][1]]+1;
				}

			}
		}

	}
	public static boolean checkOrder(int[][] tr,int[] order){
		boolean ret= true;
		for(int i=0;i<tr.length;i++){
			if(tr[i][0]!=na){
				if(order[i]<=order[tr[i][0]]){
					ret=false;
					return ret;
				}
			}
			if(tr[i][1]!=na){
				if(order[i]<=order[tr[i][1]]){
					ret=false;
					return ret;
				}
			}
		}

実行例

int N=8;

		int[][] tree=new int[N][2];
		tree[0][0]=-9;
		tree[0][1]=-9;
		tree[1][0]=-9;
		tree[1][1]=-9;
		tree[2][0]=0;
		tree[2][1]=1;
		tree[3][0]=-9;
		tree[3][1]=-9;
		tree[4][0]=2;
		tree[4][1]=3;
		tree[5][0]=2;
		tree[5][1]=3;
		tree[6][0]=0;
		tree[6][1]=4;
		tree[7][0]=6;
		tree[7][1]=3;

について

0	0	1	0	2	2	3	4