From 816a5945a4f2b4bdaf02b5de50c19b0be0c2b7bb Mon Sep 17 00:00:00 2001 From: David James Date: Thu, 11 Apr 2013 22:59:32 -0700 Subject: Add a builder for triggering tryjobs automatically. This builder scans for new CLs and launches tryjobs to test them. Once these automatic trybots have been tested for a while, I am planning on updating it to remove the commit ready bit from CLs. I will also update the commit queue to favor CLs that have been tested by trybots. Currently, this launcher is referred to in the code as the "pre-cq", but I'm planning a followup CL to rename it to "trybot", since that's easier to understand. BUG=chromium:229101 TEST=Launch sample run with a bunch of CLs. TEST=Launch Paladin runs. Change-Id: Ie7cbacf4030e70cc487a246c1e3e00eb4bd0665b Reviewed-on: https://gerrit.chromium.org/gerrit/47975 Commit-Queue: David James Reviewed-by: David James Tested-by: David James --- third_party/digraph.py | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 67 insertions(+) create mode 100644 third_party/digraph.py (limited to 'third_party') diff --git a/third_party/digraph.py b/third_party/digraph.py new file mode 100644 index 000000000..4fafcbd46 --- /dev/null +++ b/third_party/digraph.py @@ -0,0 +1,67 @@ +# Copyright (c) 2013 Mark Dickinson +# +# The above copyright notice and this permission notice shall be included in +# all copies or substantial portions of the Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +# SOFTWARE. + +def StronglyConnectedComponents(vertices, edges): + """Find the strongly connected components of a directed graph. + + Uses a non-recursive version of Gabow's linear-time algorithm [1] to find + all strongly connected components of a directed graph. + + A "strongly connected component" of a directed graph is a maximal subgraph + such that any vertex in the subgraph is reachable from any other; any + directed graph can be decomposed into its strongly connected components. + + Written by Mark Dickinson and licensed under the MIT license [2]. + + [1] Harold N. Gabow, "Path-based depth-first search for strong and + biconnected components," Inf. Process. Lett. 74 (2000) 107--114. + [2] From code.activestate.com: http://goo.gl/X0z4C + + Args: + vertices: A list of vertices. Each vertex should be hashable. + edges: Dictionary that maps each vertex v to a set of the vertices w + that are linked to v by a directed edge (v, w). + + Returns: + A list of sets of vertices. + """ + identified = set() + stack = [] + index = {} + boundaries = [] + + for v in vertices: + if v not in index: + to_do = [('VISIT', v)] + while to_do: + operation_type, v = to_do.pop() + if operation_type == 'VISIT': + index[v] = len(stack) + stack.append(v) + boundaries.append(index[v]) + to_do.append(('POSTVISIT', v)) + to_do.extend([('VISITEDGE', w) for w in edges[v]]) + elif operation_type == 'VISITEDGE': + if v not in index: + to_do.append(('VISIT', v)) + elif v not in identified: + while index[v] < boundaries[-1]: + boundaries.pop() + else: + # operation_type == 'POSTVISIT' + if boundaries[-1] == index[v]: + boundaries.pop() + scc = set(stack[index[v]:]) + del stack[index[v]:] + identified.update(scc) + yield scc -- cgit v1.2.3