equal
deleted
inserted
replaced
34 |
34 |
35 def inverse(self): |
35 def inverse(self): |
36 '''inverse DAG, where parents becomes children, etc.''' |
36 '''inverse DAG, where parents becomes children, etc.''' |
37 raise NotImplementedError |
37 raise NotImplementedError |
38 |
38 |
39 def ancestorset(self, starts, stops=None): |
|
40 ''' |
|
41 set of all ancestors of starts (incl), but stop walk at stops (excl) |
|
42 ''' |
|
43 raise NotImplementedError |
|
44 |
|
45 def descendantset(self, starts, stops=None): |
|
46 ''' |
|
47 set of all descendants of starts (incl), but stop walk at stops (excl) |
|
48 ''' |
|
49 return self.inverse().ancestorset(starts, stops) |
|
50 |
|
51 def headsetofconnecteds(self, ixs): |
39 def headsetofconnecteds(self, ixs): |
52 ''' |
40 ''' |
53 subset of connected list of ixs so that no node has a descendant in it |
41 subset of connected list of ixs so that no node has a descendant in it |
54 |
42 |
55 By "connected list" we mean that if an ancestor and a descendant are in |
43 By "connected list" we mean that if an ancestor and a descendant are in |
57 ''' |
45 ''' |
58 raise NotImplementedError |
46 raise NotImplementedError |
59 |
47 |
60 class genericdag(basedag): |
48 class genericdag(basedag): |
61 '''generic implementations for DAGs''' |
49 '''generic implementations for DAGs''' |
62 |
|
63 def ancestorset(self, starts, stops=None): |
|
64 if stops: |
|
65 stops = set(stops) |
|
66 else: |
|
67 stops = set() |
|
68 seen = set() |
|
69 pending = list(starts) |
|
70 while pending: |
|
71 n = pending.pop() |
|
72 if n not in seen and n not in stops: |
|
73 seen.add(n) |
|
74 pending.extend(self.parents(n)) |
|
75 return seen |
|
76 |
50 |
77 def headsetofconnecteds(self, ixs): |
51 def headsetofconnecteds(self, ixs): |
78 hds = set(ixs) |
52 hds = set(ixs) |
79 if not hds: |
53 if not hds: |
80 return hds |
54 return hds |
125 |
99 |
126 def inverse(self): |
100 def inverse(self): |
127 if self._inverse is None: |
101 if self._inverse is None: |
128 self._inverse = inverserevlogdag(self) |
102 self._inverse = inverserevlogdag(self) |
129 return self._inverse |
103 return self._inverse |
130 |
|
131 def ancestorset(self, starts, stops=None): |
|
132 rlog = self._revlog |
|
133 idx = rlog.index |
|
134 if stops: |
|
135 stops = set(stops) |
|
136 else: |
|
137 stops = set() |
|
138 seen = set() |
|
139 pending = list(starts) |
|
140 while pending: |
|
141 rev = pending.pop() |
|
142 if rev not in seen and rev not in stops: |
|
143 seen.add(rev) |
|
144 revdata = idx[rev] |
|
145 for i in [5, 6]: |
|
146 prev = revdata[i] |
|
147 if prev != nullrev: |
|
148 pending.append(prev) |
|
149 return seen |
|
150 |
104 |
151 def headsetofconnecteds(self, ixs): |
105 def headsetofconnecteds(self, ixs): |
152 if not ixs: |
106 if not ixs: |
153 return set() |
107 return set() |
154 rlog = self._revlog |
108 rlog = self._revlog |