def test_brandes_erlebach_book():
    # Figure 1 chapter 7: Connectivity
    # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
    G = nx.Graph()
    G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4),
                      (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8),
                      (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)])
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cutsets
        assert_equal(3, len(nx.minimum_edge_cut(G, 1, 11, **kwargs)),
                     msg=msg.format(flow_func.__name__))
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        # Node 5 has only two edges
        assert_equal(2, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        assert_equal(set([6, 7]), minimum_st_node_cut(G, 1, 11, **kwargs),
                     msg=msg.format(flow_func.__name__))
        assert_equal(set([6, 7]), nx.minimum_node_cut(G, 1, 11, **kwargs),
                     msg=msg.format(flow_func.__name__))
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(2, len(node_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def __cut(graph):
    ''' param: 
            graph:a nx.DiGraph obj
	    return:
		    cs : edge cut set of the graph
		    g1 , g2 : subgraphs induced by cs
	
    '''
    assert isinstance(graph, nx.DiGraph), "graph class: %s " % graph.__class__
    assert graph.number_of_nodes() > 1,   "Number of nodes: %d" % graph.number_of_nodes()
    unigraph = nx.Graph( graph )          
    cs = nx.minimum_edge_cut( unigraph ) 
    if not cs:
        raise Exception,"Cut Set of this graph is Empty"

    #CS中的边，可能不存在于原来的有向图中，所以需要将这种边的方向颠倒
    #将所有real edge,存到RCS中
    rcs = []
    for eachEdge in cs:
        if not graph.has_edge( eachEdge[0], eachEdge[1] ):
            eachEdge = (eachEdge[1], eachEdge[0]) #调换方向
        rcs.append(eachEdge)
    graph.remove_edges_from(rcs)
    glist = []
    for eachCntComp in nx.weakly_connected_component_subgraphs(graph, copy = False):
        glist.append(eachCntComp)
    assert len(glist) == 2
    return rcs, glist[0], glist[1]

 def getMinCut(self):
     graph = self.getGraph()
     try: 
       min_cut = nx.minimum_edge_cut(graph)
     except: # not connected
       return -1
     return len(min_cut)

def test_edge_cutset_random_graphs():
    for i in range(5):
        G = nx.fast_gnp_random_graph(50,0.2)
        cutset = nx.minimum_edge_cut(G)
        assert_equal(nx.edge_connectivity(G), len(cutset))
        G.remove_edges_from(cutset)
        assert_false(nx.is_connected(G))

def test_white_harary_paper():
    # Figure 1b white and harary (2001)
    # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (node connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4, 7):
        G.add_edge(0, i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order() - 1)
    for i in range(7, 10):
        G.add_edge(0, i)
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(set([0]), node_cut, msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def RunProbabilityTest(G):
  '''
  Description:
    Finds the probability of running Karger's on the
    same graph 10*n**2 times with n = 20 and finding
    the min cut correctly.

  Args:
    G networkx graph of 20 nodes
    
  Returns:
    probability of running Karger's algo
    on the same graph and finding the min cut
  '''
  min_cuts_found = 0.0
  
  min_edge_cut = len(nx.minimum_edge_cut(G))
  for i in range(1, (10*20**2)+1):
    H = G.copy()

    H = RunKarger(H)

    # See if karger's returns the correct min cut
    if H.number_of_edges() == min_edge_cut:
      min_cuts_found += 1

  # For every n node sized graph find the probability 
  # of getting the min cut each time karger's is run
  # for a total of 10*n**2 runs
  print min_cuts_found, i
  return float('{0:.3f}'.format(min_cuts_found/i))

    def cut_edges_detection(self, segments, feature):

        #T = self.iterdiff(feature, segments)
        G, n_nodes, T = self.build_nodes_edges(segments, feature)

        hyp = Timeline()
        hypothesis = Timeline()
        hyp.add(
            Segment(segments[0].start, segments[n_nodes[0]].end)
        )

        hyp.add(
            Segment(segments[0].start, segments[n_nodes[0]].end)
        )
        for i, j in enumerate(n_nodes):
            hyp.add(
                Segment(
                    segments[n_nodes[i - 1]].end,
                    segments[n_nodes[i]].end
                )
            )
            Coupure = nx.minimum_edge_cut(G, T[j + 1], T[j])
            if len(Coupure) == 0:
                hypothesis.add(hyp[i])

        return hypothesis

def test_edge_cutset_random_graphs():
    for i in range(5):
        G = nx.fast_gnp_random_graph(50,0.2)
        if not nx.is_connected(G):
            ccs = iter(nx.connected_components(G))
            start = next(ccs)[0]
            G.add_edges_from( (start,c[0]) for c in ccs )
        cutset = nx.minimum_edge_cut(G)
        assert_equal(nx.edge_connectivity(G), len(cutset))
        G.remove_edges_from(cutset)
        assert_false(nx.is_connected(G))

def test_edge_cutset_random_graphs():
    for flow_func in flow_funcs:
        for i in range(3):
            G = nx.fast_gnp_random_graph(50, 0.25)
            if not nx.is_connected(G):
                ccs = iter(nx.connected_components(G))
                start = arbitrary_element(next(ccs))
                G.add_edges_from((start, arbitrary_element(c)) for c in ccs)
            cutset = nx.minimum_edge_cut(G, flow_func=flow_func)
            assert_equal(nx.edge_connectivity(G), len(cutset), msg=msg.format(flow_func.__name__))
            G.remove_edges_from(cutset)
            assert_false(nx.is_connected(G), msg=msg.format(flow_func.__name__))

def test_octahedral_cutset():
    G=nx.octahedral_graph()
    # edge cuts
    edge_cut = nx.minimum_edge_cut(G)
    assert_equal(4, len(edge_cut))
    H = G.copy()
    H.remove_edges_from(edge_cut)
    assert_false(nx.is_connected(H))
    # node cuts
    node_cut = nx.minimum_node_cut(G)
    assert_equal(4,len(node_cut))
    H = G.copy()
    H.remove_nodes_from(node_cut)
    assert_false(nx.is_connected(H))

def test_icosahedral_cutset():
    G = nx.icosahedral_graph()
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(5, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(5, len(node_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def FiveA():
  '''
  Description:
    Runs Karger's algorithm on random graphs.
    Creates the plot of the number of nodes in a
    graph vs. the probability of finding a min cut.
  '''
  
  prob_min_cut = {}
  p = 0.5

  # Create random graphs of 5,...,20 nodes
  for n in range(5, 21):
  
    min_cuts_found = 0.0

    for i in range(1, (10*(n**2))+1):
  
      G = CreateGraph(n, p)
      #plt.figure(1)
      #DrawGraph(G, 'ps3_q5.png')

      # Get the min cut using a built in method from networkx
      min_edge_cut = len(nx.minimum_edge_cut(G))

      G = RunKarger(G)

      # See if karger's returns the correct min cut
      if G.number_of_edges() == min_edge_cut:
        min_cuts_found += 1

    # For every n node sized graph find the probability 
    # of getting the min cut each time karger's is run
    # for a total of 10*n**2 runs
    prob_min_cut[n] = float('{0:.3f}'.format(min_cuts_found/i))
    
    # Output results to a csv file
    Write('ps3_q5_output.txt', n, prob_min_cut[n])
    

  # Read in results file and create a plot of results
  ReadCSV('ps3_q5_output.txt')  

def cut(graph):
    ''' parame: 
            graph:a nx.DiGraph obj
	    return:
		    cs : edge cut set of the graph
		    g1 , g2 : subgraphs induced by cs
	
    '''
    debug = True
    assert isinstance(graph, nx.DiGraph), "Input_para.__class__  %s " % graph.__class__
    assert graph.number_of_nodes() > 1,   "Number of nodes: %d" % graph.number_of_nodes()
    if debug: print "\nDigraph Edges Are:\n    %s" % str(graph.edges())
    unigraph = nx.Graph(graph)           #将输入的图转为无向图
    cs = nx.minimum_edge_cut(unigraph)   #找出该无向图的minimum edge cut -> CS
    #balance函数调用cut前，graph一定是一个un-balance 结构，所以一定有CUT?
    if not cs:
        raise Exception,"Cut Set of this graph is Empty"
    #CS中的边，可能不存在于原来的有向图中，所以需要将这种边的方向颠倒
    #将所有real edge,存到RCS中
    rcs = []
    original_edges = graph.edges()
    for eachEdge in cs:
        if not eachEdge in original_edges:
            eachEdge = (eachEdge[1], eachEdge[0]) #调换方向
        rcs.append(eachEdge)
    graph.remove_edges_from(rcs)			      #在原图中移除CS
    if debug: print "Edge Cut Set RCS :\n    %s" % str(rcs)
    if debug: print "After remove RCS :\n    %s" % str(graph.edges())
    
    # 移除RCS中的边之后得到的两个Weakly Connected Subgraph
    glist = []
    for eachCntComp in nx.weakly_connected_component_subgraphs(graph):
		#找到移除CS后的两个弱连接分量
        glist.append(eachCntComp)
        if debug:
            print "Weakly CC %d:" % len(glist)
            print "    nodes:%s" % eachCntComp.nodes() 
            print "    edges:%s" % eachCntComp.edges()
    assert len(glist) == 2
    return rcs, glist[0], glist[1]

	def build_graph(self):
		""" insert notes and edges based on user dictionary"""
		#  for key in self.user_dic.keys():
		#  self.graph.add_node(key)
		print "start building the graph"
		distinct_user = Set([])

		distinct_user.union(set( self.user_dic.keys() ))

		for value in self.user_dic.values():
			distinct_user.union(set(value))

		for eachuser in distinct_user:
			self.graph.add_node(key)

		for key in self.user_dic.keys():
			for value in self.user_dic[key]:
				# g.add_edges( [(1,2)] )
				self.graph.add_edge(key, value)

		for node in self.graph.nodes():
			self.color_dic[node] = "white"

		self.node_color = [self.color_dic[node] for node in self.graph.nodes()]

		allgraph = list(nx.connected_component_subgraphs(self.graph))

		mincut = nx.minimum_edge_cut(self.graph)
		print "mincut is ", mincut
		print "length of all connected component is ", len(allgraph)

		for graph in allgraph:

			# min_weighted_dominating_set(graphUD, weight=None)

			print graph.number_of_nodes()

		print "finish building the graph"

    def cut_edges_detection(self, feature, first_segments):

        """Recherche des arcs de coupure
            first_segments: segmenation initiale"""

        G, n_nodes, T = self.build_nodes_edges(feature, first_segments)

        hyp = Timeline()
        hypothesis = Timeline()
        hyp.add(
            Segment(first_segments[0].start, first_segments[n_nodes[0]].end)
        )
        for i, j in enumerate(n_nodes):
            hyp.add(
                Segment(
                    first_segments[n_nodes[i - 1]].end,
                    first_segments[n_nodes[i]].end
                )
            )
            Coupure = nx.minimum_edge_cut(G, T[j + 1], T[j])
            if len(Coupure) == 0:
                hypothesis.add(hyp[i])

        return hypothesis

def CalMaxFlows(DG_network, Dnodes, maxFlows):
	"""
	If two nodes are connected in networkx graph G, This function returns maxflow value, shortest path length, minimum edges cut 
	between this two nodes.
	"""
	for i in range(len(Dnodes)):
		for j in range(i+1, len(Dnodes)):

			if nx.has_path(DG_network, Dnodes[i], Dnodes[j]):
				maxflow = nx.maximum_flow_value(DG_network, Dnodes[i], Dnodes[j], capacity = 'weight')
				shortest_path_length = nx.shortest_path_length(DG_network, source = Dnodes[i], target = Dnodes[j])
				min_edges_cut = len(nx.minimum_edge_cut(DG_network, Dnodes[i], Dnodes[j]))
			else:
				continue
			if Dnodes[i] < Dnodes[j]:
				a_path = (Dnodes[i], Dnodes[j])
			else:
				a_path = (Dnodes[j], Dnodes[i])

			if not maxFlows.has_key(a_path):
				maxFlows[a_path] = (maxflow, shortest_path_length, min_edges_cut)
			else:
				print "impossibly!", a_path
				sys.exit(1)

	g = nx.Graph()
	for ma in matches:
		g.add_nodes_from(ma['teams'])
		n1, n2 = ma['teams']
		g.add_edge(
				n1,
				n2,
				attr_dict = {
					'capacity': g.get_edge_data(
						n1, n2, { }
					).get('capacity', 0) + 1,
				}
		)
	for repi in itertools.count(1):
		print repi, nx.number_of_nodes(g), nx.number_of_edges(g)
		min_cut_edges = list(nx.minimum_edge_cut(g))
		g.remove_edges_from(min_cut_edges)
		ccs = list(nx.connected_component_subgraphs(g))
		assert len(ccs) == 2
		n1, n2 = [ sg.number_of_nodes() for sg in ccs ]
		if n1 > n2:
			g = ccs[0]
		else:
			g = ccs[1]

if 0:
	with open('dat.csv', 'wb') as datcsvf:
		datcsvf.write('gh,ga\n')
		for ma in matches:
			datcsvf.write(str(ma['score'][0]))
			datcsvf.write(',')

def general_k_edge_subgraphs(G, k):
    """General algorithm to find all maximal k-edge-connected subgraphs in G.

    Returns
    -------
    k_edge_subgraphs : a generator of nx.Graphs that are k-edge-subgraphs
        Each k-edge-subgraph is a maximal set of nodes that defines a subgraph
        of G that is k-edge-connected.

    Notes
    -----
    Implementation of the basic algorithm from _[1].  The basic idea is to find
    a global minimum cut of the graph. If the cut value is at least k, then the
    graph is a k-edge-connected subgraph and can be added to the results.
    Otherwise, the cut is used to split the graph in two and the procedure is
    applied recursively. If the graph is just a single node, then it is also
    added to the results. At the end, each result is either guaranteed to be
    a single node or a subgraph of G that is k-edge-connected.

    This implementation contains optimizations for reducing the number of calls
    to max-flow, but there are other optimizations in _[1] that could be
    implemented.

    References
    ----------
    .. [1] Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs
        from a large graph.  ACM International Conference on Extending Database
        Technology 2012 480-–491.
        https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

    Example
    -------
    >>> from networkx.utils import pairwise
    >>> paths = [
    ...     (11, 12, 13, 14, 11, 13, 14, 12),  # a 4-clique
    ...     (21, 22, 23, 24, 21, 23, 24, 22),  # another 4-clique
    ...     # connect the cliques with high degree but low connectivity
    ...     (50, 13),
    ...     (12, 50, 22),
    ...     (13, 102, 23),
    ...     (14, 101, 24),
    ... ]
    >>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))
    >>> sorted(map(len, k_edge_subgraphs(G, k=3)))
    [1, 1, 1, 4, 4]
    """
    if k < 1:
        raise ValueError('k cannot be less than 1')

    # Node pruning optimization (incorporates early return)
    # find_ccs is either connected_components/strongly_connected_components
    find_ccs = partial(_high_degree_components, k=k)

    # Quick return optimization
    if G.number_of_nodes() < k:
        for node in G.nodes():
            yield G.subgraph([node]).copy()
        return

    # Intermediate results
    R0 = {G.subgraph(cc).copy() for cc in find_ccs(G)}
    # Subdivide CCs in the intermediate results until they are k-conn
    while R0:
        G1 = R0.pop()
        if G1.number_of_nodes() == 1:
            yield G1
        else:
            # Find a global minimum cut
            cut_edges = nx.minimum_edge_cut(G1)
            cut_value = len(cut_edges)
            if cut_value < k:
                # G1 is not k-edge-connected, so subdivide it
                G1.remove_edges_from(cut_edges)
                for cc in find_ccs(G1):
                    R0.add(G1.subgraph(cc).copy())
            else:
                # Otherwise we found a k-edge-connected subgraph
                yield G1

def get_coordinate_path(coords):    
    """
    Returns a path of 'coords' (assumed a single <x,y> coordinates of a 
    skeleton) such that:

    1) the start (endpoint) has the highest, second-lowest distance (the lowest
    distance is always +/- 1 pixel; the second lowest will be the greatest
    for an endpoint)
    
    2) all other points are separated from each other by at most 1 pixel

    Args:
        coords: the two-column array of pixel distances
    Returns:
        the sorted coordinate list
    """
    n_coords = len(coords)
    distances = scipy.spatial.distance_matrix(coords,coords,p=2)
    for i in range(n_coords):
        distances[i,i] = np.inf
    # check that the skeletonization is OK
    maximum_of_minimum_distances = np.sqrt(2)
    max_of_min = max(np.min(distances,axis=0))
    assert abs(max_of_min - maximum_of_minimum_distances) < 1e-6 , \
        "Skeletonization failed?"
    # POST: distances okay; all pixels at most 1 away in x and y
    # Now we need to decide on (possible arbitrary) endpoints. These should
    # be the two nodes with the largest *second* lowest distances (all have
    # at least one neighbor which is +/- 1 pixel; 'interior' nodes have at 
    # least two '1-pixel' neighbords
    second_lowest_distances = [sorted(row)[1] for row in distances]
    # sorted from low to high; what we want is the highest, second lowest
    sort_idx_second_highest = np.argsort(second_lowest_distances)
    endpoint = sort_idx_second_highest[-1]
    # POST: have endpoint. Add all the points with their two closest to the 
    # graph (except the endpoint, where we only add its closest)
    # create a graph of all the pixels
    G = nx.Graph()
    n_neightbors = 2
    # sort the data so the endpoint is first?
    print(endpoint)
    sorted_idx = list(np.arange(endpoint,n_coords)) + \
                 list(np.arange(0,endpoint))
    sorted_idx= np.array(sorted_idx)
    distances = distances[sorted_idx]
    coords = coords[sorted_idx]
    for i in range(n_coords):
        dist_tmp = distances[i]
        closest_nodes = np.argsort(dist_tmp)
        # add the closest N
        j = 0
        G.add_edge(i,closest_nodes[0],weight=1)
        G.add_edge(i,closest_nodes[1],weight=1)
    print("connectivity")
    remove_all_but_one = list(nx.minimum_edge_cut(G))
    for r in remove_all_but_one[:-1]:
        g.remove_edge(*r)
    print(nx.node_connectivity(G))
    nx.draw(G)
    plt.show()
    graph,path = single_chinese_postman_path(G)
    print(path,n_coords)
    for i in range(len(path)):
        print(len(set(path[:i])),i,n_coords)
    """
    see: 
https://stackoverflow.com/questions/18794308/algorithm-to-cover-all-edges-given-starting-node

https://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.matching.max_weight_matching.html#networkx.algorithms.matching.max_weight_matching

    also https://groups.google.com/forum/#!topic/networkx-discuss/NxbsY2dzkNk
    
    https://healthyalgorithms.com/2009/03/23/aco-in-python-minimum-weight-perfect-matchings-aka-matching-algorithms-and-reproductive-health-part-4/
    """
    coords_x = np.array(coords[:,0])
    coords_y = np.array(coords[:,1])

    return coords[path]

#.........这里部分代码省略.........
			tokensofthislevel = []
		
		intrinsic_merit = vertices*edges*relatedness / first_convergence_level
		output.write('Intrinsic merit of this document is:\n')
		output.write(str(intrinsic_merit))
		output.write('\n')
		output.write('Node with maximum parents (and hence the most likely class of document) is:\n')
		output.write(nodewithmaxparents)
		output.write('\n')
	
	print definitiongraphedges


	nxg=nx.DiGraph()
	pos=nx.spectral_layout(nxg)
	for k,v in definitiongraphedges.iteritems():
		for l in v:
			nxg.add_edge(k,l)
			nxg.add_edge(l,k)
			ksynset=wn.synsets(k)
			lsynset=wn.synsets(l)
			if ksynset and lsynset:
				print "ksynset=",ksynset[0]
				print "lsynset=",lsynset[0]
				hypoksynsets=set([i for i in ksynset[0].closure(lambda n:n.hyponyms())])
				hyperlsynsets=set([i for i in lsynset[0].closure(lambda n:n.hypernyms())])
				for m in hypoksynsets:
					try:
						mlemmanames=m.lemma_names()
						weight_str_map[k+" - "+l]=weight_str_map[k+" - "+l]+" contains "+mlemmanames[0]
					except KeyError:
						weight_str_map[k+" - "+l]=""
				for n in hyperlsynsets:
					try:
						nlemmanames=n.lemma_names()
						weight_str_map[l+" - "+k]=weight_str_map[l+" - "+k]+" is part of "+nlemmanames[0]
					except KeyError:
						weight_str_map[l+" - "+k]=""
	if not required_none_vertices:
		filter_none_vertices(nxg)
	
	nx.draw_networkx(nxg)
	try:
		nx.write_dot(nxg,"InterviewAlgorithmWithIntrinisicMerit_Crawl_Visual_RGOGraph.dot")
	except:
		pass
	plt.show()
	nxg.remove_edges_from(nxg.selfloop_edges())
	#print "Core number =",nx.core_number(nxg)
	sorted_core_nxg=sorted(nx.core_number(nxg).items(),key=operator.itemgetter(1), reverse=True)
	print "Core number (sorted) :",sorted_core_nxg
	print "============================================================================================================="
	print "Unsupervised Classification based on top percentile Core numbers of the definition graph(subgraph of WordNet)"
	print "============================================================================================================="
	no_of_classes=len(nx.core_number(nxg))
	top_percentile=0
	max_core_number=0
	for n in sorted_core_nxg:
		print "This document belongs to class:",n[0],",core number=",n[1]
		if top_percentile < no_of_classes*0.10:
			top_percentile+=1
		else:	
			break
		if n[1] > max_core_number:
			max_core_number=n[1]
	print "max_core_number",max_core_number

	print "==================================================================="
	print "Page Rank of the vertices of RGO Definition Graph"
	print "==================================================================="
	print sorted(nx.pagerank(nxg).items(),key=operator.itemgetter(1),reverse=True)

	try:
		print "=========================================================================================================="
		print "Alternative Quantitative Intrinsic Merit  - connectivity of RGO Definition Graph - Mengers Theorem"
		print "=========================================================================================================="
		print nx.node_connectivity(nxg)
	except:
		pass 
	try:
		print "=========================================================================================================="
		print "Alternative Quantitative Intrinsic Merit  - Maxflow-Mincut of RGO Definition Graph - Minimum Edge Cut"
		print "=========================================================================================================="
		print nx.minimum_edge_cut(nxg)
	except:
		pass 
	try:
		print "=========================================================================================================="
		print "Alternative Quantitative Intrinsic Merit  - Maxflow-Mincut of RGO Definition Graph - Stoer-Wagner"
		print "=========================================================================================================="
		print nx.stoer_wagner(nxg)
	except:
		pass 
	try:
		print "=========================================================================================================="
		print "Alternative Quantitative Intrinsic Merit  - Average Clustering Coefficient"
		print "=========================================================================================================="
		print nx.average_clustering(nxg)
	except:
		pass