root/BH13SPARQLBuilder/src/org/biohackathon/SPARQLBuilder/OWL/OWLClassGraph.java @ 72

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.biohackathon.SPARQLBuilder.OWL;

/**
 *
 * @author atsuko
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class OWLClassGraph extends LabeledMultiDigraph{
    String startClass;
    String endClass;
    int nsteps;
    int limit;
    int th;
    double concut;
    double divcut;
        
    public class LinkAndPath{
        String originalClassURI; // originalClasssURI -classLink.propertyURI-> classLink.linkedClassURL
        ClassLink classLink;
        List<ClassLink> path;
        boolean converge;
        
        public LinkAndPath(ClassLink classLink, List<ClassLink> path){
           this.classLink = classLink;
           this.path = path;
           this.converge = false;
        }
        
        public LinkAndPath(ClassLink classLink, List<ClassLink> path, String orinalClassURI, boolean converge){
           this.classLink = classLink;
           this.path = path;
           this.originalClassURI = originalClassURI;
           this.converge = converge;
        }
    }
    
    public OWLClassGraph(String startClass, String endClass){
        super();
        this.startClass = startClass;
        addNode(startClass);
        this.endClass = endClass;
        addNode(endClass);
        nsteps = 3;
        limit = 1000;
        th = 0;
        concut = 2.0;
        divcut = - 2.0;
    }
    
    /*
    public void generateGraph(List<List<ClassLink>> paths){
        ListIterator<List<ClassLink>> pit = paths.listIterator();
        while( pit.hasNext() ){
            List<ClassLink> cls = pit.next();
            String start = startClass;
            ListIterator<ClassLink> cit = cls.listIterator();
            while ( cit.hasNext() ){
                // KOKO
            }
        }
    }
   */
    
    public Path[] getPaths(OWLQueryBuilderImpl qb, int mode, boolean countLink){
        List<List<ClassLink>> paths = null;
        if ( mode <= 1){
            paths = searchPaths(qb, mode, countLink);
        }else if ( mode == 2 ){
            paths = searchPathsWithCut(qb);        
        }else{
            System.err.println("Mode is not correct");
            return null;
        }
        Path[] patharray = new Path[paths.size()];
        ListIterator<List<ClassLink>> pit = paths.listIterator();
        int i = 0;
        while ( pit.hasNext() ){
            patharray[i] = new Path();
            patharray[i].setStartClass(startClass);
            List<ClassLink> path = pit.next();
            patharray[i].setClassLinks(path);
            ListIterator<ClassLink> cit = path.listIterator();
            int min = Integer.MAX_VALUE;
            while ( cit.hasNext() ){
                ClassLink cl = cit.next();
                if ( cl.getNumOfLinks() < min ){
                    min = cl.getNumOfLinks();
                }
            }
            patharray[i].setWidth(min);
            i++;
        }
        return patharray;
    }
        
    private List<List<ClassLink>> searchPaths(OWLQueryBuilderImpl qb, int mode, boolean countLinks){
        List<List<ClassLink>> paths = new ArrayList<>();
        ClassLink crrLink = new ClassLink(null,startClass,Direction.both,0,0,0,0,0);
        List<LinkAndPath> lp = new LinkedList<>();
        lp.add(new LinkAndPath(crrLink, new LinkedList<ClassLink>()));
        try{
          for ( int i = 0; i < nsteps; i++ ){
              ListIterator<LinkAndPath> lit = lp.listIterator();
              List<LinkAndPath> nextlp = new LinkedList<>();
              while ( lit.hasNext() ){
                  LinkAndPath crrlp = lit.next();
                  ClassLink[] classLinks = null;
                  // Mode
                  if ( mode == 0 ){
                      classLinks = qb.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, countLinks);
                  }else if ( mode == 1 ){
                      classLinks = qb.getNextClassViaInstanceLink(null, crrlp.classLink.getLinkedClassURI(), limit); 
                  }else{ System.err.println("Mode is not correct."); }
                  for ( int j = 0 ; j < classLinks.length; j++ ){
                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
                      crrpath.add(classLinks[j]);
                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
                          paths.add(new LinkedList<>(crrpath));
                          continue;
                      }
                      if ( countLinks == true && classLinks[j].getNumOfLinks() <= th){
                          continue;
                      }
                      nextlp.add(new LinkAndPath(classLinks[j],crrpath));
                  }
              }
              lp = nextlp;
          }
        }catch(Exception e){ 
            System.err.println(e);
        }
        return paths;  
    }
    
    private List<List<ClassLink>> searchPathsWithCut(OWLQueryBuilderImpl qb){
        List<List<ClassLink>> paths = new ArrayList<>();
        ClassLink crrLink = new ClassLink(null,startClass,Direction.both,0,0,0,0,0);
        List<LinkAndPath> lp = new LinkedList<>();
        lp.add(new LinkAndPath(crrLink, new LinkedList<ClassLink>()));
        try{
          for ( int i = 0; i < nsteps; i++ ){
              ListIterator<LinkAndPath> lit = lp.listIterator();
              List<LinkAndPath> nextlp = new LinkedList<>();
              while ( lit.hasNext() ){
                  LinkAndPath crrlp = lit.next();
                  ClassLink[] classLinks = null;
                  classLinks = qb.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, true); 
                  for ( int j = 0 ; j < classLinks.length; j++ ){
                      if ( classLinks[j].getNumOfLinks() == 0 ){ continue; }
                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
                      crrpath.add(classLinks[j]);
                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
                          paths.add(new LinkedList<>(crrpath));
                          continue;
                      }
                      if (classLinks[j].getNumOfLinks() <= th ){
                          continue; //cut by the number of instances
                      }
                      // Divergence & Convergence Decision
                      boolean con = false;
                      boolean div = false;
                      if ( decideConvergence(classLinks[j]) ){ // convergence
                          con = true;
                      }
                      if ( decideDivergence(classLinks[j]) ){ // divergence
                          div = true;
                      }
                      if ( crrlp.converge == true && div == true ){ // converge & 縲€diverge
                          continue; // cut by the differences of entropies
                      }
                      // crr & next are the same arcs
                      if ( crrlp.classLink.getPropertyURI().equals(classLinks[j].getPropertyURI()) &&
                           crrlp.classLink.getDirection() != classLinks[j].getDirection() &&
                           crrlp.originalClassURI.equals( classLinks[j].getLinkedClassURI()) ){
                          continue;
                      }
                      
                      nextlp.add(new LinkAndPath(classLinks[j], crrpath, crrlp.classLink.getLinkedClassURI(), con));
                  }
              }
              lp = nextlp;
          }
        }catch(Exception e){ 
            System.err.println(e);
        }
        return paths;  
    }
    
    private boolean decideConvergence(ClassLink classLink){
        double con = getValueForConvergence(classLink.getNumOfOriginInstances(), 
                                              classLink.getNumOfLinkedInstances(),
                                              classLink.getNumOfLinks());
        if ( con > concut  ){
            return true;
        }
        return false;
    }
    
    private boolean decideDivergence(ClassLink classLink){
        double con = getValueForConvergence(classLink.getNumOfOriginInstances(), 
                                              classLink.getNumOfLinkedInstances(),
                                              classLink.getNumOfLinks());
        if ( con < divcut  ){
            return true;
        }
        return false;
    }

    private double getValueForConvergence(int numOfOriginInstances, int numOfLinkedInstances, int numOfLinks){
        //return (double) numOfLinks / (double) numOfLinkedInstances ;
        // Convergence plus, Divergence minus
        return Math.log((double)numOfOriginInstances) - Math.log((double)numOfLinkedInstances); 
    }
}