/*
This function modifies the supplied directed graph to make it acyclic by
reversing edges that participate in cycles. This algorithm currently uses
a basic DFS traversal.

This algorithm does not preserve attributes.
357621
function makeAcyclic(g) {
    var onStack = {};
    var visited = {};

    function dfs(u) {
      if (u in visited) {
        return;
      }
      visited[u] = true;
      onStack[u] = true;
      g.successors(u).forEach(function(v) {
        if (v in onStack) {
          g.addEdge(v, u);
          g.removeEdge(u, v);
        } else {
          dfs(v);
        }
      });
      delete onStack[u];
    }

    g.nodes().forEach(function(u) {
      dfs(u);
    });
  }
1253465
private static List<Vertex> dijkstra(Graph graph)
    {
        List<Vertex> resultList = new LinkedList<Vertex>();
        Vertex[] vertexes = graph.getVertexes();
        List<EdgeFrom>[] edgesTo = graph.getEdgesTo();
        double[] d = new double[vertexes.length];
        Arrays.fill(d, Double.MAX_VALUE);
        d[d.length - 1] = 0;
        int[] path = new int[vertexes.length];
        Arrays.fill(path, -1);
        PriorityQueue<State> que = new PriorityQueue<State>();
        que.add(new State(0, vertexes.length - 1));
        while (!que.isEmpty())
        {
            State p = que.poll();
            if (d[p.vertex] < p.cost) continue;
            for (EdgeFrom edgeFrom : edgesTo[p.vertex])
            {
                if (d[edgeFrom.from] > d[p.vertex] + edgeFrom.weight)
                {
                    d[edgeFrom.from] = d[p.vertex] + edgeFrom.weight;
                    que.add(new State(d[edgeFrom.from], edgeFrom.from));
                    path[edgeFrom.from] = p.vertex;
                }
            }
        }
        for (int t = 0; t != -1; t = path[t])
        {
            resultList.add(vertexes[t]);
        }
        return resultList;
    }
1237145
private void generateOrderedDepGraph() {
		TopologicalOrderIterator<Predicate, DefaultEdge> iter =
				new TopologicalOrderIterator<Predicate, DefaultEdge>(predicateDependencyGraph);
		
		while (iter.hasNext()){
			Predicate pred = iter.next();
			predicatesInBottomUp.add(pred);
		}
		Collections.reverse(predicatesInBottomUp);
	}
1335917
function (graph, head, where) {
    var routes = [];

    Graph.Visitor.Stacked(graph, head, function (node, stack, weight) {
      if (where && where.length !== stack.length){
        return;
      }
      routes.push(new Graph.Route(stack.slice(), weight));
    });
    return routes;
  }
383279
def graph_simplify(G):
    
    spurs = []
    path_nodes = []
    for k, d in G.degree().iteritems():
        if d == 1:
            spurs.append(k)
        elif d == 2:
            path_nodes.append(k)

    logging.debug("Remove {0} spurs.".format(len(spurs)))
    G.remove_nodes_from(spurs)

    SG = G.subgraph(path_nodes)
    cc = nx.connected_components(SG)
    for c in cc:
        if len(c) == 1:
            continue
        c = set(c)
        neighbors = set()
        for x in c:
            neighbors |= set(G.neighbors(x))
        neighbors -= c
        newtag = list(c)[0] + "*"
        for n in neighbors:
            G.add_edge(newtag, n)
        G.remove_nodes_from(c)
    logging.debug("Contract {0} path nodes into {1} nodes.".\
                    format(len(path_nodes), len(cc)))
994365
function graph(g) {
    init(g);

    var xs = [upperLeft(g), upperRight(g), lowerRight(g), lowerLeft(g)];

    g.nodes().forEach(function(u) {
      var xArray = [];
      for (var i = 0; i < xs.length; ++i) {
        xArray.push(xs[i][u]);
      }
      xArray.sort();
      g.node(u).x = (xArray[1] + xArray[2]) / 2;
    });
  }
355768
private void postTraversalProcessing() {
		int nc1 = treeSize;
		info[KR] = new int[leafCount];
		info[RKR] = new int[leafCount];

		int lc = leafCount;
		int i = 0;

		// compute left-most leaf descendants
		// go along the left-most path, remember each node and assign to it the path's
		// leaf
		// compute right-most leaf descendants (in reversed postorder)
		for (i = 0; i < treeSize; i++) {
			if (paths[LEFT][i] == -1) {
				info[POST2_LLD][i] = i;
			} else {
				info[POST2_LLD][i] = info[POST2_LLD][paths[LEFT][i]];
			}
			if (paths[RIGHT][i] == -1) {
				info[RPOST2_RLD][treeSize - 1 - info[POST2_PRE][i]] =
						(treeSize - 1 - info[POST2_PRE][i]);
			} else {
				info[RPOST2_RLD][treeSize - 1 - info[POST2_PRE][i]] =
						info[RPOST2_RLD][treeSize - 1
								- info[POST2_PRE][paths[RIGHT][i]]];
			}
		}

		// compute key root nodes
		// compute reversed key root nodes (in revrsed postorder)
		boolean[] visited = new boolean[nc1];
		boolean[] visitedR = new boolean[nc1];
		Arrays.fill(visited, false);
		int k = lc - 1;
		int kR = lc - 1;
		for (i = nc1 - 1; i >= 0; i--) {
			if (!visited[info[POST2_LLD][i]]) {
				info[KR][k] = i;
				visited[info[POST2_LLD][i]] = true;
				k--;
			}
			if (!visitedR[info[RPOST2_RLD][i]]) {
				info[RKR][kR] = i;
				visitedR[info[RPOST2_RLD][i]] = true;
				kR--;
			}
		}

		// compute minimal key roots for every subtree
		// compute minimal reversed key roots for every subtree (in reversed postorder)
		int parent = -1;
		int parentR = -1;
		for (i = 0; i < leafCount; i++) {
			parent = info[KR][i];
			while (parent > -1 && info[POST2_MIN_KR][parent] == -1) {
				info[POST2_MIN_KR][parent] = i;
				parent = info[POST2_PARENT][parent];
			}
			parentR = info[RKR][i];
			while (parentR > -1 && info[RPOST2_MIN_RKR][parentR] == -1) {
				info[RPOST2_MIN_RKR][parentR] = i;
				parentR =
						info[POST2_PARENT][info[RPOST2_POST][parentR]]; // get parent's postorder
				if (parentR > -1) {
					parentR = treeSize - 1 - info[POST2_PRE][parentR]; // if parent exists get its
					// rev. postorder
				}
			}
		}
	}
321767
def accessibility(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    accessibility = {}        # Accessibility matrix

    # For each node i, mark each node j if that exists a path from i to j.
    for each in graph:
        access = {}
        # Perform DFS to explore all reachable nodes
        _dfs(graph, access, 1, each)
        accessibility[each] = list(access.keys())
    
    setrecursionlimit(recursionlimit)
    return accessibility
1113385
function visit(rootNodes, graph) {
    const result = {};
    const queue = rootNodes;
    rootNodes.forEach((node) => {
        result[node] = true;
    });
    while (queue.length > 0) {
        const el = queue.shift();
        const myEdges = graph[el] || [];
        myEdges.forEach((toNode) => {
            if (!result[toNode]) {
                result[toNode] = true;
                queue.push(toNode);
            }
        });
    }
    return result;
}
773514
private void dfs(Visitor visitor, int v, int[] cc, int id) {
        visitor.visit(v);
        cc[v] = id;
        for (int t = 0; t < n; t++) {
            if (graph[v][t] != 0.0) {
                if (cc[t] == -1) {
                    dfs(visitor, t, cc, id);
                }
            }
        }
    }
798702
public DiGraph<Vertex> reverseDiGraph() {
	final DiGraph<Vertex> origDiGraph = this;
	return new DiGraph<Vertex>() {
	    public Set<Vertex> getRoots() {
		return origDiGraph.vertices();
	    }
	    public BiDiNavigator<Vertex> getBiDiNavigator() {
		return
		    GraphUtil.<Vertex>reverseBiDiNavigator(origDiGraph.getBiDiNavigator());
	    }
	};
    }
452445
function dijkstra(graph, s) {
  const distance = {};
  const previous = {};
  const q = new PriorityQueue();
  // Initialize
  distance[s] = 0;
  graph.vertices.forEach(v => {
    if (v !== s) {
      distance[v] = Infinity;
    }
    q.insert(v, distance[v]);
  });

  let currNode;
  const relax = v => {
    const newDistance = distance[currNode] + graph.edge(currNode, v);
    if (newDistance < distance[v]) {
      distance[v] = newDistance;
      previous[v] = currNode;
      q.changePriority(v, distance[v]);
    }
  };
  while (!q.isEmpty()) {
    currNode = q.extract();
    graph.neighbors(currNode).forEach(relax);
  }
  return {
    distance,
    previous
  };
}
571382
private void bfs(int v, int[] cc, int id) {
        cc[v] = id;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        while (!queue.isEmpty()) {
            int t = queue.poll();
            for (Edge edge : graph[t]) {
                int i = edge.v2;
                if (!digraph && i == t) {
                    i = edge.v1;
                }

                if (cc[i] == -1) {
                    queue.offer(i);
                    cc[i] = id;
                }
            }
        }
    }
720708
public static <V> void removeVertices(DirectedGraph<V, DefaultEdge> graph, Set<V> vertices) {
        for (V vertex : vertices) {
            if (graph.containsVertex(vertex)) {
                graph.removeVertex(vertex);
            }
        }
    }
307743
def DFS_Tree(G):
    
    if not G.vertices:
        raise GraphInsertError("This graph have no vertices.")
    pred = {}
    T = digraph.DiGraph()
    vertex_data = DFS(G)
    for vertex in vertex_data:
        pred[vertex] = vertex_data[vertex][0]
    queue = Queue()
    for vertex in pred:
        if pred[vertex] == None:
            queue.put(vertex)
    while queue.qsize() > 0:
        current = queue.get()
        for element in pred:
            if pred[element] == current:
                T.add_edge(current, element)
                queue.put(element)
    return T
285846
def tarjan_recursif(graph):
    
    global sccp, waiting, dfs_time, dfs_num
    sccp = []
    waiting = []
    waits = [False] * len(graph)
    dfs_time = 0
    dfs_num = [None] * len(graph)

    def dfs(node):
        global sccp, waiting, dfs_time, dfs_num
        waiting.append(node)           # new node is waiting
        waits[node] = True
        dfs_num[node] = dfs_time       # mark visit
        dfs_time += 1
        dfs_min = dfs_num[node]        # compute dfs_min
        for neighbor in graph[node]:
            if dfs_num[neighbor] is None:
                dfs_min = min(dfs_min, dfs(neighbor))
            elif waits[neighbor] and dfs_min > dfs_num[neighbor]:
                dfs_min = dfs_num[neighbor]
        if dfs_min == dfs_num[node]:   # representative of a component
            sccp.append([])            # make a component
            while True:                # add waiting nodes
                u = waiting.pop()
                waits[u] = False
                sccp[-1].append(u)
                if u == node:          # until representative
                    break
        return dfs_min

    for node in range(len(graph)):
        if dfs_num[node] is None:
            dfs(node)
    return sccp
377999
def eulerian_tour_directed(graph):
    
    P = []
    Q = [0]
    R = []
    succ = [0] * len(graph)
    while Q:
        node = Q.pop()
        P.append(node)
        while succ[node] < len(graph[node]):
            neighbor = graph[node][succ[node]]
            succ[node] += 1
            R.append(neighbor)
            node = neighbor
        while R:
            Q.append(R.pop())
    return P