Code covered by the BSD License

# causal polytree algorithm 2004

### Guangdi Li (view profile)

A polytree algorithm published by M. Ouerd, B. John Oommen, Stan Matwin.

Querd_PolytreeRecover( CIMatric,UPRMatric,ArtSet )
```function [ UPRMatric,IAPS,CINumber] = Querd_PolytreeRecover( CIMatric,UPRMatric,ArtSet )
% this function is the implementation of the algorithm in paper:
% M. Ouerd, B. John Oommen, Stan Matwin, A formal approach to using data distributions for building causal polytree structures. Information Sciences,Volume 168, Issues 1–4, 3 December 2004, Pages 111–132
% ArtSet is the predefined set of articulation point.

CINumber = 0;
Dim = size( UPRMatric,2 );
VisitedNodes = zeros( 1,Dim );

% Filter the leaves out of ArtSet
for p = 1:Dim
if ArtSet( p )==1 && IsLeaf( UPRMatric,p )==1
ArtSet( p )=0;
end
end
%ArtSet
%go to main part of algorithm
for p = 1:Dim
if VisitedNodes( p )==0 && ArtSet( p )==1
[ UPRMatric,VisitedNodes,CINumber] = Processing( p,CIMatric,UPRMatric,VisitedNodes,CINumber );
end
end

IAPS = SearchPolytreeIAPS( UPRMatric );

end

function [ UPRMatric,VisitedNodes,CINumber] = Processing( CurrentNode,CIMatric,UPRMatric,VisitedNodes,CINumber )
Dim = size( UPRMatric,2 );
% CurrentNode is not a leaf
if VisitedNodes( CurrentNode ) == 0 && IsLeaf( UPRMatric,CurrentNode ) == 0
% CINumber
[ UPRMatric,CINumber] = IndepOrient( CurrentNode,CIMatric,UPRMatric,CINumber );
%CINumber
%CurrentNode
VisitedNodes( CurrentNode ) =1;
for p = 1:Dim
if UPRMatric( CurrentNode,p ) == 1 && UPRMatric( p,CurrentNode ) == 0
[ UPRMatric,VisitedNodes,CINumber] = Processing( p,CIMatric,UPRMatric,VisitedNodes,CINumber );
end
end
end
end

function  [ UPRMatric,CINumber] = IndepOrient( CurrentNode,CIMatric,UPRMatric,CINumber )
Dim = size( UPRMatric,2 );
for p = 1:Dim-1 % every distinct N1 and N2 in ConList
if UPRMatric( CurrentNode,p ) == 1 || UPRMatric( p,CurrentNode ) == 1
for q = (p+1):Dim
if  UPRMatric( CurrentNode,q )==1 || UPRMatric( q,CurrentNode )==1
CINumber = CINumber + 1;
%  p
%  q
if CIMatric( p,q ) == 1
UPRMatric( CurrentNode,p ) = 0;
UPRMatric( p,CurrentNode ) = 1;
UPRMatric( CurrentNode,q ) = 0;
UPRMatric( q,CurrentNode ) = 1;
end
end
end
end
end

% Every distinct p and q in ConList(X), orient p->A- q into p->A->q
p=1;
while p <= Dim
if UPRMatric( CurrentNode,p ) == 0 && UPRMatric( p,CurrentNode )==1
break;
end
p = p + 1;
end
if p<= Dim
for q = 1:Dim
if UPRMatric( CurrentNode,q ) == 1 && UPRMatric( q,CurrentNode )==1
UPRMatric( q,CurrentNode )= 0 ;
end
end
end

end
```