チェンジセット 221 : SPARQLBuilderWWW/src/java/org/biohackathon/SPARQLBuilder/OWL/OWLClassGraph.java

更新日時:

2014/12/19 18:01:25 (10 年 前)

更新者:

atsuko

ログメッセージ:

パス探索アルゴリズムを大幅変更

ファイル:

• SPARQLBuilderWWW/src/java/org/biohackathon/SPARQLBuilder/OWL/OWLClassGraph.java (変更) (10 diff)

SPARQLBuilderWWW/src/java/org/biohackathon/SPARQLBuilder/OWL/OWLClassGraph.java

@@ -12 +12 @@
 
 public class OWLClassGraph extends LabeledMultiDigraph{
-    String startClass;
-    String endClass;
-    int nsteps;
-    int limit;
-    int th;
-    int prunecut;
+    //String startClass;
+    //String endClass;
+    int nsteps = 5;
+    int limit = 100;
+    int th = 1;
+    List<String> nodeType;
+    ArrayList<HashSet<Integer>> connectionTable;
 
     public class LinkAndPath{
@@ -24 +25 @@
         List<ClassLink> path;
         Set<String> classURIs; // apearing class URIs in the path
-        //boolean converge;
+        
         
         public LinkAndPath(ClassLink classLink, List<ClassLink> path){
            this.classLink = classLink;
            this.path = path;
-           //this.converge = false;
         }
         
@@ -36 +36 @@
            this.path = path;
            this.originalClassURI = originalClassURI;
-           //this.converge = converge;
         }
 
@@ -44 +43 @@
            this.originalClassURI = originalClassURI;
            this.classURIs = classURIs;
-           //this.converge = converge;
-        }
-    }
-
+        }
+    }
+
+/*
     public OWLClassGraph(String startClass, String endClass){
         super();
@@ -58 +57 @@
         nsteps = 3;
         limit = 1000;
-        prunecut = 100;
         th = 5;
     }
-
+*/
+
+/*    
     public OWLClassGraph(String startClass, String endClass, int th){
         super();
@@ -74 +74 @@
         nsteps = 3;
         limit = 1000;
-        prunecut = 100;
-    }
-
-    public Path[] getPaths(RDFSchemaAnalyzer rdfsa, boolean countLink){
+    }
+*/    
+
+    public OWLClassGraph(RDFSchemaAnalyzer rdfsa){
+        super();
+        nodeType = new LinkedList<String>();
+        setClassGraph(rdfsa);
+        connectionTable = createConnectionTable();
+    }
+    
+    public int getNumberOfEdge(String url){
+        Integer node = labelednodes.get(url);
+        if (node == null){
+            return 0;
+        }
+        return adjlist.get(node).size();
+    }
+    
+    public Path[] getPaths(String startClass, String endClass){
+        List<List<ClassLink>> paths = searchPaths(startClass, endClass);
+
+        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();
+                }
+            }
+            // using length of path
+            int rankwidth = (int) ( ( min * nsteps )/ crrpath.size() );
+            path.setWidth(rankwidth);
+            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;
+    }
+    
+    public HashSet<Integer> getConnectionList(Integer node){
+        return connectionTable.get(node);
+    }
+    
+    public Path[] getPaths_old(RDFSchemaAnalyzer rdfsa, boolean countLink, String startClass, String endClass){
         List<List<ClassLink>> paths = null;
-        //paths = searchPaths(rdfsa, countLink);
-        paths = searchPathsbyVisitingNodes(rdfsa, countLink);
+        paths = searchPathsbyVisitingNodes(rdfsa, countLink, startClass, endClass);
         NavigableSet<Path> sortedpath = new TreeSet<Path>();
         ListIterator<List<ClassLink>> pit = paths.listIterator();
@@ -110 +163 @@
         return patharray;
     }
-    
+
+    private List<List<ClassLink>> searchPaths(String startClass, String endClass){
+
+        List<List<ClassLink>> paths = new ArrayList<>();
+        List<List<Integer>> simplePaths = new LinkedList<>();
+        Integer snode = labelednodes.get(startClass);
+        Integer enode = labelednodes.get(endClass);
+        List<List<Integer>> lp = new LinkedList<>();
+        List<Integer> ini = new LinkedList<Integer>(); // initial path
+        ini.add(snode);
+        lp.add(ini);
+        for (int i = 0; i < nsteps; i++ ){
+            ListIterator<List<Integer>> lit = lp.listIterator();
+            List<List<Integer>> nextlp = new LinkedList<>();
+            while ( lit.hasNext() ){ 
+                List<Integer> crrpath = lit.next();
+                Integer crrnode = crrpath.get(crrpath.size()-1);
+                Set<Integer> nexts = gadjlist.get(crrnode).keySet();
+                Iterator<Integer> nit = nexts.iterator();
+                while( nit.hasNext() ){
+                    Integer nextnode = nit.next();
+                    if ( crrpath.contains(nextnode) ){ continue; }
+                    List<Integer> nextpath = new LinkedList<Integer>(crrpath); // copy
+                    nextpath.add(nextnode);
+                    if ( nextnode.equals(enode) ){
+                        simplePaths.add(nextpath);
+                        continue;
+                    }
+                    nextlp.add(nextpath);
+                }
+            }
+            lp = nextlp;
+        }
+        
+        ListIterator<List<Integer>> pit = simplePaths.listIterator();
+        while( pit.hasNext()){
+            List<Integer> spath = pit.next();
+            List<List<ClassLink>> convertedPaths = convertSimplePathToPaths(spath);
+            paths.addAll(convertedPaths);
+        }
+        return paths;
+    }
+    
+    private List<List<ClassLink>> convertSimplePathToPaths(List<Integer> simplePath){
+        List<List<ClassLink>> paths = new LinkedList<List<ClassLink>>();
+        //List<List<LabeledEdge>> multiedges = new LinkedList<List<LabeledEdge>>();
+        ListIterator<Integer> spit = simplePath.listIterator();
+        Integer start = spit.next();
+        Integer end = spit.next();
+        List<LabeledEdge> edges = gadjlist.get(start).get(end);
+        ListIterator<LabeledEdge> eit = edges.listIterator();
+        while ( eit.hasNext() ){
+            List<ClassLink> cl = new LinkedList<ClassLink>();
+            cl.add((ClassLink)eit.next().getLabel());
+            paths.add(cl);
+        }
+        start = end;
+        while( spit.hasNext() ){
+            end = spit.next();
+            // start-end
+            edges = gadjlist.get(start).get(end);
+            List<List<ClassLink>> tmppaths = new LinkedList<List<ClassLink>>();            
+            // current path
+            ListIterator<List<ClassLink>> pit = paths.listIterator();
+            while ( pit.hasNext() ){
+                List<ClassLink> basepath = pit.next();
+                eit = edges.listIterator();
+                while ( eit.hasNext() ){
+                    ClassLink cl = (ClassLink) eit.next().label;
+                    List<ClassLink> addedpath = new LinkedList<ClassLink>(basepath);
+                    addedpath.add(cl);
+                    tmppaths.add(addedpath);
+                }
+            }
+            paths = tmppaths;
+            start = end;
+        }        
+        return paths;
+    }
+    
+    /*
     private List<List<ClassLink>> searchPaths(RDFSchemaAnalyzer rdfsa, boolean countLinks){
         List<List<ClassLink>> paths = new ArrayList<>();
@@ -150 +283 @@
         return paths;  
     }
-
-    private List<List<ClassLink>> searchPathsbyVisitingNodes(RDFSchemaAnalyzer rdfsa, boolean countLinks){
+    */
+    
+    private List<List<ClassLink>> searchPathsbyVisitingNodes(RDFSchemaAnalyzer rdfsa, boolean countLinks,
+            String startClass, String endClass){
         List<List<ClassLink>> paths = new ArrayList<>();
         List<LinkAndPath> lp = new LinkedList<>();
@@ -193 +328 @@
         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); 
-    }
-    */
-      
-   public void setWholeGraph(RDFSchemaAnalyzer rdfsa){
+              
+   private void setClassGraph(RDFSchemaAnalyzer rdfsa){
        // setNodes
        SClass[] classes = null;
@@ -303 +339 @@
        for (int i = 0 ; i < classes.length; i++){
            addNode(classes[i].getClassURI());
+           nodeType.add("class");
        }
        // setEdges
-       for (int i = 0 ; i < classes.length; i++){
+       for (int i = 0 ; i < classes.length; i++ ){
            try{
                ClassLink[] classLinks = rdfsa.getNextClass(null, classes[i].getClassURI(), limit, true);
                for (int j = 0 ; j < classLinks.length; j++){
-                   addEdge(i, labelednodes.get(classLinks[j].getLinkedClassURI()),
-                           classLinks[j].getPropertyURI(),
-                           classLinks[j].getDirection(),
-                           classLinks[j].getNumOfLinkedInstances());
+                   Integer n = labelednodes.get(classLinks[j].getLinkedClassURI());
+                   if ( n != null ){
+                       addEdge(i, n, classLinks[j]);
+                   }else{
+                       n = labelednodes.get(classLinks[j].getLinkedLiteralDatatypeURI());
+                       if ( n == null ){
+                           addNode(classLinks[j].getLinkedLiteralDatatypeURI());
+                           n = nodeType.size();
+                           nodeType.add("literal");
+                       }
+                       addEdge(i, n, classLinks[j]);
+                       /*
+                       ClassLink rev = new ClassLink( classLinks[j].getPropertyURI(),
+                               //classLinks[j].getLinkedClassURI(),
+                               classes[i].getClassURI(),
+                               classLinks[j].getLinkedLiteralDatatypeURI(),
+                               classLinks[j].getDirection(), classLinks[j].getNumOfLinks(), 
+                               classLinks[j].getNumOfOriginInstances(), classLinks[j].getNumOfLinkedInstances(),
+                               classLinks[j].getNumOfOriginClassInstances(), classLinks[j].getNumOfLinkedClassInstances(),
+                               classLinks[j].isDomainClassLimitedQ(), classLinks[j].isRangeClassLimitedQ() );
+                       rev.setDirection(Direction.reverse);
+                       addEdge(n, i, rev);
+                               */
+                   }
                }
            }catch(Exception e){
                System.err.println(e);
            }
-       } 
+       }       
    }
    
-   /*
-   public Path[] getPathsByWholeGraph(RDFSchemaAnalyzer rdfsa){
-        setWholeGraph(rdfsa);
-        List<List<ClassLink>> paths = null;
-        //paths = searchPaths(rdfsa, countLink);
-        paths = searchPathsbyVisitingNodes(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 ArrayList<HashSet<Integer>> createConnectionTable(){
+       ArrayList<HashSet<Integer>> ct = new ArrayList<HashSet<Integer>>();
+       for (int i = 0; i < labels.size(); i++ ){ // each node
+           HashSet<Integer> cl = createConnectionList(i);
+           ct.add(cl);
+       }
+       return ct;
+   }
+   
+   private HashSet<Integer> createConnectionList(Integer node){
+       HashSet<Integer> cl = new HashSet<Integer>();
+       HashSet<Integer> crrnodes = new HashSet<Integer>();
+       crrnodes.add(node);
+       cl.add(node);
+       for ( int i = 0 ; i < nsteps; i++ ){
+           Set<Integer> nextnodes = new HashSet<Integer>();
+           Iterator<Integer> cit = crrnodes.iterator();
+           while ( cit.hasNext() ){
+               Integer crr = cit.next();
+               Set<Integer> nexts = gadjlist.get(crr).keySet();
+               Iterator<Integer> nit = nexts.iterator();
+               while ( nit.hasNext() ){
+                   Integer next = nit.next();
+                   if ( !cl.contains(next) ){
+                       nextnodes.add(next);
+                       cl.add(next);
+                   }
+               }
+           }
+           crrnodes.clear();
+           crrnodes.addAll(nextnodes);
+       }
+       return cl;
+   }
 }