transform

commit 6afcffe88a34e26b777eca212db143c8d2ac10a0
parent c8ef335cb20081ffb74df220bae9540b7b660a46
Author: Étienne Simon <esimon@esimon.eu>
Date:   Wed, 18 Jun 2014 17:10:47 +0200

Add circuit detection to relations analyzer

Diffstat:
M
utils/relations analyzer.py
 | 
35
++++++++++++++++++++++++++++++-----

1 file changed, 30 insertions(+), 5 deletions(-)
diff --git a/utils/relations analyzer.py b/utils/relations analyzer.py
@@ -11,15 +11,17 @@ if __name__ == '__main__':
         sys.exit(1)
     data = Dataset(sys.argv[1])
 
-    print('# Splitting dataset')
+    print('# Splitting dataset and building adjacency lists')
     lefts, rights = [[] for _ in xrange(data.number_relations)], [[] for _ in xrange(data.number_relations)]
+    adj_list = [[] for _ in xrange(data.number_entities)]
     for relation, left, right in data.iterate("test"):
         left, relation, right = left.indices[0], relation.indices[0], right.indices[0]
         lefts[relation].append(left)
         rights[relation].append(right)
+        adj_list[left].append((relation, right))
 
-    total_injective, total_functional, total_onetoone, total_irreflexive = 0, 0, 0, 0
-    print(' '*123+'injective functional 1-to-1 irreflexive')
+    total_injective, total_functional, total_onetoone, total_irreflexive, total_circuit = 0, 0, 0, 0, 0
+    print(' '*103+'injective functional 1-to-1 irreflexive circuit')
     for index, relation in enumerate(data.relations):
         left = lefts[index]
         right = rights[index]
@@ -34,14 +36,36 @@ if __name__ == '__main__':
             if l==r:
                 irreflexive = False
 
-        intersection = image & preimage
+        visitme = image & preimage
+        visiting = set()
 
-        print('{0:<120} : {1:<9} {2:<10} {3:<6} {4:<11}'.format(relation, injective, functional, onetoone, irreflexive))
+        def dfs(node):
+            visiting.add(node)
+            for (rel, right) in adj_list[node]:
+                if rel == index:
+                    if right in visiting:
+                        return True
+                    elif right in visitme:
+                        visitme.remove(right)
+                        if dfs(right):
+                            return True
+            visiting.remove(node)
+            return False
+
+        circuit = False
+        while len(visitme)>0:
+            if dfs(visitme.pop()):
+                circuit = True
+                break
+
+
+        print('{0:<100} : {1:<9} {2:<10} {3:<6} {4:<11} {5:<6}'.format(relation, injective, functional, onetoone, irreflexive, circuit))
 
         total_injective += injective
         total_functional += functional
         total_irreflexive += irreflexive
         total_onetoone += onetoone
+        total_circuit += circuit
     
     N = float(len(data.relations))
     print('')
@@ -49,3 +73,4 @@ if __name__ == '__main__':
     print('Total functional: {0} ({1})'.format(total_functional/N, total_functional))
     print('Total 1-to-1: {0} ({1})'.format(total_onetoone/N, total_onetoone))
     print('Total irreflexive: {0} ({1})'.format(total_irreflexive/N, total_irreflexive))
+    print('Total circuit: {0} ({1})'.format(total_circuit/N, total_circuit))