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

リビジョン 250, 20.4 KB (コミッタ: atsuko, 9 年 前)

バグ対応
  • 属性 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        Integer snode = labelednodes.get(startClass);
129        Integer enode = labelednodes.get(endClass);
130        List<List<Integer>> simplePaths = searchSimplePaths(snode, enode);
131       
132        ListIterator<List<Integer>> pit = simplePaths.listIterator();
133        //System.out.println("SPATH:");
134        //System.out.println(simplePaths.size());
135        while( pit.hasNext()){
136            List<Integer> spath = pit.next();
137            List<List<ClassLink>> convertedPaths = convertSimplePathToPaths(spath);
138            paths.addAll(convertedPaths);
139        }
140        //System.out.println("PATH:");
141        //System.out.println(paths.size());
142        return paths;
143    }
144
145    private List<List<Integer>> searchSimplePaths(Integer snode, Integer enode){
146        List<List<Integer>> simplePaths = new LinkedList<>();
147        List<List<Integer>> lp = new LinkedList<>();
148        List<Integer> ini = new LinkedList<Integer>(); // initial path
149        ini.add(snode);
150        lp.add(ini);
151        for (int i = 0; i < nsteps; i++ ){
152            ListIterator<List<Integer>> lit = lp.listIterator();
153            List<List<Integer>> nextlp = new LinkedList<>();
154            while ( lit.hasNext() ){
155                List<Integer> crrpath = lit.next();
156                Integer crrnode = crrpath.get(crrpath.size()-1);
157                Set<Integer> nexts = gadjlist.get(crrnode).keySet();
158                Iterator<Integer> nit = nexts.iterator();
159                while( nit.hasNext() ){
160                    Integer nextnode = nit.next();
161                    if ( crrpath.contains(nextnode) ){ continue; }
162                    List<Integer> nextpath = new LinkedList<Integer>(crrpath); // copy
163                    nextpath.add(nextnode);
164                    // tmp
165                    if ( i >= 1 ){
166                        int wn = nodeweight.get(crrnode);
167                        int in = edgeweight.get(crrpath.get(crrpath.size()-2)).get(crrnode);
168                        int out = edgeweight.get(nextnode).get(crrnode);
169                        if ( wn > in + out ){
170                            /*
171                            String key1 = nextnode.toString().concat("-").concat(crrpath.get(crrpath.size()-1).toString())
172                                .concat("-").concat(crrpath.get(crrpath.size()-2).toString());
173                            String key2 = crrpath.get(crrpath.size()-2).toString().concat("-").concat(crrpath.get(crrpath.size()-1).toString())
174                                .concat("-").concat(nextnode.toString());
175                            if ( checkedpaths.containsKey(key1) ){
176                                if ( checkedpaths.get(key1) == false ){
177                                   continue;
178                                }
179                            }else if ( checkedpaths.containsKey(key2) ){
180                                if ( checkedpaths.get(key2) == false ){
181                                   continue;
182                                }
183                            }else{                     
184                                boolean chk = EndpointAccess.check3SimplePathwithJoin(nextnode, crrpath.get(crrpath.size()-1),
185                                    crrpath.get(crrpath.size()-2), this, sparqlEndpoint);
186                                checkedpaths.put(key1, chk);
187                                if ( chk == false ){
188                                    continue;
189                                }
190                            }
191                            */
192                            continue;
193                        }
194                    }
195                    if ( nextnode.equals(enode) ){
196                        simplePaths.add(nextpath);
197                        continue;
198                    }
199                    nextlp.add(nextpath);
200                }
201            }
202            lp = nextlp;
203        }       
204        return simplePaths;
205    }
206   
207   
208    private List<List<ClassLink>> convertSimplePathToPaths(List<Integer> simplePath){
209        List<List<ClassLink>> paths = new LinkedList<List<ClassLink>>();
210        ListIterator<Integer> spit = simplePath.listIterator();
211        Integer start = spit.next();
212        String startClass = this.labels.get(start);
213        Integer end = spit.next();
214        List<LabeledEdge> edges = gadjlist.get(start).get(end);
215        ListIterator<LabeledEdge> eit = edges.listIterator();
216        while ( eit.hasNext() ){
217            List<ClassLink> cl = new LinkedList<ClassLink>();
218            cl.add((ClassLink)eit.next().getLabel());
219            paths.add(cl);
220        }
221        start = end;
222        while( spit.hasNext() ){
223            end = spit.next();
224            // start-end
225            edges = gadjlist.get(start).get(end);
226            List<List<ClassLink>> tmppaths = new LinkedList<List<ClassLink>>();           
227            // current path
228            ListIterator<List<ClassLink>> pit = paths.listIterator();
229            while ( pit.hasNext() ){
230                List<ClassLink> basepath = pit.next();
231                eit = edges.listIterator();
232                while ( eit.hasNext() ){
233                    ClassLink cl = (ClassLink) eit.next().label;
234                    List<ClassLink> addedpath = new LinkedList<ClassLink>(basepath);
235                    addedpath.add(cl);
236                    // check
237                    //if ( EndpointAccess.checkPath(startClass, addedpath, sparqlEndpoint) ){
238                        tmppaths.add(addedpath);
239                    //}
240                }
241            }
242            paths = tmppaths;
243            start = end;
244        }       
245        return paths;
246    }
247   
248/*             
249   private void setClassGraph(RDFSchemaAnalyzer rdfsa){
250       // setNodes
251       SClass[] classes = null;
252       try{
253           classes = rdfsa.getOWLClasses(null, null, null, true);
254       }catch(Exception e){
255           System.err.println(e); return;
256       }
257       for (int i = 0 ; i < classes.length; i++){
258           addNode(classes[i].getClassURI());
259           nodeType.add("class");
260       }
261       // setEdges
262       for (int i = 0 ; i < classes.length; i++ ){
263           try{
264               ClassLink[] classLinks = rdfsa.getNextClass(null, classes[i].getClassURI(), limit, true);
265               for (int j = 0 ; j < classLinks.length; j++){
266                   Integer n = labelednodes.get(classLinks[j].getLinkedClassURI());
267                   if ( n != null ){
268                       addEdge(i, n, classLinks[j]);
269                   }else{
270                       n = labelednodes.get(classLinks[j].getLinkedLiteralDatatypeURI());
271                       if ( n == null ){
272                           addNode(classLinks[j].getLinkedLiteralDatatypeURI());
273                           n = nodeType.size();
274                           nodeType.add("literal");
275                       }
276                       addEdge(i, n, classLinks[j]);
277                   }
278               }
279           }catch(Exception e){
280               System.err.println(e);
281           }
282       }       
283   }*/
284
285    public void setPartClassGraph(RDFSchemaAnalyzer rdfsa, String sparqlEndpoint, String startClass){
286        // set endpoint
287        this.sparqlEndpoint = sparqlEndpoint;
288        visited = new HashSet<Integer>();
289        edgeweight = new LinkedList<Map<Integer,Integer>>();
290        nodeweight = new LinkedList<Integer>();
291        // setNodes for all classes
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           edgeweight.add(new HashMap<Integer,Integer>());
302           nodeweight.add(classes[i].getNumOfInstances());
303        }
304        // setEdges
305        Integer snode = labelednodes.get(startClass);
306        Set<Integer> nodes = new HashSet<Integer>();
307        nodes.add(snode);
308        visited.add(snode);
309        for (int i = 0 ; i < nsteps; i++ ){
310            Iterator<Integer> nit = nodes.iterator();
311            Set<Integer> nextnodes = new HashSet<Integer>();
312            while ( nit.hasNext() ){
313                Integer crr = nit.next();
314                try{
315                    ClassLink[] classLinks = rdfsa.getNextClass(null, labels.get(crr), limit, true);
316                    for (int j = 0 ; j < classLinks.length; j++){
317                        Integer nn = labelednodes.get(classLinks[j].getLinkedClassURI());
318                        if ( nn == null ){
319                            continue;
320                        }
321                        if ( !visited.contains(nn) ){
322                            nextnodes.add(nn);
323                        }
324                        addEdge(crr, nn, classLinks[j]);
325                        updateWeight(crr, nn, classLinks[j]);
326                    }
327                }catch(Exception e){
328                    e.printStackTrace();
329                }
330            }
331            nodes = nextnodes;
332            visited.addAll(nodes);
333        }
334        // cut visited
335        Iterator<Integer> nit = visited.iterator();
336        while(nit.hasNext()){
337            Integer node = nit.next();
338            if ( ! node.equals(snode) ){
339                List<List<Integer>> paths = searchSimplePaths(snode, node);
340                if ( paths.isEmpty()){
341                    nit.remove();
342                }
343            }
344        }
345    }
346   
347   
348   private ArrayList<HashSet<Integer>> createConnectionTable(){ // not used
349       ArrayList<HashSet<Integer>> ct = new ArrayList<HashSet<Integer>>();
350       for (int i = 0; i < labels.size(); i++ ){ // each node
351           HashSet<Integer> cl = createConnectionList(i);
352           ct.add(cl);
353       }
354       return ct;
355   }
356   
357   private HashSet<Integer> createConnectionList(Integer node){ // not used
358       HashSet<Integer> cl = new HashSet<Integer>();
359       HashSet<Integer> crrnodes = new HashSet<Integer>();
360       crrnodes.add(node);
361       cl.add(node);
362       for ( int i = 0 ; i < nsteps; i++ ){
363           Set<Integer> nextnodes = new HashSet<Integer>();
364           Iterator<Integer> cit = crrnodes.iterator();
365           while ( cit.hasNext() ){
366               Integer crr = cit.next();
367               Set<Integer> nexts = gadjlist.get(crr).keySet();
368               Iterator<Integer> nit = nexts.iterator();
369               while ( nit.hasNext() ){
370                   Integer next = nit.next();
371                   if ( !cl.contains(next) ){
372                       nextnodes.add(next);
373                       cl.add(next);
374                   }
375               }
376           }
377           crrnodes.clear();
378           crrnodes.addAll(nextnodes);
379       }
380       return cl;
381   }
382   
383   
384   private void updateWeight(Integer node1, Integer node2, ClassLink edge){
385       Map<Integer, Integer> weight = edgeweight.get(node1);
386       Integer crr = weight.get(node2);
387       if (crr == null ){
388           crr = edge.getNumOfLinkedClassInstances();
389           weight.put(node2, crr);           
390       }
391       if ( crr < edge.getNumOfLinkedClassInstances() ){
392           crr = edge.getNumOfLinkedClassInstances();
393           weight.put(node2, crr);
394       }
395       weight = edgeweight.get(node2);
396       crr = weight.get(node1);
397       if (crr == null ){
398           crr = edge.getNumOfOriginClassInstances();
399           weight.put(node1, crr);
400       }
401       if ( crr < edge.getNumOfOriginClassInstances() ){
402           crr = edge.getNumOfOriginInstances();
403           weight.put(node1, crr);
404       }
405   }
406   
407   // old codes
408   /*
409    public Path[] getPaths_old(RDFSchemaAnalyzer rdfsa, boolean countLink, String startClass, String endClass){
410        List<List<ClassLink>> paths = null;
411        paths = searchPathsbyVisitingNodes(rdfsa, countLink, startClass, endClass);
412        NavigableSet<Path> sortedpath = new TreeSet<Path>();
413        ListIterator<List<ClassLink>> pit = paths.listIterator();
414        int j = 0;
415        while ( pit.hasNext() ){
416            Path path = new Path();
417            path.setStartClass(startClass);
418            List<ClassLink> crrpath = pit.next();
419            path.setClassLinks(crrpath);
420            ListIterator<ClassLink> cit = crrpath.listIterator();
421            int min = Integer.MAX_VALUE;
422            while ( cit.hasNext() ){
423                ClassLink cl = cit.next();
424                if ( cl.getNumOfLinks() < min ){
425                    min = cl.getNumOfLinks();
426                }
427            }
428            path.setWidth(min);
429            sortedpath.add(path);
430            j++;
431        }
432        Path[] patharray = new Path[paths.size()];
433        Iterator<Path> pait = sortedpath.descendingIterator();
434        int i = 0;
435        while ( pait.hasNext() ){
436            patharray[i] = pait.next();
437            i++;
438        }
439        return patharray;
440    }
441
442    private List<List<ClassLink>> searchPaths_old(String startClass, String endClass){
443
444        List<List<ClassLink>> paths = new ArrayList<>();
445        List<List<Integer>> simplePaths = new LinkedList<>();
446        Integer snode = labelednodes.get(startClass);
447        Integer enode = labelednodes.get(endClass);
448        List<List<Integer>> lp = new LinkedList<>();
449        List<Integer> ini = new LinkedList<Integer>(); // initial path
450        ini.add(snode);
451        lp.add(ini);
452        for (int i = 0; i < nsteps; i++ ){
453            ListIterator<List<Integer>> lit = lp.listIterator();
454            List<List<Integer>> nextlp = new LinkedList<>();
455            while ( lit.hasNext() ){
456                List<Integer> crrpath = lit.next();
457                Integer crrnode = crrpath.get(crrpath.size()-1);
458                Set<Integer> nexts = gadjlist.get(crrnode).keySet();
459                Iterator<Integer> nit = nexts.iterator();
460                while( nit.hasNext() ){
461                    Integer nextnode = nit.next();
462                    if ( crrpath.contains(nextnode) ){ continue; }
463                    List<Integer> nextpath = new LinkedList<Integer>(crrpath); // copy
464                    nextpath.add(nextnode);
465                    if ( nextnode.equals(enode) ){
466                        simplePaths.add(nextpath);
467                        continue;
468                    }
469                    nextlp.add(nextpath);
470                }
471            }
472            lp = nextlp;
473        }
474       
475        ListIterator<List<Integer>> pit = simplePaths.listIterator();
476        while( pit.hasNext()){
477            List<Integer> spath = pit.next();
478            List<List<ClassLink>> convertedPaths = convertSimplePathToPaths(spath);
479            paths.addAll(convertedPaths);
480        }
481        return paths;
482    }   
483    */
484       /*
485    private List<List<ClassLink>> searchPaths(RDFSchemaAnalyzer rdfsa, boolean countLinks){
486        List<List<ClassLink>> paths = new ArrayList<>();
487        List<LinkAndPath> lp = new LinkedList<>();
488        lp.add(new LinkAndPath(new ClassLink("",startClass,null,Direction.both,0,0,0,0,0,false,false), new LinkedList<ClassLink>(), ""));
489        try{
490          for ( int i = 0; i < nsteps; i++ ){
491              ListIterator<LinkAndPath> lit = lp.listIterator();
492              List<LinkAndPath> nextlp = new LinkedList<>();
493              while ( lit.hasNext() ){
494                  LinkAndPath crrlp = lit.next();
495                  ClassLink[] classLinks = rdfsa.getNextClass(null, crrlp.classLink.getLinkedClassURI(), limit, countLinks);
496                  for ( int j = 0 ; j < classLinks.length; j++ ){
497                      List<ClassLink> crrpath = new LinkedList<>(crrlp.path);
498                      crrpath.add(classLinks[j]);
499                      if ( classLinks[j].getLinkedClassURI() == null ){ continue; }
500                      if ( classLinks[j].getLinkedClassURI().equals(endClass) ){
501                          paths.add(new LinkedList<>(crrpath));
502                          continue;
503                      }
504                      if ( countLinks == true && classLinks[j].getNumOfLinks() <= th){
505                          continue;
506                      }
507                      if ( i >= 2 ){
508                          if ( crrlp.classLink.getPropertyURI().equals(classLinks[j].getPropertyURI()) &&
509                           crrlp.classLink.getDirection() != classLinks[j].getDirection() &&
510                           crrlp.originalClassURI.equals( classLinks[j].getLinkedClassURI()) ){
511                              continue;
512                          }
513                      }
514                      nextlp.add(new LinkAndPath(classLinks[j], crrpath, crrlp.classLink.getLinkedClassURI()));
515                  }
516              }
517              lp = nextlp;
518          }
519        }catch(Exception e){
520            System.err.println(e);
521        }
522        return paths; 
523    }
524    */
525
526}
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。