def make_strongly_connected(G):
    components = nx.strongly_connected_components(G)
    num_components = len(components)
    if num_components == 1:
        return G

    # for each connected component, connect one node to a node in
    # the successor component, and delete an edge to make up for it.
    # which edge to delete isn't trivial -- it only needs to be an edge
    # that is somehow redundant in terms of connecting the graph. Our
    # approach is to delete an edge at random, and keep trying until
    # either the graph is connected or we exhaust the number of tries.
    attempts = 0
    max_attempts = num_components * math.log2(num_components)
    while num_components > 1 and attempts < max_attempts:
        for index in range(num_components):
            source_comp = components[index]
            target_comp = components[(index+1) % num_components]

            # pick a random vertex from the source component and connect it
            # to a vertex in the target component, deleting one of the outgoing
            # edges from the source vertex to keep the degree constant
            source_vertex = source_comp[npr.randint(len(source_comp))]
            target_vertex = target_comp[npr.randint(len(target_comp))]
            source_edges = list(G[source_vertex].keys())
            G.remove_edge(source_vertex, source_edges[npr.randint(len(source_edges))])
            G.add_edge(source_vertex, target_vertex)
        components = nx.strongly_connected_components(G)
        num_components = len(components)
        attempts += 1
    return G

    def _check_graph(self, out_stream=sys.stdout):
        # Cycles in group w/o solver
        cgraph = self.root._relevance._cgraph
        for grp in self.root.subgroups(recurse=True, include_self=True):
            path = [] if not grp.pathname else grp.pathname.split('.')
            graph = cgraph.subgraph([n for n in cgraph if n.startswith(grp.pathname)])
            renames = {}
            for node in graph.nodes_iter():
                renames[node] = '.'.join(node.split('.')[:len(path)+1])
                if renames[node] == node:
                    del renames[node]

            # get the graph of direct children of current group
            nx.relabel_nodes(graph, renames, copy=False)

            # remove self loops created by renaming
            graph.remove_edges_from([(u,v) for u,v in graph.edges()
                                         if u==v])

            strong = [s for s in nx.strongly_connected_components(graph)
                        if len(s)>1]

            if strong and isinstance(grp.nl_solver, RunOnce): # no solver, cycles BAD
                relstrong = []
                for slist in strong:
                    relstrong.append([])
                    for s in slist:
                        relstrong[-1].append(name_relative_to(grp.pathname, s))
                        relstrong[-1] = sorted(relstrong[-1])
                print("Group '%s' has the following cycles: %s" %
                     (grp.pathname, relstrong), file=out_stream)

            # Components/Systems/Groups are not in the right execution order
            subnames = [s.pathname for s in grp.subsystems()]
            while strong:
                # break cycles to check order
                lsys = [s for s in subnames if s in strong[0]]
                for p in graph.predecessors(lsys[0]):
                    if p in lsys:
                        graph.remove_edge(p, lsys[0])
                strong = [s for s in nx.strongly_connected_components(graph)
                            if len(s)>1]

            visited = set()
            out_of_order = set()
            for sub in grp.subsystems():
                visited.add(sub.pathname)
                for u,v in nx.dfs_edges(graph, sub.pathname):
                    if v in visited:
                        out_of_order.add(v)

            if out_of_order:
                print("In group '%s', the following subsystems are out-of-order: %s" %
                      (grp.pathname, sorted([name_relative_to(grp.pathname, n)
                                                for n in out_of_order])), file=out_stream)

    def find_cut_dfg(self, dfg):
        condensed_graph_1 = nx.DiGraph()
        for scc in nx.strongly_connected_components(dfg):
            condensed_graph_1.add_node(tuple(scc))
        for edge in dfg.edges():
            sccu = None
            sccv = None
            u = edge[0]
            for scc in nx.strongly_connected_components(dfg):
                if u in scc:
                    sccu = tuple(scc)
            v = edge[1]
            for scc in nx.strongly_connected_components(dfg):
                if v in scc:
                    sccv = tuple(scc)
            if sccv != sccu:
                condensed_graph_1.add_edge(sccu, sccv)
        xor_graph = nx.DiGraph()
        xor_graph.add_nodes_from(condensed_graph_1)
        scr1 = CutFinderIMSequenceReachability(condensed_graph_1)

        for node in condensed_graph_1.nodes():
            reachable_from_to = scr1.get_reachable_from_to(node)
            not_reachable = set(condensed_graph_1.nodes()).difference(reachable_from_to)
            if node in not_reachable:
                not_reachable.remove(node)
            for node2 in not_reachable:
                xor_graph.add_edge(node, node2)
        condensed_graph_2 = nx.DiGraph()
        for n in nx.strongly_connected_components(xor_graph):
            r = set()
            for s in n:
                r.update(s)
            condensed_graph_2.add_node(tuple(r))
        for edge in condensed_graph_1.edges():
            sccu = None
            sccv = None
            u = edge[0]
            for scc in condensed_graph_2.nodes():
                if u[0] in scc:
                    sccu = tuple(scc)
            v = edge[1]
            for scc in condensed_graph_2.nodes():
                if v[0] in set(scc):
                    sccv = tuple(scc)
            if sccv != sccu:
                condensed_graph_2.add_edge(tuple(sccu), tuple(sccv))
        self.scr2 = CutFinderIMSequenceReachability(condensed_graph_2)
        result = []
        result.extend(set(condensed_graph_2.nodes()))
        result.sort(self.compare)
        return Cut(Operator.sequence, result)

 def directed_stats(self):
     #   UG = nx.to_undirected(g) #claims to not have this function     
     if nx.is_strongly_connected(g): 
         sconl = nx.strongly_connected_components(g)
     else: sconl = 'NA - graph is not strongly connected'
     result = {#"""returns boolean"""
         'scon': nx.is_strongly_connected(g), 
         'sconn': nx.number_connected_components(g),
         # """returns boolean"""        
         'dag': nx.is_directed_acyclic_graph(g),
         # """returns lists"""
         'sconl': nx.strongly_connected_components(g),
         #Conl = connected_component_subgraphs(Ug)
         }
     return result

    def find_widening_points(function_addr, function_endpoints, graph):  # pylint: disable=unused-argument
        """
        Given a local transition graph of a function, find all widening points inside.

        Correctly choosing widening points is very important in order to not lose too much information during static
        analysis. We mainly consider merge points that has at least one loop back edges coming in as widening points.

        :param int function_addr: Address of the function.
        :param list function_endpoints: Endpoints of the function, typically coming from Function.endpoints.
        :param networkx.DiGraph graph: A local transition graph of a function, normally Function.graph.
        :return: A list of addresses of widening points.
        :rtype: list
        """

        sccs = networkx.strongly_connected_components(graph)

        widening_addrs = set()

        for scc in sccs:
            if len(scc) == 1:
                node = next(iter(scc))
                if graph.has_edge(node, node):
                    # self loop
                    widening_addrs.add(node.addr)
            else:
                for n in scc:
                    predecessors = graph.predecessors(n)
                    if any([p not in scc for p in predecessors]):
                        widening_addrs.add(n.addr)
                        break

        return list(widening_addrs)

def _high_degree_components(G, k):
    """Helper for filtering components that can't be k-edge-connected.

    Removes and generates each node with degree less than k.  Then generates
    remaining components where all nodes have degree at least k.
    """
    # Iteravely remove parts of the graph that are not k-edge-connected
    H = G.copy()
    singletons = set(_low_degree_nodes(H, k))
    while singletons:
        # Only search neighbors of removed nodes
        nbunch = set(it.chain.from_iterable(map(H.neighbors, singletons)))
        nbunch.difference_update(singletons)
        H.remove_nodes_from(singletons)
        for node in singletons:
            yield {node}
        singletons = set(_low_degree_nodes(H, k, nbunch))

    # Note: remaining connected components may not be k-edge-connected
    if G.is_directed():
        for cc in nx.strongly_connected_components(H):
            yield cc
    else:
        for cc in nx.connected_components(H):
            yield cc

 def test_null_graph(self):
     G = nx.DiGraph()
     assert_equal(list(nx.strongly_connected_components(G)), [])
     assert_equal(list(nx.kosaraju_strongly_connected_components(G)), [])
     assert_equal(list(nx.strongly_connected_components_recursive(G)), [])
     assert_equal(len(nx.condensation(G)), 0)
     assert_raises(nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph())

def plot_abstraction_scc(ab, ax=None):
    """Plot Regions colored by strongly connected component.
    
    Handy to develop new examples or debug existing ones.
    """
    ppp = ab.ppp
    ts = ab.ts
    ppp2ts = ab.ppp2ts
    
    # each connected component of filtered graph is a symbol
    components = nx.strongly_connected_components(ts)
    
    if ax is None:
        ax = mpl.pyplot.subplot()
    
    l, u = ab.ppp.domain.bounding_box
    ax.set_xlim(l[0,0], u[0,0])
    ax.set_ylim(l[1,0], u[1,0])
    
    for component in components:
        # map to random colors
        red = np.random.rand()
        green = np.random.rand()
        blue = np.random.rand()
        
        color = (red, green, blue)
        
        for state in component:
            i = ppp2ts.index(state)
            ppp[i].plot(ax=ax, color=color)
    return ax

def process(filename):  
    clauses, literalCount = read(filename)  
  
    G=nx.DiGraph()  
    G.add_nodes_from(range(1, literalCount + 1) + range(-literalCount, 0))  
  
    for clause in clauses:  
        G.add_edge(-clause[0], clause[1])  
        G.add_edge(-clause[1], clause[0])  
  
    print "Graph creation for %s completed" % filename  
  
    components = nx.strongly_connected_components(G)  
  
    print "Calculation of SSC for %s completed" % filename  
  
    isSatisfiable = True  
    for component in filter(lambda component : len(component) > 1, components):  
        isSatisfiableComponent = True  
        vertexes = set()  
        for vertex in component:  
            if -vertex in vertexes:  
                isSatisfiableComponent = False  
                break  
            vertexes.add(vertex)  
        if not isSatisfiableComponent:  
            isSatisfiable = False  
            break  
  
    print "%s satisfiable result: %s" % (filename, isSatisfiable)  
    return isSatisfiable  

def stg2htg(STG):
	"""
	Computes the HTG of the *STG*. For a definition see :ref:`Berenguier2013 <Berenguier2013>`.

	**arguments**:
		* *STG*: state transition graph

	**returns**:
		* *HTG* (networkx.DiGraph): the HTG of *STG*

	**example**::

		>>> htg = stg2htg(stg)
	"""

	graph = networkx.DiGraph()
	graph.graph["node"] = {"color":"none"}

	sccs = []
	cascades = []
	attractors = []
	for x in networkx.strongly_connected_components(STG):
		x=tuple(sorted(x))
		if len(x)>1 or STG.has_edge(x[0],x[0]):
			sccs.append(x)
			suc = PyBoolNet.Utility.DiGraphs.successors(STG,x)
			if set(suc)==set(x):
				attractors.append(x)
		else:
			cascades+= x

	graph.add_nodes_from(sccs, style="filled", fillcolor="lightgray", shape="rect")

	sigma = {}
	for x in cascades:
		pattern = []
		for i, A in enumerate(sccs):
			if PyBoolNet.Utility.DiGraphs.has_path(STG,x,A):
				pattern.append(i)
		pattern = tuple(pattern)

		if not pattern in sigma:
			sigma[pattern] = []
		sigma[pattern].append(x)

	I = [tuple(sorted(x)) for x in sigma.values()]
	graph.add_nodes_from(I)

	for X in graph.nodes():
		for Y in graph.nodes():
			if X==Y: continue

			if PyBoolNet.Utility.DiGraphs.has_edge(STG,X,Y):
				graph.add_edge(X,Y)

	for node in graph.nodes():
		lines = [",".join(x) for x in PyBoolNet.Utility.Misc.divide_list_into_similar_length_lists(node)]
		graph.node[node]["label"]="<%s>"%",<br/>".join(lines)

	return graph

    def scc_dicts(self) :
        """
        bestimmt SCCs und gibt dictionary Knoten>SCC und SCC>[Knoten] zurueck
        SCCs, die nur aus einem Element bestehen, welches kein Attraktor (= nicht in attr)
        ist, werden in SCC 0 verschoben und tauchen in node2scc nicht auf
        """
        if not self._attrs :
             self._attrs = nx.attracting_components(self.stg())
        sccs=nx.strongly_connected_components(self.stg()) # erzeugt Liste SCC>[Knoten]
        node2scc={}
        scc2nodes={}
        attr_flattened=[item for sublist in [list(x) for x in self._attrs] for item in sublist]
        # Liste durchgehen und a) fuer jeden Knoten SCC und b) fuer jede SCC Knoten speichern
        for (i,nodes) in enumerate(sccs):
            for node in nodes:

                # pruefen, ob Knoten in trivialem SCC liegt und kein Attraktor ist
                if len(nodes)<=1 and (node not in attr_flattened):
                    scc_index=0 # in diesem Fall wird Knoten in SCC 0 verschoben
                else:
                    # ansonsten entspricht die SCC-Nummer dem Index+1
                    # +1, damit Index 0 fuer Sammlung trivialer SCCs zur Verfuegung steht
                    scc_index=i+1

                    node2scc[node]=scc_index # dictionary Knoten>SCC schreiben

                if scc_index not in scc2nodes: # pruefen, ob SCC bereits in dictionary SCC>[Knoten] vorhanden ist
                    scc2nodes[scc_index]=[] # ggf. Eintrag erstellen
                scc2nodes[scc_index].append(node) # und aktuellen Knoten hinzufuegen

        return(node2scc,scc2nodes,sccs)

def attracting_components(G):
    """Generates a list of attracting components in `G`.

    An attracting component in a directed graph `G` is a strongly connected
    component with the property that a random walker on the graph will never
    leave the component, once it enters the component.

    The nodes in attracting components can also be thought of as recurrent
    nodes.  If a random walker enters the attractor containing the node, then
    the node will be visited infinitely often.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attractors : generator of sets
        A generator of sets of nodes, one for each attracting component of G.

    See Also
    --------
    number_attracting_components
    is_attracting_component 
    attracting_component_subgraphs

    """
    scc = list(nx.strongly_connected_components(G))
    cG = nx.condensation(G, scc)
    for n in cG:
        if cG.out_degree(n) == 0:
            yield scc[n]

def netstats_listsdi(graph):
    G = graph
 #   UG = nx.to_undirected(G) #claims to not have this function     
    if nx.is_strongly_connected(G): 
        sconl = nx.strongly_connected_components(G)
    else: sconl = 'NA - graph is not strongly connected'
    result = {#"""returns boolean"""
              'scon': nx.is_strongly_connected(G), 
              'sconn': nx.number_connected_components(G),
             # """returns boolean"""        
              'dag': nx.is_directed_acyclic_graph(G),
             # """returns lists"""
              'sconl': nx.strongly_connected_components(G),
#              Conl = connected_component_subgraphs(UG)
              }
    return result    

    def updateSCCs(self, transitions):
        '''Updates the subgraphs and SCCs associated with each pair in the
        acceptance set.
        
        Note: Assumes that all transitions correspond to a single TS transition.
        '''
        # process transitions and update SCCs based on intersection probabilities
        for k, subg in enumerate(self.pa.subgraphs):
            # check if any of the transitions intersect the k-th bad set
            if all([(d['sat'][k][1] == 0) for _, _, d in transitions]):
                sub_trans = [(u, v, {'prob': d['prob']})
                                                    for u, v, d in transitions]
                subg.add_edges_from(sub_trans) # add all transitions to subgraph
                good_trans = [(u, v) for u, v, d in transitions
                                         if d['sat'][k][0] > 0]
                self.pa.good_transitions[k].extend(good_trans)
#         for u, v, d in transitions: #TODO: check this
#             for k, pathProb in enumerate(d['sat']):
#                 if not pathProb[1]: # does not intersect the bad set
#                     self.pa.subgraphs[k].add_edge(u, v, prob=d['prob'])
#                 if pathProb[0]: # intersects the good set, save it
#                     self.pa.good_transitions[k].append((u, v))
        # update SCCs
        for k, subg in enumerate(self.pa.subgraphs): #TODO: check this
            self.pa.sccs[k] = map(tuple, nx.strongly_connected_components(subg))
        # compute good SCCs
        self.pa.good_sccs = [set() for _ in self.rabin.final]
        for trs, sccs, gsccs in it.izip(self.pa.good_transitions, self.pa.sccs, self.pa.good_sccs):
            for u, v in trs:
                gsccs.update(tuple([scc for scc in sccs if (u in scc) and (v in scc)]))

def find_outdag(IGraph):
	"""
	Finds the maximal directed acyclic subgraph that is closed under the successors operation.
	Essentially, these components are the "output cascades" which can be exploited by various algorithms, e.g.
	the computation of basins of attraction.

	**arguments**:
		* *IGraph*: interaction graph

	**returns**:
		* *Names* (list): the outdag

	**example**::

		>>> find_outdag(igraph)
		['v7', 'v8', 'v9']
	"""

	graph = IGraph.copy()

	sccs = networkx.strongly_connected_components(graph)
	sccs = [list(x) for x in sccs]
	candidates = [scc[0] for scc in sccs if len(scc)==1]
	candidates = [x for x in candidates if not graph.has_edge(x,x)]
	sccs = [scc for scc in sccs if len(scc)>1 or graph.has_edge(scc[0],scc[0])]

	graph.add_node("!")
	for scc in sccs:
		graph.add_edge(scc[0],"!")

	outdags = [x for x in candidates if not networkx.has_path(graph,x,"!")]

	return outdags

def demo_rgud():
    R = np.asarray([[ 1.0,  0.4, -0.4],
                    [ 0.4,  1.0,  0.6],
                    [-0.4,  0.6,  1.0]])
    
    nstates = 50
    nactions = 2
    mu = [100.0] * 3
    sigma = [10.0] * 3
    cov = cor2cov(R, sigma)
    rewards = mvnrewards(nstates, nactions, mu, cov)
    G = rgud(nstates, nactions)
    cc = nx.strongly_connected_components(G)
    G2 = make_strongly_connected(G)
    cc2 = nx.strongly_connected_components(G2)
    return (G, G2, cc, cc2)

def has_large_scc_in_substance_graph(f, sc):
    # f: fragment
    # sc: subgraph components in fragment 'f'

    # tells you if fragment 'f' has strongly-connected component of length greater than one in corresponding directed graph induced by paths in sc
    # this should tell you if fragment f contains subgraphs that have at least one cycle of length greater than one
    
    substance_edges_in_paths = set()
    for key in sc.keys():
        for path in sc[key]['n_paths']+sc[key]['p_paths']:
            # 
            curr_edge = (path[0],path[2])
#            if curr_edge not in substance_edges_in_paths:
            substance_edges_in_paths.add(curr_edge)
    substance_edges_in_paths = list(substance_edges_in_paths)

    substance_graph = nx.DiGraph()
    substance_graph.add_edges_from(substance_edges_in_paths)

    strong_comp = nx.strongly_connected_components(substance_graph)

    if max([len(el) for el in strong_comp]) > 1:
        # strongly-connected component of size > 1 detected in directed substance graph
        return True
    else:
        # all strongly-connected components are individual substance nodes
        return False

def lesion_met_largest_strong_component(G, orig_order=None):
    """
    Get largest strong component size of a graph.

    Parameters
    ----------
    G : directed networkx graph
        Graph to compute largest component for
    orig_order : int
        Define orig_order if you'd like the largest component proportion

    Returns
    -------
    largest strong component size : int
        Proportion of largest remaning component size if orig_order
        is defined. Otherwise, return number of nodes in largest component.
    """

    components = sorted(nx.strongly_connected_components(G), key=len,
                        reverse=True)
    if len(components) > 0:
        largest_component = len(components[0])
    else:
        largest_component = 0.

    # Check if original component size is defined
    if orig_order is not None:
        return largest_component / float(orig_order)
    else:
        return largest_component

def get_paths_in_scc(f, sc):
    # f: fragment
    # sc: subgraph components in fragment 'f'

    # returns list of those paths that are part of at least one 'large' strongly-connected component
    # i.e. only those paths are returned that are part of an scc of length > 1

    substance_edges_in_paths = set()
    for key in sc.keys():
        for path in sc[key]['n_paths']+sc[key]['p_paths']:
            curr_edge = (path[0],path[2])
#            if curr_edge not in substance_edges_in_paths:
            substance_edges_in_paths.add(curr_edge)
    substance_edges_in_paths = list(substance_edges_in_paths)

    substance_graph = nx.DiGraph()
    substance_graph.add_edges_from(substance_edges_in_paths)

    strong_comp = nx.strongly_connected_components(substance_graph)

    # collect paths for return
    n_paths = set()
    p_paths = set()
    count = 0
    for scc in strong_comp:
        if len(scc) > 1:
            for substance in scc:
                for path in sc[substance]['n_paths']:
                    n_paths.add(path)
                    count = count + 1
                for path in sc[substance]['p_paths']:
                    p_paths.add(path)
                    count = count + 1
    # return
    return {'n_paths': list(n_paths), 'p_paths': list(p_paths), 'count': count}

def attracting_components(G):
    """Returns a list of attracting components in `G`.

    An attracting component in a directed graph `G` is a strongly connected
    component with the property that a random walker on the graph will never
    leave the component, once it enters the component.

    The nodes in attracting components can also be thought of as recurrent
    nodes.  If a random walker enters the attractor containing the node, then
    the node will be visited infinitely often.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attractors : list
        The list of attracting components, sorted from largest attracting
        component to smallest attracting component.

    See Also
    --------
    number_attracting_components
    is_attracting_component 
    attracting_component_subgraphs

    """
    scc = nx.strongly_connected_components(G)
    cG = nx.condensation(G, scc)
    attractors = [scc[n] for n in cG if cG.out_degree(n) == 0]
    attractors.sort(key=len,reverse=True)
    return attractors