From 17bd9beaf7f358a44e5bf36a5855fe6727d506dc Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Tue, 10 May 2022 18:17:06 +0100 Subject: [pagoda] Move project to Scala This commit includes a few changes: - The repository still uses Maven to manage dependency but it is now a Scala project. - The code has been ported from OWLAPI 3.4.10 to 5.1.20 - A proof of concept program using both RSAComb and PAGOdA has been added. --- .../ac/ox/cs/pagoda/endomorph/DependencyGraph.java | 290 --------------------- 1 file changed, 290 deletions(-) delete mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java (limited to 'src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java') diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java deleted file mode 100644 index 0f215ad..0000000 --- a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java +++ /dev/null @@ -1,290 +0,0 @@ - package uk.ac.ox.cs.pagoda.endomorph; - - import uk.ac.ox.cs.pagoda.summary.Edge; - import uk.ac.ox.cs.pagoda.summary.Graph; - import uk.ac.ox.cs.pagoda.summary.Node; - import uk.ac.ox.cs.pagoda.summary.NodeTuple; - import uk.ac.ox.cs.pagoda.util.Timer; - import uk.ac.ox.cs.pagoda.util.Utility; - - import java.util.*; - -public class DependencyGraph { - - Set entrances = new HashSet(); - - public Set getEntrances() { - return entrances; - } - - Set exits = new HashSet(); - - public Set getExits() { - return exits; - } - - Map> outGoingEdges = new HashMap>(); - - public Map> getOutGoingEdges() { - return outGoingEdges; - } - - Map> inComingEdges = new HashMap>(); - - public Map> getInComingEdges() { - return inComingEdges; - } - - Graph graph; - EndomorphChecker homomorphismChecker; - Set cliques = new HashSet(); - - public DependencyGraph(Graph graph) { - this.graph = graph; - homomorphismChecker = new EndomorphChecker2(graph); -// homomorphismChecker = new EndomorphChecker1(graph); - } - - private int compareNodeTuple(NodeTuple t1, NodeTuple t2) { - Iterator iter1 = t1.getNodes().iterator(); - Iterator iter2 = t2.getNodes().iterator(); - int ret; - int index = 0; - Node u, v; - while (iter1.hasNext()) { - u = iter1.next(); v = iter2.next(); - if (u == null && v == null) { - if ((ret = t1.getAnswerTuple().getGroundTerm(index).toString().compareTo(t2.getAnswerTuple().getGroundTerm(index).toString())) != 0) - return ret; - } - else if (u != null && v != null) { - if ((ret = compareNode(u, v)) != 0) return ret; - } - else if (u == null) - return 1; - else if (v == null) - return -1; - - } - - return 0; - } - - private int compareNode(Node o1, Node o2) { - int result = o1.getConcepts().size() - o2.getConcepts().size(); - if (result != 0) return dir(result); - Edge[] edge1 = graph.getOutGoingEdges(o1), edge2 = graph.getOutGoingEdges(o2); - int len1 = edge1 == null ? 0 : edge1.length, len2 = edge2 == null ? 0 : edge2.length; - result = len1 - len2; - if (result != 0) return dir(result); - - edge1 = graph.getInComingEdges(o1); edge2 = graph.getInComingEdges(o2); - len1 = edge1 == null ? 0 : edge1.length; len2 = edge2 == null ? 0 : edge2.length; - result = len1 - len2; - if (result != 0) return dir(result); - - else return o1.getLabel().compareTo(o2.getLabel()); - } - - private int dir(int flag) { return - flag; } - - public void build(Collection nodeTuples) { - - if (nodeTuples.isEmpty()) return ; - - Timer t = new Timer(); - - NodeTuple[] nodeTupleArray = new NodeTuple[nodeTuples.size()]; - nodeTuples.toArray(nodeTupleArray); - - Arrays.sort(nodeTupleArray, new Comparator() { - @Override - public int compare(NodeTuple t1, NodeTuple t2) { - return compareNodeTuple(t1, t2); - } - }); - - Utility.logDebug(nodeTupleArray[0].toString(), - nodeTupleArray[nodeTupleArray.length - 1].toString()); - - for (NodeTuple nodeTuple: nodeTupleArray) addNodeTuple(nodeTuple); - - Utility.logDebug("The number of times to call homomorphism checker: " + homomorphismCheckCounter + "(" + outGoingCheckCounter + "," + inComingCheckCounter + ").", - "Time to compute endomorphism relation: " + t.duration()); - -// print(); - - topologicalOrder = null; - Utility.logDebug("link: " + link); - } - - LinkedList topologicalOrder = null; - - public LinkedList getTopologicalOrder() { - if (topologicalOrder != null) return topologicalOrder; - - topologicalOrder = new LinkedList(); - Queue toVisit = new LinkedList(entrances); - Map toVisitedInComingDegree = new HashMap(); - - int count; - while (!toVisit.isEmpty()) { - Clique cu = toVisit.remove(); - topologicalOrder.add(cu); - if (outGoingEdges.containsKey(cu)) - for (Clique cv: outGoingEdges.get(cu)) { - if (toVisitedInComingDegree.containsKey(cv)) { - count = toVisitedInComingDegree.get(cv) - 1; - toVisitedInComingDegree.put(cv, count); - } - else - toVisitedInComingDegree.put(cv, count = inComingEdges.get(cv).size() - 1); - if (count == 0) - toVisit.add(cv); - } - } - - return topologicalOrder; - } - - private void addNodeTuple(NodeTuple u) { - Queue toCompare = new LinkedList(entrances); - - Map toVisitedDegree = new HashMap(); - Collection directSuccessors = new LinkedList(); - - int count; - while (!toCompare.isEmpty()) { - Clique cv = toCompare.remove(); - ++outGoingCheckCounter; - if (checkHomomorphism(u, cv.representative)) { - directSuccessors.add(cv); - } - else { - if (outGoingEdges.containsKey(cv)) - for (Clique c: outGoingEdges.get(cv)) { - if (toVisitedDegree.containsKey(c)) { - count = toVisitedDegree.get(c) - 1; - toVisitedDegree.put(c, count); - } - else - toVisitedDegree.put(c, count = inComingEdges.get(c).size() - 1); - - if (count == 0) - toCompare.add(c); - } - } - } - - if (directSuccessors.size() == 1) { - Clique clique = directSuccessors.iterator().next(); - if (checkHomomorphism(clique.representative, u)) { - clique.addNodeTuple(u); - return ; - } - } - - Clique cu = new Clique(u); - cliques.add(cu); - - toCompare.clear(); - Set visited = new HashSet(); - - if (directSuccessors.size() == 0) - toCompare.addAll(exits); - else { - for (Clique cv: directSuccessors) - if (inComingEdges.containsKey(cv)) - for (Clique cw: inComingEdges.get(cv)) { - visited.add(cw); - toCompare.add(cw); - } - } - - - - Collection directPredecessors = new LinkedList(); - - while (!toCompare.isEmpty()) { - Clique cv = toCompare.remove(); - ++inComingCheckCounter; - if (checkHomomorphism(cv.representative, u)) - directPredecessors.add(cv); - else { - if (inComingEdges.containsKey(cv)) - for (Clique c: inComingEdges.get(cv)) - if (!visited.contains(c)) { - visited.add(c); - toCompare.add(c); - } - } - } - - for (Clique cv: directSuccessors) { - if (entrances.contains(cv)) entrances.remove(cv); - link(cu, cv); - } - - for (Clique cw: directPredecessors) { - if (exits.contains(cw)) exits.remove(cw); - link(cw, cu); - } - - if (directPredecessors.size() == 0) entrances.add(cu); - if (directSuccessors.size() == 0) exits.add(cu); - } - - private int homomorphismCheckCounter = 0; - private int outGoingCheckCounter = 0, inComingCheckCounter = 0; - - private boolean checkHomomorphism(NodeTuple u, NodeTuple v) { - ++homomorphismCheckCounter; - homomorphismChecker.setMapping(u, v); - - if(!homomorphismChecker.isMappingTo(u, v)) - return false; - - try { - Node node1, node2; - for (Iterator iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) { - node1 = iter1.next(); node2 = iter2.next(); - if (node1 != node2 && !homomorphismChecker.check(node1, node2)) { -// System.out.println(homomorphismChecker.check(node1, node2)); - return false; - } - } - return true; - } finally { - homomorphismChecker.clearMappings(); - } - } - - private void link(Clique u, Clique v) { - ++link; - addToList(outGoingEdges, u, v); - addToList(inComingEdges, v, u); - } - - private int link = 0; - - private void addToList(Map> map, Clique u, Clique v) { - Collection temp; - if ((temp = map.get(u)) == null) { - temp = new LinkedList(); - map.put(u, temp); - } - temp.add(v); - } - - public void print() { - System.out.println("---------- Dependency Graph -------------"); - for (Clique u: cliques) - if (outGoingEdges.containsKey(u)) - for (Clique v: outGoingEdges.get(u)) - System.out.println(u + " -> " + v); - System.out.println("-----------------------------------------"); - } - - -} - -- cgit v1.2.3