1. Mark Howison
  2. gabi

Commits

Mark Howison  committed 5c5bd1d

graph: random walk now stops if it intersects itself

  • Participants
  • Parent commits d24dcae
  • Branches chloroplast, devel 3
    1. hiv
    2. issue-7
    3. issue7a

Comments (0)

Files changed (1)

File gabi/graph.py

View file
  • Ignore whitespace
     def backward(self, n):
         return self.G.predecessors_iter(n)
 
-    def forward_random(self, n):
-        return choice(self.G.successors(n))
+    def forward_random(self, n, exclude=None):
+        if exclude:
+            successors = filter(
+                lambda n : not n in exclude, self.G.successors_iter(n))
+        else:
+            successors = self.G.successors(n)
+        return choice(successors)
 
-    def backward_random(self, n):
-        return choice(self.G.predecessors(n))
+    def backward_random(self, n, exclude=None):
+        if exclude:
+            predecessors = filter(
+                lambda n : not n in exclude, self.G.predecessors_iter(n))
+        else:
+            predecessors = self.G.predecessors(n)
+        return choice(predecessors)
 
     def forward_active(self, n):
         if self.A.has_node(n) and self.A.out_degree(n):
             self.deactivate(e)
         else:
             path = []
+            path_set = set()
             # Search forward until reaching an active path or an endpoint
             n = n2
             while not (n is None or self.A.has_node(n)):
                 path.append(n)
-                n = self.forward_random(n)
+                path_set.add(n)
+                n = self.forward_random(n, exclude=path_set)
             end = n
             # Search backward until reaching an active path or an endpoint
             n = n1
             while not (n is None or self.A.has_node(n)):
                 path.insert(0, n)
-                n = self.backward_random(n)
+                path_set.add(n)
+                n = self.backward_random(n, exclude=path_set)
             start = n
             # Deactivate old path forward
             if start is not None: