Return True if the directed graph g has a cycle. The directed graph
    should be represented as a dictionary mapping of edges for each node.
188155
def is_cyclic(graph):
    
    path = set()

    def visit(vertex):
        path.add(vertex)
        for neighbour in graph.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in graph)
505632
public function hasCycle()
    {
        $components = new ConnectedComponents($this->graph);
        if ($components->isSingle()) {
            $alg = new Degree($this->graph);

            foreach ($this->graph->getVertices() as $vertex) {
                // uneven degree => fail
                if ($alg->getDegreeVertex($vertex) & 1) {
                    return false;
                }
            }

            return true;
        }

        return false;
    }
133562
def __get_segments_from_cycle(graph, cycle_path):
    """"""
    list_of_segments = []
    # We work through the cycle in a bottom-up fashion
    for n in cycle_path[::-1]:
        segments = __get_segments_from_node(n, graph)
        if segments:
            list_of_segments.append(segments)

    return list_of_segments
1142710
def _get_connected_components_adjacency(self, graph, counts):
        ''' '''

        found = set()
        components = list()

        for node in sorted(graph, key=lambda x: counts[x], reverse=True):
            if node not in found:
                # component = self.search(node, graph)
                component = breadth_first_search(node, graph)
                found.update(component)
                components.append(component)
        return components
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
619931
def topological_order_dfs(graph):
    
    n = len(graph)
    order = []
    times_seen = [-1] * n
    for start in range(n):
        if times_seen[start] == -1:
            times_seen[start] = 0
            to_visit = [start]
            while to_visit:
                node = to_visit[-1]
                children = graph[node]
                if times_seen[node] == len(children):
                    to_visit.pop()
                    order.append(node)
                else:
                    child = children[times_seen[node]]
                    times_seen[node] += 1
                    if times_seen[child] == -1:
                        times_seen[child] = 0
                        to_visit.append(child)
    return order[::-1]
546464
def graph_from_incidence_matrix(matrix, node_prefix='', directed=False):
    

    if directed:
        graph = Dot(graph_type='digraph')
    else:
        graph = Dot(graph_type='graph')

    for row in matrix:
        nodes = []
        c = 1

        for node in row:
            if node:
                nodes.append(c * node)
            c += 1

        nodes.sort()

        if len(nodes) == 2:
            graph.add_edge(
                Edge(
                    node_prefix + abs(nodes[0]),
                    node_prefix + nodes[1]))

    if not directed:
        graph.set_simplify(True)

    return graph
71559
def reduce_to_cycles(self):
        
        if not self._reduced:
            reduced = copy(self)
            reduced.objects = self.objects[:]
            reduced.metadata = []
            reduced.edges = []
            self.num_in_cycles = reduced._reduce_to_cycles()
            reduced.num_in_cycles = self.num_in_cycles
            if self.num_in_cycles:
                reduced._get_edges()
                reduced._annotate_objects()
                for meta in reduced.metadata:
                    meta.cycle = True
            else:
                reduced = None
            self._reduced = reduced
        return self._reduced
868274
public function isTriangle()
    {
        // exactly 3 (implicitly distinct) edges
        return (count($this->walk->getEdges()) === 3 &&
                // exactly three distinct vertices
                count($this->walk->getVertices()->getVerticesDistinct()) === 3 &&
                // this is actually a cycle
                $this->isCycle());
    }
1283663
def connected(self):
        
        node_list = self.node_list()
        for node in node_list:
            bfs_list = self.forw_bfs(node)
            if len(bfs_list) != len(node_list):
                return False
        return True
233233
def get_graph(self, parse_direction=False):
        
        g = nx.DiGraph()

        for way_id, (tags, nodes) in self.ways.items():
            # If oneway is '-1', reverse the way and treat as a normal oneway
            if tags.get('oneway') == '-1':
                nodes = reversed(nodes)
                tags['oneway'] = 'yes'
            oneway = tags.get('oneway') == 'yes'

            for n0, n1 in tools.pairwise(nodes):
                g.add_edge(n0, n1, attr_dict=tags)
                if parse_direction:
                    g[n0][n1]['_direction'] = 'forward'
                if not oneway:
                    g.add_edge(n1, n0, attr_dict=tags)
                    if parse_direction:
                        g[n1][n0]['_direction'] = 'backward'

                g.node[n0].update(self._node_properties(n0))
            g.node[n1].update(self._node_properties(n1))

        return g
498798
public static boolean isConstantMsg(int edge, FactorGraph fg) {
        BipartiteGraph<Var,Factor> bg = fg.getBipgraph();
        int numNbs = bg.isT1T2(edge) ? bg.numNbsT1(bg.parentE(edge)) : bg.numNbsT2(bg.parentE(edge)); 
        return numNbs == 1;
    }
1044061
public boolean isAcyclic() {

		// Tarjan's algorithm to detect strongly connected componenent of a graph
		final AbstractJobVertex[] reachable = getAllReachableJobVertices();
		final HashMap<AbstractJobVertex, Integer> indexMap = new HashMap<AbstractJobVertex, Integer>();
		final HashMap<AbstractJobVertex, Integer> lowLinkMap = new HashMap<AbstractJobVertex, Integer>();
		final Stack<AbstractJobVertex> stack = new Stack<AbstractJobVertex>();
		final Integer index = Integer.valueOf(0);

		for (int i = 0; i < reachable.length; i++) {
			if (!indexMap.containsKey(reachable[i])) {
				if (!tarjan(reachable[i], index, indexMap, lowLinkMap, stack)) {
					return false;
				}
			}
		}

		return true;
	}
1066712
def cycle_cut(self, cycle_len_thresh=12, directed=False, copy=True):
    '''
    '''
    symmetric = not directed
    adj = self.kernelize('binary').matrix('csr', 'dense', copy=True)
    if symmetric:
      adj = adj + adj.T

    removed_edges = []
    while True:
      c = _atomic_cycle(adj, cycle_len_thresh, directed=directed)
      if c is None:
        break
      # remove edges in the cycle
      ii, jj = c.T
      adj[ii,jj] = 0
      if symmetric:
        adj[jj,ii] = 0
      removed_edges.extend(c)

    #XXX: if _atomic_cycle changes, may need to do this on each loop
    if ss.issparse(adj):
      adj.eliminate_zeros()

    # select only the necessary cuts
    ii, jj = _find_cycle_inducers(adj, removed_edges, cycle_len_thresh,
                                  directed=directed)
    # remove the bad edges
    return self.remove_edges(ii, jj, symmetric=symmetric, copy=copy)
894797
def is_valid(self):
        
        if len(self.geometry) == 0:
            return True

        try:
            referenced = {self.graph[i][1]
                          for i in self.graph.nodes_geometry}
        except BaseException:
            # if connectivity to world frame is broken return false
            return False

        # every geometry is referenced
        ok = referenced == set(self.geometry.keys())

        return ok
450063
public Map relevantCycles() {
        Map result = new HashMap();
        //minimize();

        for (SimpleCycleBasis subgraphBase : subgraphBases) {
            SimpleCycleBasis cycleBasis = subgraphBase;
            result.putAll(cycleBasis.relevantCycles());
        }

        return result;
    }
145444
def build_cycle_graph(num_nodes):
    """"""
    graph = UndirectedGraph()

    if num_nodes > 0:
        first_node = graph.new_node()
        if num_nodes > 1:
            previous_node = first_node
            for _ in range(num_nodes - 1):
                new_node = graph.new_node()
                graph.new_edge(previous_node, new_node)
                previous_node = new_node
            graph.new_edge(previous_node, first_node)

    return graph