Eulerian tour on an undirected graph

       :param graph: directed graph in listlist format, cannot be listdict
       :assumes: graph is eulerian
       :returns: eulerian cycle as a vertex list
       :complexity: `O(|V|+|E|)`
176553
def eulerian_tour_undirected(graph):
    
    P = []
    Q = [0]
    R = []
    succ = [0] * len(graph)
    seen = [set() for _ in graph]
    while Q:
        node = Q.pop()
        P.append(node)
        while succ[node] < len(graph[node]):
            neighbor = graph[node][succ[node]]
            succ[node] += 1
            if neighbor not in seen[node]:
                seen[neighbor].add(node)
                R.append(neighbor)
                node = neighbor
        while R:
            Q.append(R.pop())
    return P
128163
def dominator_tree(graph):
    
    todo = Queue()
    done = set()
    dominator = Tree(None)
    nodes = list(graph.nodes)

    while True:
        # FIGURE OUT NET ITEM TO WORK ON
        if todo:
            node = todo.pop()
        elif nodes:
            node = nodes.pop()
            if len(nodes) % 1000 == 0:
                Log.note("{{num}} nodes remaining", num=len(nodes))
        else:
            break
        if node in done:
            continue

        parents = graph.get_parents(node) - {node}
        if not parents:
            # node WITHOUT parents IS A ROOT
            done.add(node)
            dominator.add_edge(Edge(ROOTS, node))
            continue

        not_done = parents - done
        if not_done:
            # THERE ARE MORE parents TO DO FIRST
            more_todo = not_done - todo
            if not more_todo:
                # ALL PARENTS ARE PART OF A CYCLE, MAKE node A ROOT
                done.add(node)
                dominator.add_edge(Edge(LOOPS, node))
            else:
                # DO THE PARENTS BEFORE node
                todo.push(node)
                for p in more_todo:
                    todo.push(p)
            continue

        # WE CAN GET THE DOMINATORS FOR ALL parents
        if len(parents) == 1:
            # SHORTCUT
            dominator.add_edge(Edge(list(parents)[0], node))
            done.add(node)
            continue

        paths_from_roots = [
            list(reversed(dominator.get_path_to_root(p)))
            for p in parents
        ]

        if any(p[0] is ROOTS for p in paths_from_roots):
            # THIS OBJECT CAN BE REACHED FROM A ROOT, IGNORE PATHS FROM LOOPS
            paths_from_roots = [p for p in paths_from_roots if p[0] is ROOTS]
            if len(paths_from_roots) == 1:
                # SHORTCUT
                dom = paths_from_roots[0][-1]
                dominator.add_edge(Edge(dom, node))
                done.add(node)
                continue

        # FIND COMMON PATH FROM root
        num_paths = len(paths_from_roots)
        for i, x in enumerate(zip_longest(*paths_from_roots)):
            if x.count(x[0]) != num_paths:
                dom = paths_from_roots[0][i-1]
                if dom is LOOPS:
                    # CAN BE REACHED FROM MORE THAN ONE LOOP, PICK ONE TO BLAME
                    dom = paths_from_roots[0][-1]
                break
        else:
            # ALL PATHS IDENTICAL
            dom = paths_from_roots[0][-1]

        dominator.add_edge(Edge(dom, node))
        done.add(node)

    return dominator
588645
def isa_from_graph(graph: nx.Graph, oneq_type='Xhalves', twoq_type='CZ') -> ISA:
    
    all_qubits = list(range(max(graph.nodes) + 1))
    qubits = [Qubit(i, type=oneq_type, dead=i not in graph.nodes) for i in all_qubits]
    edges = [Edge(sorted((a, b)), type=twoq_type, dead=False) for a, b in graph.edges]
    return ISA(qubits, edges)
419146
private void topologicalSortVisit(V n, List<V> L, Set<V> visited, LinkedHashSet<V> sequence) throws CycleException, EX {
		//    if n has not been visited yet then
		//        mark n as visited
		if(visited.add(n)) {
			//        for each node m with an edge from n to m do
			for(Edge<V> e : (isForward ? graph.getEdgesFrom(n) : graph.getEdgesTo(n))) {
				V m = isForward ? e.getTo() : e.getFrom();
				//            visit(m)
				if(!sequence.add(m)) {
					List<V> vertices = new ArrayList<>();
					boolean found = false;
					for(V seq : sequence) {
						if(!found && seq.equals(m)) found = true;
						if(found) vertices.add(seq);
					}
					vertices.add(m);
					throw new CycleException(AoCollections.optimalUnmodifiableList(vertices));
				}
				topologicalSortVisit(m, L, visited, sequence);
				sequence.remove(m);
			}
			//        add n to L
			L.add(n);
		}
	}
745059
def full_subgraph(self, vertices):
        
        subgraph_vertices = {v for v in vertices}
        subgraph_edges = {edge
                          for v in subgraph_vertices
                          for edge in self._out_edges[v]
                          if self._heads[edge] in subgraph_vertices}
        subgraph_heads = {edge: self._heads[edge]
                          for edge in subgraph_edges}
        subgraph_tails = {edge: self._tails[edge]
                          for edge in subgraph_edges}
        return DirectedGraph._raw(
            vertices=subgraph_vertices,
            edges=subgraph_edges,
            heads=subgraph_heads,
            tails=subgraph_tails,
        )
1216029
def _topo_sort(self, forward=True):
        
        topo_list = []
        queue = deque()
        indeg = {}

        # select the operation that will be performed
        if forward:
            get_edges = self.out_edges
            get_degree = self.inc_degree
            get_next = self.tail
        else:
            get_edges = self.inc_edges
            get_degree = self.out_degree
            get_next = self.head

        for node in self.node_list():
            degree = get_degree(node)
            if degree:
                indeg[node] = degree
            else:
                queue.append(node)

        while queue:
            curr_node = queue.popleft()
            topo_list.append(curr_node)
            for edge in get_edges(curr_node):
                tail_id = get_next(edge)
                if tail_id in indeg:
                    indeg[tail_id] -= 1
                    if indeg[tail_id] == 0:
                        queue.append(tail_id)

        if len(topo_list) == len(self.node_list()):
            valid = True
        else:
            # the graph has cycles, invalid topological sort
            valid = False

        return (valid, topo_list)
1261728
def inc_edges(self, node):
        
        try:
            return list(self.nodes[node][0])
        except KeyError:
            raise GraphError('Invalid node %s' % node)

        return None
1236558
def __get_cycle(graph, ordering, parent_lookup):
    """"""
    root_node = ordering[0]
    for i in range(2, len(ordering)):
        current_node = ordering[i]
        if graph.adjacent(current_node, root_node):
            path = []
            while current_node != root_node:
                path.append(current_node)
                current_node = parent_lookup[current_node]
            path.append(root_node)
            path.reverse()
            return path
930996
def get_igraph_from_adjacency(adjacency, directed=None):
    """"""
    import igraph as ig
    sources, targets = adjacency.nonzero()
    weights = adjacency[sources, targets]
    if isinstance(weights, np.matrix):
        weights = weights.A1
    g = ig.Graph(directed=directed)
    g.add_vertices(adjacency.shape[0])  # this adds adjacency.shap[0] vertices
    g.add_edges(list(zip(sources, targets)))
    try:
        g.es['weight'] = weights
    except:
        pass
    if g.vcount() != adjacency.shape[0]:
        logg.warn('The constructed graph has only {} nodes. '
                  'Your adjacency matrix contained redundant nodes.'
                  .format(g.vcount()))
    return g
598598
def transitive_reduction(self):
        
        combinations = []
        for node, edges in self.graph.items():
            combinations += [[node, edge] for edge in edges]

        while True:
            new_combinations = []
            for comb1 in combinations:
                for comb2 in combinations:
                    if not comb1[-1] == comb2[0]:
                        continue
                    new_entry = comb1 + comb2[1:]
                    if new_entry not in combinations:
                        new_combinations.append(new_entry)
            if not new_combinations:
                break
            combinations += new_combinations

        constructed = {(c[0], c[-1]) for c in combinations if len(c) != 2}
        for node, edges in self.graph.items():
            bad_nodes = {e for n, e in constructed if node == n}
            self.graph[node] = edges - bad_nodes
440477
def reverse(self):
        
        assert self.DIRECTED, "Undirected graph types such as %s cannot be reversed" % self.__class__.__name__
        
        N = self.__class__()
    
        #- Add the nodes
        N.add_nodes( n for n in self.nodes() )
    
        #- Add the reversed edges
        for (u, v) in self.edges():
            wt = self.edge_weight((u, v))
            label = self.edge_label((u, v))
            attributes = self.edge_attributes((u, v))
            N.add_edge((v, u), wt, label, attributes)
        return N
729868
def _dfs(vertex, vertices_neighbours):
    
    visited = set()
    to_visit = deque([vertex])
    while to_visit:
        vertex = to_visit.pop()
        if vertex not in visited:
            yield vertex
            visited.add(vertex)
            to_visit.extend(vertices_neighbours[vertex])
869630
function MultiGraph(List) {

			/**
    * O(1)
    */
			var Graph = function Graph() {

				this.V = new List();
				this.E = new List();
			};

			/**
    * O(1)
    */
			Graph.prototype.vadd = function () {

				var v = new Vertex(new List());

				v.iterator = this.V.push(v);

				return v;
			};

			/**
    * O(n) where n is the degree of v
    */
			Graph.prototype.vdel = function (v) {

				// remove all incident edges
				var _iteratorNormalCompletion13 = true;
				var _didIteratorError13 = false;
				var _iteratorError13 = undefined;

				try {
					for (var _iterator13 = this.iitr(v)[Symbol.iterator](), _step13; !(_iteratorNormalCompletion13 = (_step13 = _iterator13.next()).done); _iteratorNormalCompletion13 = true) {
						var e = _step13.value;
						this.edel(e);
					} // remove vertex
				} catch (err) {
					_didIteratorError13 = true;
					_iteratorError13 = err;
				} finally {
					try {
						if (!_iteratorNormalCompletion13 && _iterator13["return"]) {
							_iterator13["return"]();
						}
					} finally {
						if (_didIteratorError13) {
							throw _iteratorError13;
						}
					}
				}

				this.V.erase(v.iterator);
			};

			/**
    * O(1)
    */
			Graph.prototype.eadd = function (u, v) {

				var e = new Edge(u, v);

				// add to edge list
				e.iterator = this.E.push(e);

				// add to edge list of u
				e.uiterator = u.E.push(e);

				// add to edge list of v if u !== v
				if (u !== v) e.viterator = v.E.push(e);

				return e;
			};

			/**
    * O(1)
    */
			Graph.prototype.edel = function (e) {

				// remove from edge list
				this.E.erase(e.iterator);

				// remove from edge list of u
				e.u.E.erase(e.uiterator);

				// remove from edge list of v if u !== v
				if (e.u !== e.v) e.v.E.erase(e.viterator);
			};

			Graph.prototype.vitr = regeneratorRuntime.mark(function callee$3$0() {
				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							return context$4$0.delegateYield(this.V, "t0", 1);

						case 1:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this);
			});

			Graph.prototype.eitr = regeneratorRuntime.mark(function callee$3$0() {
				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							return context$4$0.delegateYield(this.E, "t0", 1);

						case 1:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this);
			});

			Graph.prototype.iitr = regeneratorRuntime.mark(function callee$3$0(v) {
				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							return context$4$0.delegateYield(v.E, "t0", 1);

						case 1:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this);
			});

			Graph.prototype.initr = Graph.prototype.iitr;
			Graph.prototype.outitr = Graph.prototype.iitr;

			Graph.prototype.nitr = regeneratorRuntime.mark(function callee$3$0(w) {
				var _iteratorNormalCompletion14, _didIteratorError14, _iteratorError14, _iterator14, _step14, _step14$value, u, v;

				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							_iteratorNormalCompletion14 = true;
							_didIteratorError14 = false;
							_iteratorError14 = undefined;
							context$4$0.prev = 3;
							_iterator14 = w.E[Symbol.iterator]();

						case 5:
							if (_iteratorNormalCompletion14 = (_step14 = _iterator14.next()).done) {
								context$4$0.next = 14;
								break;
							}

							_step14$value = _step14.value;
							u = _step14$value.u;
							v = _step14$value.v;
							context$4$0.next = 11;
							return u === w ? v : u;

						case 11:
							_iteratorNormalCompletion14 = true;
							context$4$0.next = 5;
							break;

						case 14:
							context$4$0.next = 20;
							break;

						case 16:
							context$4$0.prev = 16;
							context$4$0.t0 = context$4$0["catch"](3);
							_didIteratorError14 = true;
							_iteratorError14 = context$4$0.t0;

						case 20:
							context$4$0.prev = 20;
							context$4$0.prev = 21;

							if (!_iteratorNormalCompletion14 && _iterator14["return"]) {
								_iterator14["return"]();
							}

						case 23:
							context$4$0.prev = 23;

							if (!_didIteratorError14) {
								context$4$0.next = 26;
								break;
							}

							throw _iteratorError14;

						case 26:
							return context$4$0.finish(23);

						case 27:
							return context$4$0.finish(20);

						case 28:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this, [[3, 16, 20, 28], [21,, 23, 27]]);
			});

			Graph.prototype.dsitr = Graph.prototype.nitr;
			Graph.prototype.dpitr = Graph.prototype.nitr;

			Graph.prototype.vertices = Graph.prototype.vitr;

			Graph.prototype.edges = regeneratorRuntime.mark(function callee$3$0() {
				var _iteratorNormalCompletion15, _didIteratorError15, _iteratorError15, _iterator15, _step15, e;

				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							_iteratorNormalCompletion15 = true;
							_didIteratorError15 = false;
							_iteratorError15 = undefined;
							context$4$0.prev = 3;
							_iterator15 = this.eitr()[Symbol.iterator]();

						case 5:
							if (_iteratorNormalCompletion15 = (_step15 = _iterator15.next()).done) {
								context$4$0.next = 12;
								break;
							}

							e = _step15.value;
							context$4$0.next = 9;
							return [e.u, e.v, e];

						case 9:
							_iteratorNormalCompletion15 = true;
							context$4$0.next = 5;
							break;

						case 12:
							context$4$0.next = 18;
							break;

						case 14:
							context$4$0.prev = 14;
							context$4$0.t0 = context$4$0["catch"](3);
							_didIteratorError15 = true;
							_iteratorError15 = context$4$0.t0;

						case 18:
							context$4$0.prev = 18;
							context$4$0.prev = 19;

							if (!_iteratorNormalCompletion15 && _iterator15["return"]) {
								_iterator15["return"]();
							}

						case 21:
							context$4$0.prev = 21;

							if (!_didIteratorError15) {
								context$4$0.next = 24;
								break;
							}

							throw _iteratorError15;

						case 24:
							return context$4$0.finish(21);

						case 25:
							return context$4$0.finish(18);

						case 26:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this, [[3, 14, 18, 26], [19,, 21, 25]]);
			});

			Graph.prototype.incident = regeneratorRuntime.mark(function callee$3$0(v) {
				var _iteratorNormalCompletion16, _didIteratorError16, _iteratorError16, _iterator16, _step16, e;

				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							_iteratorNormalCompletion16 = true;
							_didIteratorError16 = false;
							_iteratorError16 = undefined;
							context$4$0.prev = 3;
							_iterator16 = this.iitr(v)[Symbol.iterator]();

						case 5:
							if (_iteratorNormalCompletion16 = (_step16 = _iterator16.next()).done) {
								context$4$0.next = 12;
								break;
							}

							e = _step16.value;
							context$4$0.next = 9;
							return [e.u, e.v, e];

						case 9:
							_iteratorNormalCompletion16 = true;
							context$4$0.next = 5;
							break;

						case 12:
							context$4$0.next = 18;
							break;

						case 14:
							context$4$0.prev = 14;
							context$4$0.t0 = context$4$0["catch"](3);
							_didIteratorError16 = true;
							_iteratorError16 = context$4$0.t0;

						case 18:
							context$4$0.prev = 18;
							context$4$0.prev = 19;

							if (!_iteratorNormalCompletion16 && _iterator16["return"]) {
								_iterator16["return"]();
							}

						case 21:
							context$4$0.prev = 21;

							if (!_didIteratorError16) {
								context$4$0.next = 24;
								break;
							}

							throw _iteratorError16;

						case 24:
							return context$4$0.finish(21);

						case 25:
							return context$4$0.finish(18);

						case 26:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this, [[3, 14, 18, 26], [19,, 21, 25]]);
			});

			Graph.prototype.ingoing = regeneratorRuntime.mark(function callee$3$0(v) {
				var _iteratorNormalCompletion17, _didIteratorError17, _iteratorError17, _iterator17, _step17, e;

				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							_iteratorNormalCompletion17 = true;
							_didIteratorError17 = false;
							_iteratorError17 = undefined;
							context$4$0.prev = 3;
							_iterator17 = this.initr(v)[Symbol.iterator]();

						case 5:
							if (_iteratorNormalCompletion17 = (_step17 = _iterator17.next()).done) {
								context$4$0.next = 12;
								break;
							}

							e = _step17.value;
							context$4$0.next = 9;
							return [e.u === v ? e.v : e.u, v, e];

						case 9:
							_iteratorNormalCompletion17 = true;
							context$4$0.next = 5;
							break;

						case 12:
							context$4$0.next = 18;
							break;

						case 14:
							context$4$0.prev = 14;
							context$4$0.t0 = context$4$0["catch"](3);
							_didIteratorError17 = true;
							_iteratorError17 = context$4$0.t0;

						case 18:
							context$4$0.prev = 18;
							context$4$0.prev = 19;

							if (!_iteratorNormalCompletion17 && _iterator17["return"]) {
								_iterator17["return"]();
							}

						case 21:
							context$4$0.prev = 21;

							if (!_didIteratorError17) {
								context$4$0.next = 24;
								break;
							}

							throw _iteratorError17;

						case 24:
							return context$4$0.finish(21);

						case 25:
							return context$4$0.finish(18);

						case 26:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this, [[3, 14, 18, 26], [19,, 21, 25]]);
			});

			Graph.prototype.outgoing = regeneratorRuntime.mark(function callee$3$0(v) {
				var _iteratorNormalCompletion18, _didIteratorError18, _iteratorError18, _iterator18, _step18, e;

				return regeneratorRuntime.wrap(function callee$3$0$(context$4$0) {
					while (1) switch (context$4$0.prev = context$4$0.next) {
						case 0:
							_iteratorNormalCompletion18 = true;
							_didIteratorError18 = false;
							_iteratorError18 = undefined;
							context$4$0.prev = 3;
							_iterator18 = this.outitr(v)[Symbol.iterator]();

						case 5:
							if (_iteratorNormalCompletion18 = (_step18 = _iterator18.next()).done) {
								context$4$0.next = 12;
								break;
							}

							e = _step18.value;
							context$4$0.next = 9;
							return [v, e.u === v ? e.v : e.u, e];

						case 9:
							_iteratorNormalCompletion18 = true;
							context$4$0.next = 5;
							break;

						case 12:
							context$4$0.next = 18;
							break;

						case 14:
							context$4$0.prev = 14;
							context$4$0.t0 = context$4$0["catch"](3);
							_didIteratorError18 = true;
							_iteratorError18 = context$4$0.t0;

						case 18:
							context$4$0.prev = 18;
							context$4$0.prev = 19;

							if (!_iteratorNormalCompletion18 && _iterator18["return"]) {
								_iterator18["return"]();
							}

						case 21:
							context$4$0.prev = 21;

							if (!_didIteratorError18) {
								context$4$0.next = 24;
								break;
							}

							throw _iteratorError18;

						case 24:
							return context$4$0.finish(21);

						case 25:
							return context$4$0.finish(18);

						case 26:
						case "end":
							return context$4$0.stop();
					}
				}, callee$3$0, this, [[3, 14, 18, 26], [19,, 21, 25]]);
			});

			Graph.prototype.endpoints = function (e) {

				return [e.u, e.v];
			};

			/**
    * O(1)
    */
			Graph.prototype.reverse = function () {};

			return Graph;
		}
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;
}
1220853
def laplacian_reordering(G):
  ''''''
  L = G.laplacian()
  vals, vecs = np.linalg.eigh(L)
  min_positive_idx = np.argmax(vals == vals[vals>0].min())
  vec = vecs[:, min_positive_idx]
  return permute_graph(G, np.argsort(vec))
158162
def _random_edge_iterator(graph, n_edges: int) -> Iterable[Tuple[BaseEntity, BaseEntity, int, Mapping]]:
    
    edges = list(graph.edges())
    edge_sample = random.sample(edges, n_edges)
    for u, v in edge_sample:
        keys = list(graph[u][v])
        k = random.choice(keys)
        yield u, v, k, graph[u][v][k]
908676
def _parse_loops_from_graph(self, graph):
        
        outtop = []
        outall = []
        for subg in networkx.strongly_connected_component_subgraphs(graph):
            if len(subg.nodes()) == 1:
                if len(list(subg.successors(list(subg.nodes())[0]))) == 0:
                    continue
            thisloop, allloops = self._parse_loop_graph(subg, graph)
            if thisloop is not None:
                outall += allloops
                outtop.append(thisloop)
        return outtop, outall