第７章 有向グラフ、有限オートマトン 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』
本駆け足シリーズの全体の目次はこちら
- 用語
- 有向グラフ directed graph (digraph)、弧 arc、始点 initial point、終点 terminal point、ループ loop、多重弧 parallel arc、出次数 outdegree、入次数 indegree、閉じた歩道 closed walk、全域歩道 spanning walk、半歩道 semiwalk、半小道 semitrail、半道 semipath、弱連結 weakly connected、片方向連結 unilaterally conncted、強連結 strongly connected、狭義の片方向 strictly unilateral、狭義の弱 strictly weak
- 有向グラフは非負整数正方行列
- 有限状態機械
- 入力記号A、機械の内部状態S、出力記号Z、SxAからSへの状態推移関数 f 、SxAからZへの出力関数 g にて定義される。Sの初期状態が与えられることも
- 有限状態機械の表現方法
- 状態推移表(テンソル)
- 状態推移図 state diagram(ラベル付き有向グラフ)
- 有限オートマトン
- 入力記号A、内部状態S、Sの部分集合T(受理状態 accepting states)、Sの初期状態、SxAからSへの状態推移関数 f
- 有限状態機械の出力記号に代えて、受理(YesかNoかの出力)を持つ
- プログラミング問題
- indegree outdegreeは次数のカウントをedge入力の前後に留意してカウントすればよい->CountVandDeg, vertex[i][2]=indegree,vertex[i][3]=outdegree
- 有向きグラフの行列は、edgeの向きに留意する点のみが無向グラフのそれと変わるのみである->CreateAdjMatrix, adjDirectedMatrix
- 有向グラフの弱連結性は、有向グラフを無向グラフとみなしたときの行列による連結判断に同じ->Connection
- 片方向連結は、有効グラフの行列表現において、A+A^2+...+A^(n-1)の非対角成分について、対称な２要素の両方がゼロであるようなij組がないこと->ConnectionUnilateralDirected
- 有向グラフの強連結性は、有向グラフの行列表現において、無向の場合のそれと同様(A+A^2+...A^(n-1)の非対角成分のいずれもゼロでないこと)->ConnectionDirected
- ソースは、第５、６章のそれの改変版
public class Graph {
int numV;
int numE;
int directed;//direcetd graph 1, non-directed graph 0 or null
int[][] edgeMatrix;
int[][] vertex;//id, name,degree, if directed graph, [1]=indegree+outdigree,[2]=indegree,[3]=outdegree
int[][] adjMatrix;
int[][] adjDirectedMatrix;
int[][] conMatrix;
Tensor connectionMatrix;
Tensor connectionMatrixDirected;public static void main(String[] args) {
//Create Graph object from data on edges
//int[][] e = {{1,2},{1,5},{1,3},{2,3},{1,4},{4,5},{3,5},{3,4}};
int[][] e = {{2,3},{1,2},{1,5},{5,6},{4,6}};
Graph g1 = new Graph(e);
CountVandDeg(g1);
CreateAdjMatrix(g1);
CreateDirectedAdjMatrix(g1);
CreateConMatrix(g1);
//connected?
int connection = Connection(g1);
ConnectionDirected(g1);
System.out.println("Connected ? (0=unconnected 1=connected)\n"+connection);
PrintGraph(g1,"\t","\n");
int[] addedge = {1,2};
Graph addedG=AddEdge(g1,addedge);
connection = Connection(addedG);
ConnectionDirected(addedG);
System.out.println("After addition of an edge. Connected ? (0=unconnected 1=connected)\n"+connection);
PrintGraph(addedG,"\t","\n");
//coloring
//int[][] ec= {{1,2},{2,3},{5,3},{3,6},{4,1},{5,6},{1,3},{4,5},{5,2},{6,4}};
int[][] ec= {{1,2},{1,3},{1,7},{1,4},{2,3},{2,4},{2,5},{3,5},{3,6},{3,7},{4,7},{4,5},{5,6},{5,7},{5,8},{6,8},{7,8}};
Graph colG = new Graph(ec);
CreateDataGraph(colG);
int chromaticN = WelchPowell(colG);
System.out.println("WelchPowell " + chromaticN);
//int[][] eweight = {{1,2,3},{2,3,2},{5,3,3},{3,6,1},{4,1,2},{5,6,2},{1,3,1},{4,5,2},{5,2,1},{6,4,2}};
int[][] eweight ={{1,2,1},{1,3,1}};
Graph ew = new Graph(eweight);
CreateDataGraph(ew);
PrintGraph(ew,"\t","\n");
//Create graph withou edge
int[] vert ={1,2,3,4};
/*
int[][] emptyE ={};
Graph eGraph = new Graph(emptyE);
CreateDataGraph(eGraph);
AddVertex(eGraph,vert);
PrintGraphE(eGraph,"\t","\n");
CreateDataGraph2(eGraph);
*/
Graph eGraph = CreateVertexGraph(vert);
PrintGraph(eGraph,"\t","\n");
//System.out.println("############");
int[][] elist ={{1,2,5},{2,3,2},{3,4,2},{2,4,20}};
eGraph = MinimumSpanningTree(eGraph,elist);
int weakConnection = Connection(eGraph);
System.out.println("Weak connection " + weakConnection);
int unilateralConnection = ConnectionUnilateralDirected(eGraph);
System.out.println("Unilateral connection " + unilateralConnection);
int strongConnection = ConnectionDirected(eGraph);
System.out.println("Strong connection " + strongConnection);
PrintGraph(eGraph,"\t","\n");
}
public Graph(int[][] edge){
edgeMatrix = new int[edge.length][3];
for(int i=0;i<edge.length;i++){
edgeMatrix[i][0]=edge[i][0];
edgeMatrix[i][1]=edge[i][1];
if(edge[i].length<3){
edgeMatrix[i][2]=1;
}else{
edgeMatrix[i][2]=edge[i][2];
}
}
numE = edgeMatrix.length;
}
public Graph(int[][] e,int[][] v){//vertex without edge can be registered
vertex = new int[v.length][2];
for(int i=0;i<vertex.length;i++){
vertex[i][0]=v[i][0];
vertex[i][1]=0;
}
for(int i=0;i<e.length;i++){
}
}
public static String StringGraph(Graph g,String sep1,String sep2){
String ret = "";
ret += "No.edge seqential_order id startV endV length" +g.numE + sep2;
for(int i=0;i<g.edgeMatrix.length;i++){
ret += i + sep1 + g.edgeMatrix[i][0] + sep1 + g.edgeMatrix[i][1] + sep1 +g.edgeMatrix[i][2]+sep2;
}
ret += "No.vertex sequential_order id degree indegree outdegree" + g.numV +sep2;
for(int i=0;i<g.vertex.length;i++){
ret += i + sep1 + g.vertex[i][0] + sep1 + g.vertex[i][1] + sep1 + g.vertex[i][2]+sep1 + g.vertex[i][3]+sep2;
}
ret += "adjMatrix numVxnumV" + sep2;
for(int i=0;i<g.adjMatrix.length;i++){
for(int j=0;j<g.adjMatrix[i].length;j++){
ret += g.adjMatrix[i][j] + sep1;
}
ret += sep2;
}
ret += "DirectedAdjMatrix numVxnumV" + sep2;
for(int i=0;i<g.adjDirectedMatrix.length;i++){
for(int j=0;j<g.adjDirectedMatrix[i].length;j++){
ret += g.adjDirectedMatrix[i][j] + sep1;
}
ret += sep2;
}
ret += "conMatrix numVxnumE" + sep2;
for(int i=0;i<g.conMatrix.length;i++){
for(int j=0;j<g.conMatrix[i].length;j++){
ret += g.conMatrix[i][j] + sep1;
}
ret += sep2;
}
ret += "Sequential sum of adjM^n form n=1 to numV-1 \n";
ret += Tensor.StringMatTensor(g.connectionMatrix,"\t","\n");
ret += "Sequential sum of adjDirectedM^n form n=1 to numV-1 \n";
ret += Tensor.StringMatTensor(g.connectionMatrixDirected,"\t","\n");
return ret;
}
public static void PrintGraph(Graph g,String sep1,String sep2){
String ret = StringGraph(g,sep1,sep2);
System.out.println(ret);
}
public static void CountVandDeg(Graph g){
if(g.edgeMatrix.length==0 && g.numV==0){
g.numV=0;
return;
}
/*
g.vertex = new int[2][4];
g.vertex[0][0]=g.edgeMatrix[0][0];
g.vertex[0][1]=1;
g.vertex[0][2]=0;
g.vertex[0][3]=1;
g.vertex[1][0]=g.edgeMatrix[0][1];
g.vertex[1][1]=1;
*/
for(int i=0;i<g.edgeMatrix.length;i++){
//System.out.println("countV" + i);
boolean[] flag = {true, true};
int[] dupv = new int[2];
for(int m=0;m<2;m++){
for(int j=0;j<g.numV;j++){
if(g.vertex[j][0]==g.edgeMatrix[i][m]){
flag[m]=false;
dupv[m]=j;
}
}
}
for(int m=0;m<2;m++){
if(flag[m]){
int[][] tmp = new int[g.numV][4];
for(int k=0;k<g.numV;k++){
tmp[k][0]=g.vertex[k][0];
tmp[k][1]=g.vertex[k][1];
tmp[k][2]=g.vertex[k][2];
tmp[k][3]=g.vertex[k][3];
}
g.vertex=new int[tmp.length+1][4];
for(int k=0;k<tmp.length;k++){
g.vertex[k][0]=tmp[k][0];
g.vertex[k][1]=tmp[k][1];
g.vertex[k][2]=tmp[k][2];
g.vertex[k][3]=tmp[k][3];
}
g.vertex[tmp.length][0]=g.edgeMatrix[i][m];
g.vertex[tmp.length][1]=1;
g.vertex[tmp.length][m+2]=1;
g.numV++;
}else{
g.vertex[dupv[m]][1]++;
g.vertex[dupv[m]][m+2]++;
}
}
}
//g.numV=g.vertex.length;
}
public static void CreateAdjMatrix(Graph g){
//System.out.println("numV " + g.numV);
g.adjMatrix = new int[g.numV][g.numV];
for(int i=0;i<g.numV;i++){
for(int j=0;j<g.numV;j++){
g.adjMatrix[i][j]=0;
}
}
for(int i=0;i<g.edgeMatrix.length;i++){
int[] vid = new int[2];
for(int j=0;j<g.vertex.length;j++){
if(g.vertex[j][0]==g.edgeMatrix[i][0]){
//vid[0]=j;
vid[0]=g.vertex[j][0];
}
if(g.vertex[j][0]==g.edgeMatrix[i][1]){
//vid[1]=j;
vid[1]=g.vertex[j][0];
}
}
//g.adjMatrix[vid[0]][vid[1]]=1;
//g.adjMatrix[vid[1]][vid[0]]=1;
g.adjMatrix[vid[0]-1][vid[1]-1]=1;
g.adjMatrix[vid[1]-1][vid[0]-1]=1;
//g.adjMatrix[g.edgeMatrix[i][0]][g.edgeMatrix[i][1]]=1;
//g.adjMatrix[g.edgeMatrix[i][1]][g.edgeMatrix[i][0]]=1;
}
}public static void CreateDirectedAdjMatrix(Graph g){
//System.out.println("numV " + g.numV);
g.adjDirectedMatrix = new int[g.numV][g.numV];
for(int i=0;i<g.numV;i++){
for(int j=0;j<g.numV;j++){
g.adjDirectedMatrix[i][j]=0;
}
}
for(int i=0;i<g.edgeMatrix.length;i++){
int[] vid = new int[2];
for(int j=0;j<g.vertex.length;j++){
if(g.vertex[j][0]==g.edgeMatrix[i][0]){
//vid[0]=j;
vid[0]=g.vertex[j][0];
}
if(g.vertex[j][0]==g.edgeMatrix[i][1]){
//vid[1]=j;
vid[1]=g.vertex[j][0];
}
}
//g.adjMatrix[vid[0]][vid[1]]=1;
//g.adjMatrix[vid[1]][vid[0]]=1;
g.adjDirectedMatrix[vid[0]-1][vid[1]-1]++;;
//g.adjMatrix[vid[1]-1][vid[0]-1]=1;
//g.adjMatrix[g.edgeMatrix[i][0]][g.edgeMatrix[i][1]]=1;
//g.adjMatrix[g.edgeMatrix[i][1]][g.edgeMatrix[i][0]]=1;
}
}
public static void CreateConMatrix(Graph g){
g.conMatrix=new int[g.numV][g.numE];
for(int i=0;i<g.numV;i++){
for(int j=0;j<g.numE;j++){
g.conMatrix[i][j]=0;
}
}
for(int i=0;i<g.edgeMatrix.length;i++){
//System.out.println("i " + i + " " + g.edgeMatrix.length);
//System.out.println("g.edgeMatrix[i][0] " + g.edgeMatrix[i][0]);
//System.out.println("g.edgeMatrix[i][1] " + g.edgeMatrix[i][1]);
g.conMatrix[g.edgeMatrix[i][0]-1][i]=1;
g.conMatrix[g.edgeMatrix[i][1]-1][i]=1;
}
}
public static int Connection(Graph g1){
//connected graph should have no 0-element in adjMat3
//after numV-1 iteration of the loop below.
int ret=1;
Tensor adjMat = Tensor.Matrix2Tensor(g1.adjMatrix);
Tensor adjMat2 = Tensor.Matrix2Tensor(g1.adjMatrix);
Tensor adjMat3 = Tensor.Matrix2Tensor(g1.adjMatrix);
for(int i=0;i<g1.numV-1;i++){
adjMat2 = Tensor.MatrixProductTensor(adjMat2,adjMat);
adjMat3 = Tensor.SumTensor(adjMat3,adjMat2);
}
//int numZeroelem = CntZeroElem(adjMat3);
int numZeroelem = CntZeroElemWithoutDiag(adjMat3);
if(numZeroelem>0){
ret=0;
}
g1.connectionMatrix = adjMat3;
return ret;
}public static int ConnectionDirected(Graph g1){
//connected graph should have no 0-element in adjMat3
//after numV-1 iteration of the loop below.
int ret=1;
Tensor adjDirectedMat = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
Tensor adjDirectedMat2 = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
Tensor adjDirectedMat3 = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
for(int i=0;i<g1.numV-1;i++){
adjDirectedMat2 = Tensor.MatrixProductTensor(adjDirectedMat2,adjDirectedMat);
adjDirectedMat3 = Tensor.SumTensor(adjDirectedMat3,adjDirectedMat2);
}
int numZeroelem = CntZeroElemWithoutDiag(adjDirectedMat3);
if(numZeroelem>0){
ret=0;
}
g1.connectionMatrixDirected = adjDirectedMat3;
return ret;
}public static int ConnectionUnilateralDirected(Graph g1){
//connected graph should have no 0-element in adjMat3
//after numV-1 iteration of the loop below.
int ret=1;
Tensor adjDirectedMat = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
Tensor adjDirectedMat2 = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
Tensor adjDirectedMat3 = Tensor.Matrix2Tensor(g1.adjDirectedMatrix);
for(int i=0;i<g1.numV-1;i++){
adjDirectedMat2 = Tensor.MatrixProductTensor(adjDirectedMat2,adjDirectedMat);
adjDirectedMat3 = Tensor.SumTensor(adjDirectedMat3,adjDirectedMat2);
}
int numZeroelem = CntZeroElemWithoutDiagUnilateral(adjDirectedMat3);
if(numZeroelem>0){
ret=0;
}
g1.connectionMatrixDirected = adjDirectedMat3;
return ret;
}
public static Graph AddEdge(Graph g, int[] e){
int[][] tmp = new int[g.edgeMatrix.length+1][3];
for(int i=0;i<g.edgeMatrix.length;i++){
tmp[i][0]=g.edgeMatrix[i][0];
tmp[i][1]=g.edgeMatrix[i][1];
if(e.length<3){
tmp[i][2]=1;
}else{
tmp[i][2]=g.edgeMatrix[i][2];
}
}
tmp[tmp.length-1][0]=e[0];
tmp[tmp.length-1][1]=e[1];
if(e.length<3){
tmp[tmp.length-1][2]=1;
}else{
tmp[tmp.length-1][2]=e[2];
}
Graph ret = new Graph(tmp);
int[] vert = new int[g.numV];
for(int i=0;i<g.numV;i++){
vert[i]=g.vertex[i][0];
}
;
AddVertex(ret,vert);
CreateDataGraph(ret);
return ret;
}
public static void AddVertex(Graph g, int[] v){
int[][] tmp = new int[g.numV+1][4];
for(int i=0;i<v.length;i++){
boolean flag=true;
for(int j=0;j<g.numV;j++){
if(v[i]==g.vertex[j][0]){
flag=false;
break;
}
}
if(flag){
int[][] tmpv = new int[g.numV+1][4];
for(int j=0;j<g.numV;j++){
tmpv[j][0]=g.vertex[j][0];
tmpv[j][1]=g.vertex[j][1];
tmpv[j][2]=g.vertex[j][2];
tmpv[j][3]=g.vertex[j][3];
}
tmpv[tmpv.length-1][0]=v[i];
tmpv[tmpv.length-1][1]=0;
tmpv[tmpv.length-1][2]=0;
tmpv[tmpv.length-1][3]=0;
g.vertex=new int[tmpv.length][4];
for(int j=0;j<tmpv.length;j++){
g.vertex[j][0]=tmpv[j][0];
g.vertex[j][1]=tmpv[j][1];
g.vertex[j][2]=tmpv[j][2];
g.vertex[j][3]=tmpv[j][3];
}
g.numV++;
}
}
g.numV=g.vertex.length;
}
public static void CreateDataGraph(Graph g){
CountVandDeg(g);
CreateAdjMatrix(g);
CreateDirectedAdjMatrix(g);
CreateConMatrix(g);
Connection(g);
ConnectionDirected(g);
}public static void CreateDataGraph2(Graph g){
//CountVandDeg(g);
CreateAdjMatrix(g);
CreateDirectedAdjMatrix(g);
CreateConMatrix(g);
Connection(g);
ConnectionDirected(g);
}
public static int WelchPowell(Graph g){
int ret=0;
int[][]p = g.vertex;
//bublsort
//boolean flag=true;
boolean sameflag=false;
for(int i=p.length-1;i>=0;i--){
for(int j=1;j<=i;j++){
if(p[j-1][1]==p[j][1]){
sameflag=true;
//ret = 0;
//return ret;
}
if(p[j-1][1]<p[j][1]){
int[] tmp = {p[j-1][0],p[j-1][1]};
p[j-1][0]=p[j][0];
p[j-1][1]=p[j][1];
p[j][0]=tmp[0];
p[j][1]=tmp[1];
//ret+=1;
//if(flag){
//flag=false;
//}else{
//flag=true;
//}
}
}
}
boolean[] colored = new boolean[p.length];
for(int i=0;i<colored.length;i++){
if(i==0){
colored[i]=true;
}else{
colored[i]=false;
}
}
int colorcnt=1;
int checkid=p[0][0];
int colorednum=1;
while(colorednum<p.length){
for(int i=0;i<p.length;i++){
if(!colored[i]){
if(g.adjMatrix[p[i][0]-1][checkid-1]==0){
colored[i]=true;
colorednum++;
}else{
//colorcnt++;
//break;
}
}
}
for(int i=0;i<colored.length;i++){
if(!colored[i]){
checkid = p[i][0];
colored[i]=true;
colorednum++;
colorcnt++;
break;
}
}
}
return colorcnt;
}
public static Graph CreateVertexGraph(int[] v){
int[][] emptyE ={};
Graph eGraph = new Graph(emptyE);
CreateDataGraph(eGraph);
//int[] vert ={1,2,3,4};
AddVertex(eGraph,v);
//PrintGraphE(eGraph,"\t","\n");
CreateDataGraph2(eGraph);
//PrintGraphE(eGraph,"\t","\n");
return eGraph;
}
public static Graph MinimumSpanningTree(Graph g,int[][] e){//arg is Graph without edge
int[] v = new int[g.vertex.length];
for(int i=0;i<v.length;i++){
v[i]=g.vertex[i][0];
}
int tmpmin=0;
for(int i=0;i<e.length;i++){
if(tmpmin<e[i][2]){
tmpmin=e[i][2];
}
}
int[] addede = new int[e.length];
for(int i=0;i<addede.length;i++){
addede[i]=0;
}
for(int i=0;i<g.numV-1;i++){
int tobeadded=0;
int tmptmpmin=tmpmin;
for(int j=0;j<e.length;j++){
if(addede[j]==0){
for(int k=0;k<g.connectionMatrix.index.length;k++){
if((g.connectionMatrix.index[k][0]==e[j][0]-1 && g.connectionMatrix.index[k][1]==e[j][1]-1) ||
(g.connectionMatrix.index[k][0]==e[j][1]-1 && g.connectionMatrix.index[k][1]==e[j][0]-1)){
if(e[j][2]<tmptmpmin){
tobeadded=j;
addede[j]=1;
tmptmpmin=e[j][2];
}
}
}
}
}
int[] ea = {e[tobeadded][0],e[tobeadded][1],e[tobeadded][2]};
g = AddEdge(g,ea);
CreateDataGraph2(g);
}
return g;
}
// Strong connection check for directed graph and Connection check for undirected graph
// and weak connection check for directed graph
// is to check non-zero ij-elements (i not equals j)
// On the other hand unilateral connection check for directed graph
// is to check ij or ji-element is more than zero
// for all ij pairs (i not eqeauls j)
public static int CntZeroElem(Tensor t){
int ret=0;
for(int i=0;i<t.data.length;i++){
if(t.data[i]==0){
ret++;
}
}
return ret;
}
public static int CntZeroElemWithoutDiag(Tensor t){
int ret=0;
for(int i=0;i<t.data.length;i++){
if(t.index[i][0]!=t.index[i][1]){
if(t.data[i]==0){
ret++;
}
}
}
return ret;
}
public static int CntZeroElemWithoutDiagUnilateral(Tensor t){
int ret=0;
for(int i=0;i<t.dimension[0];i++){
for(int j=0;j<t.dimension[0];j++){
if(i!=j){
int[] ij ={i,j};
int[] ji ={j,i};
int ijID = Tensor.ChoiceElem(t,ij);
int jiID = Tensor.ChoiceElem(t,ji);
if(t.data[ijID]+t.data[jiID]==0){
ret++;
}
}
}
}
return ret;
}
}
