Code covered by the BSD License  

Highlights from
causal polytree algorithm 2004

causal polytree algorithm 2004

by

 

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

Contact us