Skip to content

Commit

Permalink
[JENKINS-17247] Refactored a bit to extract the SCC computation into …
Browse files Browse the repository at this point in the history 
…a reusable code
  • Loading branch information
@kohsuke
kohsuke committed Jun 20, 2013
1 parent 8d0f7f5 commit edb9bc5
Show file tree
Hide file tree
Showing 2 changed files with 175 additions and 98 deletions.
118 changes: 20 additions & 98 deletions core/src/main/java/hudson/model/DependencyGraph.java
View file
Expand Up @@ -28,12 +28,12 @@
import com.google.common.collect.ImmutableList;
import hudson.security.ACL;
import jenkins.model.Jenkins;
import jenkins.util.DirectedGraph;
import jenkins.util.DirectedGraph.SCC;
import org.acegisecurity.context.SecurityContext;
import org.acegisecurity.context.SecurityContextHolder;
import org.apache.commons.collections.map.HashedMap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
Expand Down Expand Up @@ -110,106 +110,31 @@ public void build() {
* See http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
*/
private void topologicalDagSort() {
/**
* Node of the cyclic graph, which is primarily {@link AbstractProject} but with additional
* data structures needed for the Tarjan's algorithm.
*/
class Node {
final AbstractProject project;
/**
* DFS visit order.
*/
int index = -1;
/**
* The smallest index of any nodes reachable from this node transitively.
*/
int lowlink;

/**
* Strongly connected component index.
* All the {@link Node}s that have the same SCC number belongs to the same strongly-connected
* component, and more over, the Tarjan's algorithm is such that the scc index constitutes
* the reverse topological order of the topological sort of the SCC DAG.
*
* Smallest SCC# means everyone depends on you.
*/
int scc = -1;

Node(AbstractProject project) {
this.project = project;
}

Collection<AbstractProject> edges() {
return getDownstream(project);
}
}

final Map<AbstractProject, Node> nodes = new HashMap<AbstractProject, Node>();
for (AbstractProject p : forward.keySet()) {
if (!nodes.containsKey(p))
nodes.put(p,new Node(p));
}
for (AbstractProject p : backward.keySet()) {
if (!nodes.containsKey(p))
nodes.put(p,new Node(p));
}

class Tarjan {
int index = 0;
int scc = 0;
/**
* Nodes not yet classified for the strongly connected components
*/
Stack<Node> pending = new Stack<Node>();

void traverse() {
for (Node n : nodes.values()) {
if (n.index==-1)
visit(n);
}
}

void visit(Node v) {
v.index = v.lowlink = index++;
pending.push(v);

for (AbstractProject q : v.edges()) {
Node w = nodes.get(q);
if (w.index==-1) {
visit(w);
v.lowlink = Math.min(v.lowlink,w.lowlink);
} else
if (pending.contains(w)) {
v.lowlink = Math.min(v.lowlink,w.index);
}
}

if (v.lowlink==v.index) {
Node w;
do {
w = pending.pop();
w.scc = scc;
} while(w!=v);
scc++;
}
DirectedGraph<AbstractProject> g = new DirectedGraph<AbstractProject>() {
@Override
protected Collection<AbstractProject> nodes() {
final Set<AbstractProject> nodes = new HashSet<AbstractProject>();
nodes.addAll(forward.keySet());
nodes.addAll(backward.keySet());
return nodes;
}
}

new Tarjan().traverse();

// sort nodes in the topological order
Node[] a = nodes.values().toArray(new Node[nodes.size()]);
Arrays.sort(a,new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o2.scc-o1.scc; // Tarjan finds them backward, so the order is swapped here
protected Collection<AbstractProject> forward(AbstractProject node) {
return getDownstream(node);
}
});
};

List<SCC<AbstractProject>> sccs = g.getStronglyConnectedComponents();

final Map<AbstractProject,Integer> topoOrder = new HashMap<AbstractProject,Integer>();
topologicallySorted = new ArrayList<AbstractProject<?,?>>();
int idx=0;
for (Node n : a) {
topoOrder.put(n.project,idx++);
for (SCC<AbstractProject> scc : sccs) {
for (AbstractProject n : scc) {
topoOrder.put(n,idx++);
topologicallySorted.add(n);
}
}

topologicalOrder = new Comparator<AbstractProject<?, ?>>() {
Expand All @@ -219,9 +144,6 @@ public int compare(AbstractProject<?,?> o1, AbstractProject<?,?> o2) {
}
};

topologicallySorted = new ArrayList<AbstractProject<?,?>>(a.length);
for (Node n : a)
topologicallySorted.add(n.project);
topologicallySorted = Collections.unmodifiableList(topologicallySorted);
}

Expand Down
155 changes: 155 additions & 0 deletions core/src/main/java/jenkins/util/DirectedGraph.java
View file
@@ -0,0 +1,155 @@
package jenkins.util;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
* A possible cyclic directed graph.
*
* This class defines various algorithms on a directed graph that's not necessarily acyclic.
*
* @author Kohsuke Kawaguchi
*/
public abstract class DirectedGraph<N> {
/**
* All the vertices of the nodes.
*/
protected abstract Collection<N> nodes();

/**
* Forward traversal of the edges.
*/
protected abstract Collection<N> forward(N node);

/**
* Strongly connected component (SCC) of a graph.
*/
public static class SCC<N> extends AbstractSet<N> {
/**
* The Tarjan's algorithm is such that this index constitutes
* the reverse topological order of the topological sort of the SCC DAG.
*
* <p>
* That is, if you think about a derived graph where nodes are SCCs of the original directed graph,
* it will always form a DAG even when the original graph has cycles.
*
* Smallest SCC# means it's more of a sink, and larger SCC# means it's more of a source.
*/
public final int index;

private final List<N> members = new ArrayList<N>();

public SCC(int index) {
this.index = index;
}

@Override
public Iterator<N> iterator() {
return members.iterator();
}

@Override
public int size() {
return members.size();
}
}

/**
* Performs the Tarjan's algorithm and computes strongly-connected components from the
* sink to source order.
*
* See http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
*/
public List<SCC<N>> getStronglyConnectedComponents() {
/**
* Node of the cyclic graph, which is primarily {@link N} but with additional
* data structures needed for the Tarjan's algorithm.
*/
class Node {
final N n;
/**
* DFS visit order.
*/
int index = -1;
/**
* The smallest index of any nodes reachable from this node transitively.
*/
int lowlink;

SCC scc;

Node(N n) {
this.n = n;
}

Collection<N> edges() {
return forward(n);
}
}

final Map<N, Node> nodes = new HashMap<N, Node>();
for (N n : nodes()) {
nodes.put(n,new Node(n));
}

final List<SCC<N>> sccs = new ArrayList<SCC<N>>();

class Tarjan {
int index = 0;
int sccIndex = 0;
/**
* Nodes not yet classified for the strongly connected components
*/
Stack<Node> pending = new Stack<Node>();

void traverse() {
for (Node n : nodes.values()) {
if (n.index==-1)
visit(n);
}
}

void visit(Node v) {
v.index = v.lowlink = index++;
pending.push(v);

for (N q : v.edges()) {
Node w = nodes.get(q);
if (w.index==-1) {
visit(w);
v.lowlink = Math.min(v.lowlink,w.lowlink);
} else
if (pending.contains(w)) {
v.lowlink = Math.min(v.lowlink,w.index);
}
}

if (v.lowlink==v.index) {
// found a new SCC
SCC<N> scc = new SCC<N>(sccIndex++);
sccs.add(scc);

Node w;
do {
w = pending.pop();
w.scc = scc;
scc.members.add(w.n);
} while(w!=v);
}
}
}

new Tarjan().traverse();

Collections.reverse(sccs);

return sccs;
}
}

0 comments on commit edb9bc5

Please sign in to comment.