def _congruence_graph(self):
		"""Form a graph whose vertex set is the QNF basis. The edges store the information which makes two vertices congruent."""
		from networkx.classes.digraph import DiGraph
		basis = self.quasinormal_basis
		min_exp = basis.minimal_expansion_for(self)
		terminal, initial = self.semi_infinite_end_points()
		endpts = sorted(terminal + initial)
		G = DiGraph()
		orbit_generators = set(min_exp)
		orbit_generators.update(endpts)
		
		#1. Add an edge for every direct congruence relationship.
		for gen in orbit_generators:
			type, images, _ = self.orbit_type(gen, basis)
			for power, img in images.items():
				images[power] = basis.test_above(img)
			
			congruent_pairs = permutations(images.items(), 2)
			for (pow1, (head1, tail1)), (pow2, (head2, tail2)) in congruent_pairs:
				if head1 == head2:
					continue
				data = dict(start_tail = tail1, power = pow2 - pow1, end_tail = tail2)
				G.add_edge(head1, head2, data)
				assert self.repeated_image(head1.extend(tail1), pow2 - pow1) == head2.extend(tail2)
		return G

    def __init__(self, incoming_graph_data=None, **attr):
        """Initialize a graph with edges, name, or graph attributes.

        Parameters
        ----------
        incoming_graph_data : input graph
            Data to initialize graph.  If incoming_graph_data=None (default)
            an empty graph is created.  The data can be an edge list, or any
            NetworkX graph object.  If the corresponding optional Python
            packages are installed the data can also be a NumPy matrix
            or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.

        attr : keyword arguments, optional (default= no attributes)
            Attributes to add to graph as key=value pairs.

        See Also
        --------
        convert

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G = nx.Graph(name='my graph')
        >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
        >>> G = nx.Graph(e)

        Arbitrary graph attribute pairs (key=value) may be assigned

        >>> G = nx.Graph(e, day="Friday")
        >>> G.graph
        {'day': 'Friday'}

        """
        self.edge_key_dict_factory = self.edge_key_dict_factory
        DiGraph.__init__(self, incoming_graph_data, **attr)

 def __init__(self, node_dict, edge_dict, U, initial_node, initial_label):
     DiGraph.__init__(self, name='motion_mdp', init_state=initial_node, init_label=initial_label)
     for (n, prob_label) in node_dict.iteritems():
         self.add_node(n, label = prob_label, act = set())
     print "-------Motion MDP Initialized-------"
     self.add_edges(edge_dict, U)
     print "%s states and %s edges" %(str(len(self.nodes())), str(len(self.edges())))
     self.unify_mdp()

 def __init__(self, algo_id, *args, **kwargs):
     DiGraph.__init__(self, args, kwargs)
     self.id = algo_id
     self.scan_count = 0
     self.input_data = []
     self.output_data =[]
     self.data_id_dict = {}  # internal dictionary for lookups of data nodes by id
     self.scan_rate = kwargs.pop('scan_rate')  # rate at which module should be scanned

def load_graph(file_or_path:FileOrPath, ext:str=None) -> DiGraph:
  graph = DiGraph()
  for adj in load_jsonl(text_file_for(file_or_path)):
    src = adj[0]
    graph.add_node(src)
    for dst in adj[1:]:
      graph.add_edge(src, dst)
  return graph

 def delete_node(self, n):
     try:
         if len(self.succ[n])+len(self.pred[n])==1: # allowed for leaf node
             DiGraph.delete_node(self,n) # deletes adjacent edge too
         else:
             raise NetworkXError( \
           "deleting interior node %s not allowed in tree"%(n))
     except KeyError: # NetworkXError if n not in self
         raise NetworkXError, "node %s not in graph"%n

def buchi_from_ltl(formula,Type):
    promela_string = run_ltl2ba(formula)
    symbols = find_symbols(formula)
    edges = parse_ltl(promela_string)
    (states, initials, accepts) = find_states(edges)
    buchi = DiGraph(type=Type, initial=initials, accept=accepts, symbols=symbols)
    for state in states:
        buchi.add_node(state)
    for (ef,et) in edges.keys():
        guard_formula = edges[(ef,et)]
        guard_expr = parse_guard(guard_formula)
        buchi.add_edge(ef, et, guard=guard_expr, guard_formula=guard_formula)
    return buchi

 def add_edge(self, u, v=None):  
     if v is None: (u,v)=u  # no v given, assume u is an edge tuple
     if self.has_edge(u,v): return # no parallel edges
     elif u in self and v in self:
         raise NetworkXError, "adding edge %s-%s not allowed in tree"%(u,v)
     elif u in self or v in self:
         DiGraph.add_edge(self,u,v) # u->v
         return
     elif len(self.adj)==0: # first leaf
         DiGraph.add_edge(self,u,v) # u->v           
         return
     else:
         raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))

    def load_from_graphml(path):
        """
        :type path: str
        :rtype: networkx.classes.graph.Graph
        """
        #: :type : networkx.classes.graph.Graph
        g1 = nx.read_graphml(path)
        #: :type graph: networkx.classes.digraph.DiGraph
        g2 = DiGraph()

        typetest = re.compile(r"([a-zA-z]+)(\d*)")

        max_qualifiers = dict(crossing=0, poi=0, plcs=0)
        node_mapping = dict()

        for node, data in g1.nodes_iter(data=True):

            m = typetest.match(data["label"])
            if m is None:
                raise(SALMAException("Wrong label format for node {}!".format(node)))

            loctype = m.group(1)
            if loctype in ["c"]:
                loctype = "crossing"
            elif loctype in ["p"]:
                loctype = "poi"
            elif loctype in ["pl"]:
                loctype = "plcs"
            if loctype not in ["poi", "plcs", "crossing"]:
                raise(SALMAException("Wrong loctype for node {}: {}".format(node, loctype)))
            qualifier = m.group(2)
            if len(qualifier) == 0:
                qualifier = max_qualifiers[loctype] + 1
                nid = data["label"] + str(qualifier)
            else:
                nid = data["label"]
            max_qualifiers[loctype] = max(max_qualifiers[loctype], qualifier)

            pos = (round(float(data["x"])), round(float(data["y"])))

            g2.add_node(nid, pos=pos, scaled_pos=pos, loctype=loctype)
            node_mapping[node] = nid

        for u, v in g1.edges_iter():
            n1 = node_mapping[u]
            n2 = node_mapping[v]
            g2.add_edge(n1, n2)
            g2.add_edge(n2, n1)

        MapGenerator.__add_roadlengths(g2)
        return g2

	def create_fair_graph(self,system):
		G = DiGraph()
		G.add_edges_from(self.edges(data=True))
		controls = nx.get_edge_attributes(self,'control')
		unfair_cycles = []
		for cycle in nx.simple_cycles(G):
			edges = [(cycle[i],cycle[(i+1)%len(cycle)]) for i in range(len(cycle))]
			trace = [(c[0],controls[c].values()) for c in edges]
			nbre_controls = [range(len(t[1])) for t in trace]
			control_configuration = itertools.product(*nbre_controls)
			for conf in control_configuration:
				current_trace = [(t[0],t[1][conf[i]]) for i,t in enumerate(trace)]
				if not self.is_cycle_fair(system,current_trace):
					unfair_cycles.append(current_trace)
		print "Unfair cycles ",unfair_cycles

 def __init__(self, formula):
     #----call ltl2dra executable----
     ltl2dra_output = run_ltl2dra(formula)
     #----parse the output----
     statenum, init, edges, aps, acc = parse_dra(ltl2dra_output)
     #------
     DiGraph.__init__(self, type='DRA', initial=set([init,]), accept=acc, symbols=aps)
     print "-------DRA Initialized-------"
     for state in xrange(0,statenum):
         self.add_node(state)
     for (ef,et) in edges.keys():
         guard_string = edges[(ef,et)]
         self.add_edge(ef, et, guard_string=guard_string)
     print "-------DRA Constructed-------"
     print "%s states, %s edges and %s accepting pairs" %(str(len(self.nodes())), str(len(self.edges())), str(len(acc)))

def make_test_graph():
    '''     (4)  6
             ^   ^
             | X |
            (3)  5
             ^   ^
              \ /
              [2]
               ^
               |
              (1)
    '''
    web = DiGraph()
    web.add_edges_from([(1,2), (2,3), (3,4), (2,5), (3,6), (5,6), (5,4)])
    return web

 def __init__(self):
     self.androGuardObjects = []
     
     self.nodes = {}
     self.nodes_id = {}
     self.entry_nodes = []
     self.G = DiGraph()

    def __init__(self, data=None, params=None, **attr):
        # self.reaction_graph.graph['node'] = {'fontname': 'Courier new'}
        # self.reaction_graph.graph['edge'] = {'fontname': 'Arial',
        #                                      'fontsize': 10.0, # labelfontsize
        #                                      'len': 4.0}
        DiGraph.__init__(self, data, **attr)
        if params is None:
            params = {}
        self.params = params  # or "config" ?
        if 'reaction_graph_default_attrs' in params:
            self.graph.update(params['reaction_graph_default_attrs'])

        # A reaction can have multiple end-state when a complex is being split up:
        # (edge_attrs should be the same for edges belonging to the same reaction for intracomplex reactions
        self.endstates_by_reaction = {}  # [startstate][(reaction_spec_pair, reaction_attr)] = [list of endstates]
        self.endstates_by_reaction[0] = defaultdict(list) # Also adding the "null" node
        self.reverse_reaction_key = {} # get reaction edge key for the opposite direction.
        self.tau_cum_max = 0
        # self.reverse_reaction[(rx_spec_pair, rx_attr)] = (rev_rx_spec_pair, rev_rx_attr)
        # used to be a dict {edge_key => target} but we can have multiple targets for a single reaction.
        self.reaction_graph_complexes_directory = params.get("reaction_graph_complexes_directory")
        if self.reaction_graph_complexes_directory is not None:
            if not os.path.exists(self.reaction_graph_complexes_directory):
                print("Creating directory for complex files:", self.reaction_graph_complexes_directory)
                os.makedirs(self.reaction_graph_complexes_directory)
            assert os.path.isdir(self.reaction_graph_complexes_directory)

        self.dispatchers = []
        # File with changes to the reaction graph, e.g. new nodes/edges and node/edge updates:
        self.reaction_graph_events_file = params.get('reaction_graph_events_file')
        if self.reaction_graph_events_file is None and self.reaction_graph_complexes_directory is not None:
            self.reaction_graph_events_file = os.path.join(self.reaction_graph_complexes_directory,
                                                           "reaction_graph_eventstream.json")

        if self.reaction_graph_events_file:
            #self.reaction_graph_delta_file = open(self.reaction_graph_delta_file, 'a')
            #self.open_files.append(self.reaction_graph_delta_file)
            gs_file_dispatcher = GraphStreamFileDispatcher(self.reaction_graph_events_file)
            gs_file_dispatcher.writer.write("# New reaction graph initialized at %s\n" % datetime.now())
            print("\n\nWriting reaction_graph event stream to file: %s\n" % self.reaction_graph_events_file)
            self.dispatchers.append(gs_file_dispatcher)
        else:
            # raise ValueError("self.reaction_graph_events_file not given: ", self.reaction_graph_events_file)
            print("self.reaction_graph_events_file (%s) not given: Graph events will not be available." %
                  self.reaction_graph_events_file)

def get_example_1():
    # input
    g = DiGraph()
    g.add_edges_from([[1, 2], [1, 3], [2, 4], [3, 4]])

    g.node[1]['r'] = 1
    g.node[2]['r'] = 1
    g.node[3]['r'] = 1.5
    g.node[4]['r'] = 1

    g[1][2]['c'] = 2
    g[1][3]['c'] = 1
    g[2][4]['c'] = 1
    g[3][4]['c'] = 3

    U = range(6)  # 0...5
    
    expected_edge_list = [
        [],
        [(1, 3)],
        [(1, 3)],  # DiGraph([(1, 2)])
        [(1, 2), (1, 3)],
        [(1, 2), (1, 3), (2, 4)],
        [(1, 2), (1, 3), (2, 4)]
    ]
    return g, U, expected_edge_list

def get_example_2():
    # input
    g = DiGraph()
    g.add_edges_from([[1, 2], [1, 3], [2, 4], [3, 4]])
    
    g.node[1]['r'] = 1
    g.node[2]['r'] = 1
    g.node[3]['r'] = 1.5
    g.node[4]['r'] = 1
    
    g[1][2]['c'] = 0.021
    g[1][3]['c'] = 0.011
    g[2][4]['c'] = 0.009
    g[3][4]['c'] = 0.03

    U = [float(i) / 100 for i in xrange(6)]  # 0...5

    # expected value
    expected_edge_list = [
        [],
        [(1, 3)],
        [(1, 3)],
        [(1, 2), (1, 3)],
        [(1, 2), (1, 3), (2, 4)],
        [(1, 2), (1, 3), (2, 4)]
    ]

    return (g, U, expected_edge_list)

 def add_node(self, n, attr_dict=None, dHdS=(0, 0), **attr):
     """ Add state node n to reaction graph. """
     assert n not in self.adj   # edge-attrs dict, {src: {tgt1: {edge1_attrs}, ...}}
     # print("ReactionGraph.add_node(%s, %s, %s, %s)" % (n, attr_dict, dHdS, attr))
     if attr_dict is None:
         attr_dict = attr
     elif attr:
         attr_dict.update(attr)
     # First dispatch
     attr_dict['dHdS'] = dHdS
     attr_dict['encounters'] = 1
     for dispatcher in self.dispatchers:
         dispatcher.add_node(n, attr_dict)
     attr_dict['dHdS_count'] = {dHdS: 1}
     # MultiGraph, with edges keyed by (reacted_spec_pair, reaction_attr):
     # reaction_graph.adj[source][target][(reacted_spec_pair, reaction_attr)] = eattr
     #self.reaction_graph.add_node(target_state, node_attrs)
     DiGraph.add_node(self, n, attr_dict)

class BoardGraph(object):
    def walk(self, board, size_limit=maxint):
        pending_nodes = []
        self.graph = DiGraph()
        self.start = board.display(cropped=True)
        self.graph.add_node(self.start)
        pending_nodes.append(self.start)
        self.min_domino_count = len(board.dominoes)
        while pending_nodes:
            if len(self.graph) >= size_limit:
                raise GraphLimitExceeded(size_limit)
            state = pending_nodes.pop()
            board = Board.create(state, border=1)
            dominoes = set(board.dominoes)
            self.min_domino_count = min(self.min_domino_count, len(dominoes))
            for domino in dominoes:
                dx, dy = domino.direction
                self.try_move(state, domino, dx, dy, pending_nodes)
                self.try_move(state, domino, -dx, -dy, pending_nodes)
        self.last = state
        return set(self.graph.nodes())

    def try_move(self, old_state, domino, dx, dy, pending_states):
        try:
            new_state = self.move(domino, dx, dy)
            move = domino.describe_move(dx, dy)
            if not self.graph.has_node(new_state):
                # new node
                self.graph.add_node(new_state)
                pending_states.append(new_state)
            self.graph.add_edge(old_state, new_state, move=move)
        except BoardError:
            pass

    def move(self, domino, dx, dy):
        """ Move a domino and calculate the new board state.

        Afterward, put the board back in its original state.
        @return: the new board state
        @raise BoardError: if the move is illegal
        """
        domino.move(dx, dy)
        try:
            board = domino.head.board
            if not board.isConnected():
                raise BoardError('Board is not connected.')
            if board.hasLoner():
                raise BoardError('Board has a lonely domino.')
            return board.display(cropped=True)
        finally:
            domino.move(-dx, -dy)

    def test_find_connecting_nodes_good_sourceDep(self):
        '''     (4)  6
                 ^   ^
                 | X |
                (3)  5
                 ^   ^
                  \ /
                  [2]
                   ^
                   |
                  (1)
        '''
        web = DiGraph()
        web.add_edges_from([(1,2), (2,3), (3,4), (2,5), (3,6), (5,6), (5,4)])

        inp = (1, 3, 4)
        out = (2,)
        (_, _, cn_nodes, _) = _research_calculation_routes(web, inp, out)
        all_out = {1,4,3}
        all_in = {2,5,6}
        self.assertTrue(cn_nodes - all_out == cn_nodes, cn_nodes)
        self.assertTrue(all_in & cn_nodes == all_in, cn_nodes)

def test_variance_based_cost():
    D = {'u': {}, 'v': {10: {'x', 'dum'}}, 'w': {12: {'y'}}}
    G = DiGraph()
    G.add_edges_from([('u', 'v'),
                      ('u', 'w'),
                      ('v', 'dum'),
                      ('dum', 'x'),
                      ('w', 'y')])
    G.node['dum']['dummy'] = True
    reprs = np.array([[0, 1],
                      [1, 0],
                      [0, 1],
                      [1, 1],
                      [0, 0]])
    real_nodes = ['u', 'v', 'w', 'x', 'y']
    for r, n in zip(reprs, real_nodes):
        G.node[n]['r'] = r
    n = 'u'
    children = [(10, 'v'),
                (12, 'w')]

    actual = get_all_nodes(G, n, D, children, ignore_dummy=True)
    expected = real_nodes
    assert_equal(sorted(expected), sorted(actual))

    cost_func = make_variance_cost_func(euclidean, 'r')
    
    actual = cost_func(n, D, G,
                       children)
    mean_vec = np.mean(reprs, axis=0)
    expected = np.sum([euclidean(mean_vec, v)
                       for v in reprs])
    np.testing.assert_almost_equal(expected, actual)

    # with fixed_point
    cost_func_fp = make_variance_cost_func(euclidean, 'r', fixed_point=2)
    actual = cost_func_fp(n, D, G,
                          children)
    assert_equal(int(expected*100), actual)