def exp_10():
  net = MinTTTLagrangianCTMProblem.load("/Users/jdr/Desktop/out.json")
  net.cache_props()
  print len(net.sources)
  print len(net.sinks)
  print len(net.all_routes())
  print len(net.get_links())
  # for route in net.all_routes():
  #   print net.max_flow(route), net.ff_travel_time(route)
  import networkx
  print networkx.is_weakly_connected(net)
  with open('/Users/jdr/Desktop/flowdata.csv','r') as fn:
    flows = {}
    for row in fn:
      splits = row[:-1].split(';')
      print splits
      name = splits[2]
      flow = float(splits[1])
      density = float(splits[0])
      flows[name] = {
        'flow': flow,
        'density': density
      }
  def get_flows(link):
    try:
      return flows[link.name]['flow']
    except:
      return 0.0
  for junction in net.junctions:
    lsum = sum(get_flows(link) for link in junction.in_links)
    rsum = sum(get_flows(link) for link in junction.out_links)
    print lsum, rsum
  for link in net.get_links():
    print bool(link.fd.q_max < get_flows(link)), link.fd.q_max, get_flows(link)

def subgraphs_product(G1, G2, length):
    assert length <= len(G1.nodes())
    assert length <= len(G2.nodes())

    a = it.combinations(G1.nodes(), length)
    b = it.combinations(G2.nodes(), length)
    gen = it.product(a, b)

    for pair in gen:
        sub1 = G1.subgraph(pair[0])
        sub2 = G2.subgraph(pair[1])
        if nx.is_weakly_connected(sub1) and nx.is_weakly_connected(sub2):
            yield (sub1, sub2)

def evaluate(graph):
    """evaluate(Graph) -> None

    :class:`Graph` -> IO ()

    Starting from the root node, evaluate the branches.
    The graph nodes are updated in-place.

    Example:

    >>> @delayed()
    ... def foo(a):
    ...   return a
    >>> node = foo(42) & foo(24)
    >>> print evaluate(node.graph)
    None
    >>> for _, data in node.graph.nodes(data=True):
    ...   n = data['node']
    ...   print n.name, n.result.result()
    & None
    foo 42
    foo 24
    """

    assert nx.is_weakly_connected(graph)
    node = find_root_node(graph)
    node.eval()

    def connected(self):
        """
        Test if the graph is connected.

        Return True if connected, False otherwise
        """
        return nx.is_weakly_connected(self.G)

def gen_network(graph,machines,basedata):
    """ Generates an LLD network from a graph
        distributing participants in a list of machines
    """
    network = ET.Element('network')
    #network.set('type',graphtype)
    network.set('participants',str(graph.number_of_nodes()))
    network.set('edges',str(graph.size()))
    network.set('density',str(NX.density(graph)))

    network.set('connected',str(NX.is_weakly_connected(graph)))
    network.set('stronglyconnected',str(NX.is_strongly_connected(graph)))

    for node in graph.nodes_iter():
        nodelement = ET.SubElement(network,'participant')
        nodelement.set('id','participant'+str(node))
        hostelem = ET.SubElement(nodelement,'host')
        #hostelem.text = 'node'+str(int(node) % len(machines))
        hostelem.text = machines[int(node) % len(machines)]
        portelem = ET.SubElement(nodelement,'port')
        portelem.text = str(20500+int(node))
        baseelem = ET.SubElement(nodelement,'basedata')
        baseelem.text = basedata
        nodelement.append(gen_dynamic())
        for source in gen_sources(graph,node):
            nodelement.append(source)
    return network

def draw_graph(nodes, edges, graphs_dir, default_lang='all'):
    lang_graph = nx.MultiDiGraph()
    lang_graph.add_nodes_from(nodes)
    for edge in edges:
        if edges[edge] == 0:
            lang_graph.add_edge(edge[0], edge[1])
        else:
            lang_graph.add_edge(edge[0], edge[1], weight=float(edges[edge]), label=str(edges[edge]))

    # print graph info in stdout
    # degree centrality
    print('-----------------\n\n')
    print(default_lang)
    print(nx.info(lang_graph))
    try:
        # When ties are associated to some positive aspects such as friendship or collaboration,
        #  indegree is often interpreted as a form of popularity, and outdegree as gregariousness.
        DC = nx.degree_centrality(lang_graph)
        max_dc = max(DC.values())
        max_dc_list = [item for item in DC.items() if item[1] == max_dc]
    except ZeroDivisionError:
        max_dc_list = []
    # https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D1%8B%D0%B5_%D1%81%D0%B5%D1%82%D0%B8
    print('maxdc', str(max_dc_list), sep=': ')
    # assortativity coef
    AC = nx.degree_assortativity_coefficient(lang_graph)
    print('AC', str(AC), sep=': ')
    # connectivity
    print("Слабо-связный граф: ", nx.is_weakly_connected(lang_graph))
    print("количество слабосвязанных компонент: ", nx.number_weakly_connected_components(lang_graph))
    print("Сильно-связный граф: ", nx.is_strongly_connected(lang_graph))
    print("количество сильносвязанных компонент: ", nx.number_strongly_connected_components(lang_graph))
    print("рекурсивные? компоненты: ", nx.number_attracting_components(lang_graph))
    print("число вершинной связности: ", nx.node_connectivity(lang_graph))
    print("число рёберной связности: ", nx.edge_connectivity(lang_graph))
    # other info
    print("average degree connectivity: ", nx.average_degree_connectivity(lang_graph))
    print("average neighbor degree: ", sorted(nx.average_neighbor_degree(lang_graph).items(),
                                              key=itemgetter(1), reverse=True))
    # best for small graphs, and our graphs are pretty small
    print("pagerank: ", sorted(nx.pagerank_numpy(lang_graph).items(), key=itemgetter(1), reverse=True))

    plt.figure(figsize=(16.0, 9.0), dpi=80)
    plt.axis('off')
    pos = graphviz_layout(lang_graph)
    nx.draw_networkx_edges(lang_graph, pos, alpha=0.5, arrows=True)
    nx.draw_networkx(lang_graph, pos, node_size=1000, font_size=12, with_labels=True, node_color='green')
    nx.draw_networkx_edge_labels(lang_graph, pos, edges)

    # saving file to draw it with dot-graphviz
    # changing overall graph view, default is top-bottom
    lang_graph.graph['graph'] = {'rankdir': 'LR'}
    # marking with blue nodes with maximum degree centrality
    for max_dc_node in max_dc_list:
        lang_graph.node[max_dc_node[0]]['fontcolor'] = 'blue'
    write_dot(lang_graph, os.path.join(graphs_dir, default_lang + '_links.dot'))

    # plt.show()
    plt.savefig(os.path.join(graphs_dir, 'python_' + default_lang + '_graph.png'), dpi=100)
    plt.close()

def average_shortest_path_length(G, weight=None):
    r"""Return the average shortest path length.

    The average shortest path length is

    .. math::

       a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}

    where `V` is the set of nodes in `G`,
    `d(s, t)` is the shortest path from `s` to `t`,
    and `n` is the number of nodes in `G`.

    Parameters
    ----------
    G : NetworkX graph

    weight : None or string, optional (default = None)
       If None, every edge has weight/distance/cost 1.
       If a string, use this edge attribute as the edge weight.
       Any edge attribute not present defaults to 1.

    Raises
    ------
    NetworkXError:
       if the graph is not connected.

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.average_shortest_path_length(G))
    2.0

    For disconnected graphs you can compute the average shortest path
    length for each component:
    >>> G=nx.Graph([(1,2),(3,4)])
    >>> for g in nx.connected_component_subgraphs(G):
    ...     print(nx.average_shortest_path_length(g))
    1.0
    1.0

    """
    if G.is_directed():
        if not nx.is_weakly_connected(G):
            raise nx.NetworkXError("Graph is not connected.")
    else:
        if not nx.is_connected(G):
            raise nx.NetworkXError("Graph is not connected.")
    avg=0.0
    if weight is None:
        for node in G:
            path_length=nx.single_source_shortest_path_length(G, node)
            avg += sum(path_length.values())
    else:
        for node in G:
            path_length=nx.single_source_dijkstra_path_length(G, node, weight=weight)
            avg += sum(path_length.values())
    n=len(G)
    return avg/(n*(n-1))

 def is_connected(self):
     """
     Return True if the Xmrs represents a connected graph.
     Subgraphs can be connected through things like arguments,
     QEQs, and label equalities.
     """
     try:
         return nx.is_weakly_connected(self._graph)
     except nx.exception.NetworkXPointlessConcept:
         raise XmrsError("Connectivity is undefined for an empty Xmrs.")

def random_connected_graph(numNodes, numEdges):
    '''Generates a weakly connected random graph with numNodes nodes
       and numEdges edges
    '''
    tries = 0
    while tries < 100:
        tries += 1
        random_graph = nx.gnm_random_graph(numNodes,numEdges,directed = True)
        if nx.is_weakly_connected(random_graph): 
            return random_graph
    return None

 def _get_subgraphs(self, graph, name, size=3):
     subgraphs = set()
     # print "\nSubgraphs START: " + name
     target = nx.complete_graph(size)
     for sub_nodes in itertools.combinations(graph.nodes(),len(target.nodes())):
         subg = graph.subgraph(sub_nodes)
         if nx.is_weakly_connected(subg):
             # print subg.edges()
             subgraphs.add(subg)
     # print "Subgraphs END \n"
     return subgraphs

def output_conectivity_info (graph, path):
    """Output connectivity information about the graph.
       graph : (networkx.Graph)
       path: (String) contains the path to the output file
    """
    with open(path, 'w') as out:
        out.write('***Conectivity***\n')
        out.write('Is weakly connected: %s\n' % nx.is_weakly_connected(graph))
        out.write('Number of weakly connected components: %d\n' % nx.number_weakly_connected_components(graph))
        out.write('Is strongly connected: %s\n' % nx.is_strongly_connected(graph))
        out.write('Number of strongly connected components: %d' % nx.number_strongly_connected_components(graph))

    def set_domain(clz, dag):
        """ Sets the domain.  Should only be called once per class instantiation. """
        logging.info("Setting domain for poset %s" % clz.__name__)
        if nx.number_of_nodes(dag) == 0:
            raise CellConstructionFailure("Empty DAG structure.")
            
        if not nx.is_directed_acyclic_graph(dag):
            raise CellConstructionFailure("Must be directed and acyclic")

        if not nx.is_weakly_connected(dag):
            raise CellConstructionFailure("Must be connected")
        clz.domain_map[clz] = dag

    def rooted_core_interface_pairs(self, root, thickness=None,  for_base=False,
                                        hash_bitmask=None,
                                      radius_list=[],
                                      thickness_list=None,
                                      node_filter=lambda x, y: True):
        """

        Parameters
        ----------
        root:
        thickness:
        args:

        Returns
        -------

        """

        ciplist = super(self.__class__, self).rooted_core_interface_pairs(root, thickness, for_base=for_base,
                                        hash_bitmask=hash_bitmask,
                                      radius_list=radius_list,
                                      thickness_list=thickness_list,
                                      node_filter=node_filter)



        # numbering shards if cip graphs not connected
        for cip in ciplist:
            if not nx.is_weakly_connected(cip.graph):
                comps = [list(node_list) for node_list in nx.weakly_connected_components(cip.graph)]
                comps.sort()

                for i, nodes in enumerate(comps):

                    for node in nodes:
                        cip.graph.node[node]['shard'] = i

        '''
        solve problem of single-ede-nodes in the core
        this may replace the need for fix_structure thing
        this is a little hard.. may fix later

        it isnt hard if i write this code in merge_core in ubergraphlearn

        for cip in ciplist:
            for n,d in cip.graph.nodes(data=True):
                if 'edge' in d and 'interface' not in d:
                    if 'interface' in cip.graph.node[ cip.graph.successors(n)[0]]:
                        #problem found
        '''

        return ciplist

def is_semiconnected(G):
    """Return True if the graph is semiconnected, False otherwise.

    A graph is semiconnected if, and only if, for any pair of nodes, either one
    is reachable from the other, or they are mutually reachable.

    Parameters
    ----------
    G : NetworkX graph
        A directed graph.

    Returns
    -------
    semiconnected : bool
        True if the graph is semiconnected, False otherwise.

    Raises
    ------
    NetworkXNotImplemented :
        If the input graph is undirected.

    NetworkXPointlessConcept :
        If the graph is empty.

    Examples
    --------
    >>> G=nx.path_graph(4,create_using=nx.DiGraph())
    >>> print(nx.is_semiconnected(G))
    True
    >>> G=nx.DiGraph([(1, 2), (3, 2)])
    >>> print(nx.is_semiconnected(G))
    False

    See Also
    --------
    is_strongly_connected
    is_weakly_connected
    is_connected
    is_biconnected
    """
    if len(G) == 0:
        raise nx.NetworkXPointlessConcept(
            'Connectivity is undefined for the null graph.')

    if not nx.is_weakly_connected(G):
        return False

    G = nx.condensation(G)
    path = nx.topological_sort(G)
    return all(G.has_edge(u, v) for u, v in pairwise(path))

def generate_triads_1(network):
	"""
	Generate triads by making all node combinations, filtering < 2 edges. 
	Not suitable for large graphs. 

	"""
	nodes = network.nodes()
	node_combos = list(itertools.combinations(nodes, 3))
	triads = []

	for combo in node_combos:
		sub_graph = network.subgraph(combo)
		if nx.is_weakly_connected(sub_graph):
			triads.append(sub_graph)
	return triads

def get_largest_component(G, strongly=False):
    """
    Return a subgraph of the largest weakly or strongly connected component
    from a directed graph.

    Parameters
    ----------
    G : networkx multidigraph
    strongly : bool
        if True, return the largest strongly instead of weakly connected
        component

    Returns
    -------
    G : networkx multidigraph
        the largest connected component subgraph from the original graph
    """

    start_time = time.time()
    original_len = len(list(G.nodes()))

    if strongly:
        # if the graph is not connected retain only the largest strongly connected component
        if not nx.is_strongly_connected(G):
            
            # get all the strongly connected components in graph then identify the largest
            sccs = nx.strongly_connected_components(G)
            largest_scc = max(sccs, key=len)
            G = induce_subgraph(G, largest_scc)
            
            msg = ('Graph was not connected, retained only the largest strongly '
                   'connected component ({:,} of {:,} total nodes) in {:.2f} seconds')
            log(msg.format(len(list(G.nodes())), original_len, time.time()-start_time))
    else:
        # if the graph is not connected retain only the largest weakly connected component
        if not nx.is_weakly_connected(G):
            
            # get all the weakly connected components in graph then identify the largest
            wccs = nx.weakly_connected_components(G)
            largest_wcc = max(wccs, key=len)
            G = induce_subgraph(G, largest_wcc)
            
            msg = ('Graph was not connected, retained only the largest weakly '
                   'connected component ({:,} of {:,} total nodes) in {:.2f} seconds')
            log(msg.format(len(list(G.nodes())), original_len, time.time()-start_time))

    return G

def is_dependency_subgraph(graph, subgraph_candidate,
                           node_attrib='label', edge_attrib='label'):
    """
    returns True, if the graph contains all of the subgraph candidate's
    dependency rules. The subgraph must also be (weakly) connected and contain
    at least two nodes.

    NOTE: The criteria used here might not be strong enough, i.e. it would
    be possible to construct a subgraph candidate that contains only rules
    from the graph but is not a true subgraph of the graph.
    """
    if len(subgraph_candidate) > 1:
        if nx.is_weakly_connected(subgraph_candidate):
            if includes_all_subgraph_rules(graph, subgraph_candidate,
                                           node_attrib=node_attrib,
                                           edge_attrib=edge_attrib):
                return True
    return False

    def rooted_core_interface_pairs(self, root, thickness=None, **args):
        '''

        Args:
            root: int
            thickness:  
            **args:

        Returns:

        '''

        ciplist = super(self.__class__, self).rooted_core_interface_pairs(root, thickness, **args)


        #numbering shards if cip graphs not connected
        for cip in ciplist:
            if not nx.is_weakly_connected(cip.graph):
                comps = [list(node_list) for node_list in nx.weakly_connected_components(cip.graph)]
                comps.sort()

                for i, nodes in enumerate(comps):

                    for node in nodes:
                        cip.graph.node[node]['shard'] = i

        '''
        solve problem of single-ede-nodes in the core
        this may replace the need for fix_structure thing
        this is a little hard.. may fix later

        it isnt hard if i write this code in merge_core in ubergraphlearn

        for cip in ciplist:
            for n,d in cip.graph.nodes(data=True):
                if 'edge' in d and 'interface' not in d:
                    if 'interface' in cip.graph.node[ cip.graph.successors(n)[0]]:
                        #problem found
        '''

        return ciplist

    def rooted_core_interface_pairs(self, root,
                                    thickness_list=None,
                                    for_base=False,
                                    radius_list=[],
                                    base_thickness_list=False):

        """
        Parameters
        ----------
        root:
        thickness:
        args:

        Returns
        -------
        """

        ciplist = super(self.__class__, self).rooted_core_interface_pairs(root,
                                        thickness_list=thickness_list,
                                        for_base=for_base,
                                        radius_list=radius_list,
                                        base_thickness_list=base_thickness_list)



        if not for_base:
            # numbering shards if cip graphs not connected
            for cip in ciplist:
                if not nx.is_weakly_connected(cip.graph):
                    comps = [list(node_list) for node_list in nx.weakly_connected_components(cip.graph)]
                    comps.sort()
                    for i, nodes in enumerate(comps):
                        for node in nodes:
                            cip.graph.node[node]['shard'] = i


        return ciplist

#.........这里部分代码省略.........
    >>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
    5

    If you specify a pair of nodes (source and target) as parameters,
    this function returns the value of local edge connectivity.

    >>> nx.edge_connectivity(G, 3, 7)
    5

    If you need to perform several local computations among different
    pairs of nodes on the same graph, it is recommended that you reuse
    the data structures used in the maximum flow computations. See
    :meth:`local_edge_connectivity` for details.

    Notes
    -----
    This is a flow based implementation of global edge connectivity.
    For undirected graphs the algorithm works by finding a 'small'
    dominating set of nodes of G (see algorithm 7 in [1]_ ) and
    computing local maximum flow (see :meth:`local_edge_connectivity`)
    between an arbitrary node in the dominating set and the rest of
    nodes in it. This is an implementation of algorithm 6 in [1]_ .
    For directed graphs, the algorithm does n calls to the maximum
    flow function. This is an implementation of algorithm 8 in [1]_ .

    See also
    --------
    :meth:`local_edge_connectivity`
    :meth:`local_node_connectivity`
    :meth:`node_connectivity`
    :meth:`maximum_flow`
    :meth:`edmonds_karp`
    :meth:`preflow_push`
    :meth:`shortest_augmenting_path`

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

    """
    if (s is not None and t is None) or (s is None and t is not None):
        raise nx.NetworkXError('Both source and target must be specified.')

    # Local edge connectivity
    if s is not None and t is not None:
        if s not in G:
            raise nx.NetworkXError('node %s not in graph' % s)
        if t not in G:
            raise nx.NetworkXError('node %s not in graph' % t)
        return local_edge_connectivity(G, s, t, flow_func=flow_func)

    # Global edge connectivity
    # reuse auxiliary digraph and residual network
    H = build_auxiliary_edge_connectivity(G)
    R = build_residual_network(H, 'capacity')
    kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)

    if G.is_directed():
        # Algorithm 8 in [1]
        if not nx.is_weakly_connected(G):
            return 0

        # initial value for \lambda is minimum degree
        L = min(G.degree().values())
        nodes = G.nodes()
        n = len(nodes)
        for i in range(n):
            kwargs['cutoff'] = L
            try:
                L = min(L, local_edge_connectivity(G, nodes[i], nodes[i+1],
                                                   **kwargs))
            except IndexError: # last node!
                L = min(L, local_edge_connectivity(G, nodes[i], nodes[0],
                                                   **kwargs))
        return L
    else: # undirected
        # Algorithm 6 in [1]
        if not nx.is_connected(G):
            return 0

        # initial value for \lambda is minimum degree
        L = min(G.degree().values())
        # A dominating set is \lambda-covering
        # We need a dominating set with at least two nodes
        for node in G:
            D = nx.dominating_set(G, start_with=node)
            v = D.pop()
            if D:
                break
        else:
            # in complete graphs the dominating sets will always be of one node
            # thus we return min degree
            return L

        for w in D:
            kwargs['cutoff'] = L
            L = min(L, local_edge_connectivity(G, v, w, **kwargs))

        return L