root/SPARQLBuilderWWW/src/java/org/biohackathon/SPARQLBuilder/OWL/OWLClassGraph.java @ 248

リビジョン 248, 22.1 KB (コミッタ: atsuko, 10 年 前)

枝刈り，クラス順序変更(数字は下に)
  • 属性 svn:mime-type の設定値 text/plain
行番号 
1/*
2 * To change this template, choose Tools | Templates
3 * and open the template in the editor.
4 */
5package org.biohackathon.SPARQLBuilder.OWL;
6
7/**
8 *
9 * @author atsuko
10 */
11import java.util.*;
12
13public class OWLClassGraph extends LabeledMultiDigraph{
14    //String startClass;
15    //String endClass;
16    int nsteps = 4;
17    int limit = 100;
18    int th = 1;
19    List<String> nodeType;
20    ArrayList<HashSet<Integer>> connectionTable;
21    String sparqlEndpoint;
22    Set<Integer> visited;
23    boolean askcheck;
24    List<Map<Integer, Integer>> edgeweight;
25    List<Integer> nodeweight;
26   
27    public class LinkAndPath{
28        String originalClassURI; // originalClasssURI -classLink.propertyURI-> classLink.linkedClassURL
29        ClassLink classLink;
30        List<ClassLink> path;
31        Set<String> classURIs; // apearing class URIs in the path
32       
33       
34        public LinkAndPath(ClassLink classLink, List<ClassLink> path){
35           this.classLink = classLink;
36           this.path = path;
37        }
38       
39        public LinkAndPath(ClassLink classLink, List<ClassLink> path, String originalClassURI){
40           this.classLink = classLink;
41           this.path = path;
42           this.originalClassURI = originalClassURI;
43        }
44
45        public LinkAndPath(ClassLink classLink, List<ClassLink> path, String originalClassURI, Set<String> classURIs){
46           this.classLink = classLink;
47           this.path = path;
48           this.originalClassURI = originalClassURI;
49           this.classURIs = classURIs;
50        }
51    }
52
53    public OWLClassGraph(){ // not used
54        super();
55        nodeType = new LinkedList<String>();
56    }
57       
58    public OWLClassGraph(RDFSchemaAnalyzer rdfsa){ // not used
59        super();
60        nodeType = new LinkedList<String>();
61    }
62   
63    public OWLClassGraph(RDFSchemaAnalyzer rdfsa, String sparqlEndpoint, String startClass, boolean askcheck){ // used
64        super();
65        nodeType = new LinkedList<String>();
66        this.askcheck = askcheck;
67        setPartClassGraph(rdfsa, sparqlEndpoint, startClass);
68    }
69
70    public int getNumberOfEdge(String url){
71        Integer node = labelednodes.get(url);
72        if (node == null){
73            return 0;
74        }
75        return adjlist.get(node).size();
76    }
77   
78    public boolean visitedNode(String classURI){
79        if ( visited.contains(labelednodes.get(classURI)) ){
80            return true;
81        }
82        return false;
83    }
84   
85    public Path[] getPaths(String startClass, String endClass){
86        List<List<ClassLink>> paths = searchPaths(startClass, endClass);
87
88        NavigableSet<Path> sortedpath = new TreeSet<Path>();
89        ListIterator<List<ClassLink>> pit = paths.listIterator();
90        int j = 0;
91        while ( pit.hasNext() ){
92            Path path = new Path();
93            path.setStartClass(startClass);
94            List<ClassLink> crrpath = pit.next();
95            path.setClassLinks(crrpath);
96            ListIterator<ClassLink> cit = crrpath.listIterator();
97            int min = Integer.MAX_VALUE;
98            while ( cit.hasNext() ){
99                ClassLink cl = cit.next();
100                if ( cl.getNumOfLinks() < min ){
101                    min = cl.getNumOfLinks();
102                }
103            }
104            // using length of path
105            int rankwidth = (int) ( ( min * nsteps )/ crrpath.size() );
106            path.setWidth(rankwidth);
107            sortedpath.add(path);
108            j++;
109        }
110        Path[] patharray = new Path[paths.size()];
111        Iterator<Path> pait = sortedpath.descendingIterator();
112        int i = 0;
113        while ( pait.hasNext() ){
114            patharray[i] = pait.next();
115            i++;
116        }
117        return patharray;
118    }
119   
120    public HashSet<Integer> getConnectionList(Integer node){
121        return connectionTable.get(node);
122    }
123
124    private List<List<ClassLink>> searchPaths(String startClass, String endClass){
125        //int asked = 0;
126        Map<String,Boolean> checkedpaths = new HashMap<String, Boolean>();
127        List<List<ClassLink>> paths = new ArrayList<>();
128        List<List<Integer>> simplePaths = new LinkedList<>();
129        Integer snode = labelednodes.get(startClass);
130        Integer enode = labelednodes.get(endClass);
131        List<List<Integer>> lp = new LinkedList<>();
132        List<Integer> ini = new LinkedList<Integer>(); // initial path
133        ini.add(snode);
134        lp.add(ini);
135        for (int i = 0; i < nsteps; i++ ){
136            ListIterator<List<Integer>> lit = lp.listIterator();
137            List<List<Integer>> nextlp = new LinkedList<>();
138            while ( lit.hasNext() ){
139                List<Integer> crrpath = lit.next();
140                Integer crrnode = crrpath.get(crrpath.size()-1);
141                Set<Integer> nexts = gadjlist.get(crrnode).keySet();
142                Iterator<Integer> nit = nexts.iterator();
143                while( nit.hasNext() ){
144                    Integer nextnode = nit.next();
145                    if ( crrpath.contains(nextnode) ){ continue; }
146                    List<Integer> nextpath = new LinkedList<Integer>(crrpath); // copy
147                    nextpath.add(nextnode);
148                    // tmp
149                    if ( i >= 1 ){
150                        int wn = nodeweight.get(crrnode);
151                        int in = edgeweight.get(crrpath.get(crrpath.size()-2)).get(crrnode);
152                        int out = edgeweight.get(nextnode).get(crrnode);
153                        if ( wn > in + out ){
154                            /*
155                            String key1 = nextnode.toString().concat("-").concat(crrpath.get(crrpath.size()-1).toString())
156                                .concat("-").concat(crrpath.get(crrpath.size()-2).toString());
157                            String key2 = crrpath.get(crrpath.size()-2).toString().concat("-").concat(crrpath.get(crrpath.size()-1).toString())
158                                .concat("-").concat(nextnode.toString());
159                            if ( checkedpaths.containsKey(key1) ){
160                                if ( checkedpaths.get(key1) == false ){
161                                   continue;
162                                }
163                            }else if ( checkedpaths.containsKey(key2) ){
164                                if ( checkedpaths.get(key2) == false ){
165                                   continue;
166                                }
167                            }else{                     
168                                boolean chk = EndpointAccess.check3SimplePathwithJoin(nextnode, crrpath.get(crrpath.size()-1),
169                                    crrpath.get(crrpath.size()-2), this, sparqlEndpoint);
170                                checkedpaths.put(key1, chk);
171                                if ( chk == false ){
172                                    continue;
173                                }
174                            }
175                            */
176                            continue;
177                        }
178                    }
179                    if ( nextnode.equals(enode) ){
180                        simplePaths.add(nextpath);
181                        continue;
182                    }
183                    nextlp.add(nextpath);
184                }
185            }
186            lp = nextlp;
187        }
188       
189        ListIterator<List<Integer>> pit = simplePaths.listIterator();
190        //int i = 0;
191        //int j = 0;
192        System.out.println("SPATH:");
193        System.out.println(simplePaths.size());
194        while( pit.hasNext()){
195            List<Integer> spath = pit.next();
196            List<List<ClassLink>> convertedPaths = convertSimplePathToPaths(spath);
197            paths.addAll(convertedPaths);
198        }
199        System.out.println("PATH:");
200        System.out.println(paths.size());
201        return paths;
202    }
203
204   
205    private List<List<ClassLink>> convertSimplePathToPaths(List<Integer> simplePath){
206        List<List<ClassLink>> paths = new LinkedList<List<ClassLink>>();
207        ListIterator<Integer> spit = simplePath.listIterator();
208        Integer start = spit.next();
209        String startClass = this.labels.get(start);
210        Integer end = spit.next();
211        List<LabeledEdge> edges = gadjlist.get(start).get(end);
212        ListIterator<LabeledEdge> eit = edges.listIterator();
213        while ( eit.hasNext() ){
214            List<ClassLink> cl = new LinkedList<ClassLink>();
215            cl.add((ClassLink)eit.next().getLabel());
216            paths.add(cl);
217        }
218        start = end;
219        while( spit.hasNext() ){
220            end = spit.next();
221            // start-end
222            edges = gadjlist.get(start).get(end);
223            List<List<ClassLink>> tmppaths = new LinkedList<List<ClassLink>>();           
224            // current path
225            ListIterator<List<ClassLink>> pit = paths.listIterator();
226            while ( pit.hasNext() ){
227                List<ClassLink> basepath = pit.next();
228                eit = edges.listIterator();
229                while ( eit.hasNext() ){
230                    ClassLink cl = (ClassLink) eit.next().label;
231                    List<ClassLink> addedpath = new LinkedList<ClassLink>(basepath);
232                    addedpath.add(cl);
233                    // check
234                    //if ( EndpointAccess.checkPath(startClass, addedpath, sparqlEndpoint) ){
235                        tmppaths.add(addedpath);
236                    //}
237                }
238            }
239            paths = tmppaths;
240            start = end;
241        }       
242        return paths;
243    }
244   
245    /*
246    private List<List<ClassLink>> searchPathsbyVisitingNodes(RDFSchemaAnalyzer rdfsa, boolean countLinks,
247            String startClass, String endClass){
248        List<List<ClassLink>> paths = new ArrayList<>();
249        List<LinkAndPath> lp = new LinkedList<>();
250        Set<String> urls = new HashSet<String>();
251        urls.add(startClass);
252        lp.add(new LinkAndPath(new ClassLink("",startClass,null,Direction.both,0,0,0,0,0,false,false),
253                                 new LinkedList<ClassLink>(), startClass, urls));
254        try{
255          for ( int i = 0; i < nsteps; i++ ){
256              ListIterator<LinkAndPath> lit = lp.listIterator();
257              List<LinkAndPath> nextlp = new LinkedList<>();
258              while ( lit.hasNext() ){
259                  LinkAndPath crrlp = lit.next();
260                  ClassLink[] classLinks = rdfsa.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, countLinks);
261                  // limit
262                  for ( int j = 0 ; j < classLinks.length; j++ ){
263                      if (crrlp.classURIs.contains(classLinks[j].getLinkedClassURI()) ){
264                          continue; // visited
265                      }
266                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
267                      crrpath.add(classLinks[j]);
268                      Set<String> crrurls = new HashSet<String>(crrlp.classURIs);
269                      crrurls.add(classLinks[j].getLinkedClassURI());
270                      if ( classLinks[j].getLinkedClassURI() == null ){ continue; }
271                      if ( classLinks[j].getNumOfLinks() <= th){
272                          continue;
273                      }
274                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
275                          paths.add(new LinkedList<>(crrpath));
276                          continue;
277                      }
278                      //crrlp.classURIs.add()
279                      nextlp.add(new LinkAndPath(classLinks[j], crrpath, crrlp.classLink.getLinkedClassURI(),crrurls));
280                  }
281              }
282              lp = nextlp;
283          }
284        }catch(Exception e){
285            System.err.println(e);
286        }
287        return paths; 
288    }
289             
290   private void setClassGraph(RDFSchemaAnalyzer rdfsa){
291       // setNodes
292       SClass[] classes = null;
293       try{
294           classes = rdfsa.getOWLClasses(null, null, null, true);
295       }catch(Exception e){
296           System.err.println(e); return;
297       }
298       for (int i = 0 ; i < classes.length; i++){
299           addNode(classes[i].getClassURI());
300           nodeType.add("class");
301       }
302       // setEdges
303       for (int i = 0 ; i < classes.length; i++ ){
304           try{
305               ClassLink[] classLinks = rdfsa.getNextClass(null, classes[i].getClassURI(), limit, true);
306               for (int j = 0 ; j < classLinks.length; j++){
307                   Integer n = labelednodes.get(classLinks[j].getLinkedClassURI());
308                   if ( n != null ){
309                       addEdge(i, n, classLinks[j]);
310                   }else{
311                       n = labelednodes.get(classLinks[j].getLinkedLiteralDatatypeURI());
312                       if ( n == null ){
313                           addNode(classLinks[j].getLinkedLiteralDatatypeURI());
314                           n = nodeType.size();
315                           nodeType.add("literal");
316                       }
317                       addEdge(i, n, classLinks[j]);
318                   }
319               }
320           }catch(Exception e){
321               System.err.println(e);
322           }
323       }       
324   }*/
325
326    public void setPartClassGraph(RDFSchemaAnalyzer rdfsa, String sparqlEndpoint, String startClass){
327        // set endpoint
328        this.sparqlEndpoint = sparqlEndpoint;
329       
330        visited = new HashSet<Integer>();
331        edgeweight = new LinkedList<Map<Integer,Integer>>();
332        nodeweight = new LinkedList<Integer>();
333        // setNodes for all classes
334        SClass[] classes = null;
335        try{
336           classes = rdfsa.getOWLClasses(null, null, null, true);
337        }catch(Exception e){
338           System.err.println(e); return;
339        }
340        for (int i = 0 ; i < classes.length; i++){
341           addNode(classes[i].getClassURI());
342           nodeType.add("class");
343           edgeweight.add(new HashMap<Integer,Integer>());
344           nodeweight.add(classes[i].getNumOfInstances());
345        }
346        // setEdges
347        //int nedge = 0;
348        Integer snode = labelednodes.get(startClass);
349        Set<Integer> nodes = new HashSet<Integer>();
350        nodes.add(snode);
351        visited.add(snode);
352        for (int i = 0 ; i < nsteps; i++ ){
353            Iterator<Integer> nit = nodes.iterator();
354            Set<Integer> nextnodes = new HashSet<Integer>();
355            while ( nit.hasNext() ){
356                Integer crr = nit.next();
357                try{
358                    ClassLink[] classLinks = rdfsa.getNextClass(null, labels.get(crr), limit, true);
359                    for (int j = 0 ; j < classLinks.length; j++){
360                        Integer nn = labelednodes.get(classLinks[j].getLinkedClassURI());
361                        if ( nn == null ){
362                            continue;
363                        }
364                        if ( !visited.contains(nn) ){
365                            nextnodes.add(nn);
366                        }
367                        addEdge(crr, nn, classLinks[j]);
368                        updateWeight(crr, nn, classLinks[j]);
369                    }
370                }catch(Exception e){
371                    e.printStackTrace();
372                }
373            }
374            nodes = nextnodes;
375            visited.addAll(nodes);
376        }
377    }
378   
379   private ArrayList<HashSet<Integer>> createConnectionTable(){ // not used
380       ArrayList<HashSet<Integer>> ct = new ArrayList<HashSet<Integer>>();
381       for (int i = 0; i < labels.size(); i++ ){ // each node
382           HashSet<Integer> cl = createConnectionList(i);
383           ct.add(cl);
384       }
385       return ct;
386   }
387   
388   private HashSet<Integer> createConnectionList(Integer node){ // not used
389       HashSet<Integer> cl = new HashSet<Integer>();
390       HashSet<Integer> crrnodes = new HashSet<Integer>();
391       crrnodes.add(node);
392       cl.add(node);
393       for ( int i = 0 ; i < nsteps; i++ ){
394           Set<Integer> nextnodes = new HashSet<Integer>();
395           Iterator<Integer> cit = crrnodes.iterator();
396           while ( cit.hasNext() ){
397               Integer crr = cit.next();
398               Set<Integer> nexts = gadjlist.get(crr).keySet();
399               Iterator<Integer> nit = nexts.iterator();
400               while ( nit.hasNext() ){
401                   Integer next = nit.next();
402                   if ( !cl.contains(next) ){
403                       nextnodes.add(next);
404                       cl.add(next);
405                   }
406               }
407           }
408           crrnodes.clear();
409           crrnodes.addAll(nextnodes);
410       }
411       return cl;
412   }
413   
414   
415   private void updateWeight(Integer node1, Integer node2, ClassLink edge){
416       Map<Integer, Integer> weight = edgeweight.get(node1);
417       Integer crr = weight.get(node2);
418       if (crr == null ){
419           crr = edge.getNumOfLinkedClassInstances();
420           weight.put(node2, crr);           
421       }
422       if ( crr < edge.getNumOfLinkedClassInstances() ){
423           crr = edge.getNumOfLinkedClassInstances();
424           weight.put(node2, crr);
425       }
426       weight = edgeweight.get(node2);
427       crr = weight.get(node1);
428       if (crr == null ){
429           crr = edge.getNumOfOriginClassInstances();
430           weight.put(node2, crr);           
431       }
432       if ( crr < edge.getNumOfOriginClassInstances() ){
433           crr = edge.getNumOfOriginInstances();
434           weight.put(node1, crr);
435       }
436   }
437   
438   // old codes
439   /*
440    public Path[] getPaths_old(RDFSchemaAnalyzer rdfsa, boolean countLink, String startClass, String endClass){
441        List<List<ClassLink>> paths = null;
442        paths = searchPathsbyVisitingNodes(rdfsa, countLink, startClass, endClass);
443        NavigableSet<Path> sortedpath = new TreeSet<Path>();
444        ListIterator<List<ClassLink>> pit = paths.listIterator();
445        int j = 0;
446        while ( pit.hasNext() ){
447            Path path = new Path();
448            path.setStartClass(startClass);
449            List<ClassLink> crrpath = pit.next();
450            path.setClassLinks(crrpath);
451            ListIterator<ClassLink> cit = crrpath.listIterator();
452            int min = Integer.MAX_VALUE;
453            while ( cit.hasNext() ){
454                ClassLink cl = cit.next();
455                if ( cl.getNumOfLinks() < min ){
456                    min = cl.getNumOfLinks();
457                }
458            }
459            path.setWidth(min);
460            sortedpath.add(path);
461            j++;
462        }
463        Path[] patharray = new Path[paths.size()];
464        Iterator<Path> pait = sortedpath.descendingIterator();
465        int i = 0;
466        while ( pait.hasNext() ){
467            patharray[i] = pait.next();
468            i++;
469        }
470        return patharray;
471    }
472
473    private List<List<ClassLink>> searchPaths_old(String startClass, String endClass){
474
475        List<List<ClassLink>> paths = new ArrayList<>();
476        List<List<Integer>> simplePaths = new LinkedList<>();
477        Integer snode = labelednodes.get(startClass);
478        Integer enode = labelednodes.get(endClass);
479        List<List<Integer>> lp = new LinkedList<>();
480        List<Integer> ini = new LinkedList<Integer>(); // initial path
481        ini.add(snode);
482        lp.add(ini);
483        for (int i = 0; i < nsteps; i++ ){
484            ListIterator<List<Integer>> lit = lp.listIterator();
485            List<List<Integer>> nextlp = new LinkedList<>();
486            while ( lit.hasNext() ){
487                List<Integer> crrpath = lit.next();
488                Integer crrnode = crrpath.get(crrpath.size()-1);
489                Set<Integer> nexts = gadjlist.get(crrnode).keySet();
490                Iterator<Integer> nit = nexts.iterator();
491                while( nit.hasNext() ){
492                    Integer nextnode = nit.next();
493                    if ( crrpath.contains(nextnode) ){ continue; }
494                    List<Integer> nextpath = new LinkedList<Integer>(crrpath); // copy
495                    nextpath.add(nextnode);
496                    if ( nextnode.equals(enode) ){
497                        simplePaths.add(nextpath);
498                        continue;
499                    }
500                    nextlp.add(nextpath);
501                }
502            }
503            lp = nextlp;
504        }
505       
506        ListIterator<List<Integer>> pit = simplePaths.listIterator();
507        while( pit.hasNext()){
508            List<Integer> spath = pit.next();
509            List<List<ClassLink>> convertedPaths = convertSimplePathToPaths(spath);
510            paths.addAll(convertedPaths);
511        }
512        return paths;
513    }   
514    */
515       /*
516    private List<List<ClassLink>> searchPaths(RDFSchemaAnalyzer rdfsa, boolean countLinks){
517        List<List<ClassLink>> paths = new ArrayList<>();
518        List<LinkAndPath> lp = new LinkedList<>();
519        lp.add(new LinkAndPath(new ClassLink("",startClass,null,Direction.both,0,0,0,0,0,false,false), new LinkedList<ClassLink>(), ""));
520        try{
521          for ( int i = 0; i < nsteps; i++ ){
522              ListIterator<LinkAndPath> lit = lp.listIterator();
523              List<LinkAndPath> nextlp = new LinkedList<>();
524              while ( lit.hasNext() ){
525                  LinkAndPath crrlp = lit.next();
526                  ClassLink[] classLinks = rdfsa.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, countLinks);
527                  for ( int j = 0 ; j < classLinks.length; j++ ){
528                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
529                      crrpath.add(classLinks[j]);
530                      if ( classLinks[j].getLinkedClassURI() == null ){ continue; }
531                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
532                          paths.add(new LinkedList<>(crrpath));
533                          continue;
534                      }
535                      if ( countLinks == true && classLinks[j].getNumOfLinks() <= th){
536                          continue;
537                      }
538                      if ( i >= 2 ){
539                          if ( crrlp.classLink.getPropertyURI().equals(classLinks[j].getPropertyURI()) &&
540                           crrlp.classLink.getDirection() != classLinks[j].getDirection() &&
541                           crrlp.originalClassURI.equals( classLinks[j].getLinkedClassURI()) ){
542                              continue;
543                          }
544                      }
545                      nextlp.add(new LinkAndPath(classLinks[j], crrpath, crrlp.classLink.getLinkedClassURI()));
546                  }
547              }
548              lp = nextlp;
549          }
550        }catch(Exception e){
551            System.err.println(e);
552        }
553        return paths; 
554    }
555    */
556
557}
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。