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

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

/**
 *
 * @author atsuko
 */
import java.util.*;
//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;
    int prunecut;
        
    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 originalClassURI){
           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;
        prunecut = 100;
    }

    public Path[] getPaths(RDFSchemaAnalyzer rdfsa, boolean countLink){
        List<List<ClassLink>> paths = null;
        paths = searchPaths(rdfsa, countLink);
        NavigableSet<Path> sortedpath = new TreeSet<Path>();
        ListIterator<List<ClassLink>> pit = paths.listIterator();
        int j = 0;
        while ( pit.hasNext() ){
            Path path = new Path();
            path.setStartClass(startClass);
            List<ClassLink> crrpath = pit.next();
            path.setClassLinks(crrpath);
            ListIterator<ClassLink> cit = crrpath.listIterator();
            int min = Integer.MAX_VALUE;
            while ( cit.hasNext() ){
                ClassLink cl = cit.next();
                if ( cl.getNumOfLinks() < min ){
                    min = cl.getNumOfLinks();
                }
            }
            path.setWidth(min);
            sortedpath.add(path);
            j++;
        }
        Path[] patharray = new Path[paths.size()];
        Iterator<Path> pait = sortedpath.descendingIterator();
        int i = 0;
        while ( pait.hasNext() ){
            patharray[i] = pait.next();
            i++;
        }
        return patharray;
    }
        
    private List<List<ClassLink>> searchPaths(RDFSchemaAnalyzer rdfsa, boolean countLinks){
        List<List<ClassLink>> paths = new ArrayList<>();
        List<LinkAndPath> lp = new LinkedList<>();
        lp.add(new LinkAndPath(new ClassLink("",startClass,null,Direction.both,0,0,0,0,0,false,false), 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 = rdfsa.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, countLinks);
                  for ( int j = 0 ; j < classLinks.length; j++ ){
                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
                      crrpath.add(classLinks[j]);
                      if ( classLinks[j].getLinkedClassURI() == null ){ continue; }
                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
                          paths.add(new LinkedList<>(crrpath));
                          continue;
                      }
                      if ( countLinks == true && classLinks[j].getNumOfLinks() <= th){
                          continue;
                      }
                      if ( i >= 2 ){
                          if ( crrlp.classLink.getPropertyURI().equals(classLinks[j].getPropertyURI()) &&
                           crrlp.classLink.getDirection() != classLinks[j].getDirection() &&
                           crrlp.originalClassURI.equals( classLinks[j].getLinkedClassURI()) ){
                              //System.out.println("P1");
                              continue;
                          }
                          if ( checkPruning(crrlp.classLink, classLinks[j]) ){
                              //System.out.println("P2");
                              continue;
                          }
                      }
                      nextlp.add(new LinkAndPath(classLinks[j], crrpath, crrlp.classLink.getLinkedClassURI()));
                  }
              }
              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 checkPruning(ClassLink classLink1, ClassLink classLink2){
          // true -> prune link2, false -> add link2
          int noi1 = classLink1.getNumOfOriginInstances();
          int nli1 = classLink1.getNumOfLinkedInstances();
          int noi2 = classLink2.getNumOfOriginInstances();
          int nli2 = classLink2.getNumOfLinkedInstances();
          if ( noi1 == 0 || nli1 == 0 || noi2 == 0 || nli2 == 0 ){
              return true;
          }
          return ( noi1 / nli1 > prunecut && nli2 / noi2 > prunecut );
      }
    
/*    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); 
    }
    */
    
}