Args:
            given_graph (DFA): The DFA states
            sfa (boolean): A boolean for chosing SFA
        Return:
            list, list, list: sm_vector, smi_vector, em_vector initialization vectors
555928
def _init_using_k_equivalence(self, given_graph, sfa=False):
        
        graph = DFA(self.alphabet)
        graph.init_from_acceptor(given_graph)
        graph.fixminimized(self.alphabet)

        # Access Strings
        self.access_strings_map = self._bfs_path_states(graph, sorted(
            graph.states, key=attrgetter('initial'), reverse=True)[0])

        # Find Q
        set_q = set(self._object_set_to_state_list(graph.states))
        # We will work with states addresses here instead of states stateid for
        # more convenience
        set_f = set(self._object_set_to_state_list(self._get_accepted(graph)))
        # Perform P := {F, Q-F}
        set_nf = set_q.copy() - set_f.copy()
        self.groups = [set_f.copy(), set_nf.copy()]
        self.bookeeping = [(set_f, set_nf, '')]

        done = False
        while not done:
            done = True
            new_groups = []
            for selectgroup in self.groups:
                # _check for each letter if it splits the current group
                for character in self.alphabet:
                    # print 'Testing symbol: ', c
                    target = defaultdict(list)
                    target_states = defaultdict(int)
                    new_g = [set(selectgroup)]
                    for sid in selectgroup:
                        # _check if all transitions using c are going in a state
                        # in the same group. If they are going on a different
                        # group then split
                        deststate = self._delta(graph, graph[sid], character)
                        destgroup = self._get_group_from_state(
                            deststate.stateid)
                        target[destgroup].append(sid)
                        target_states[destgroup] = deststate.stateid
                    if len(target) > 1:

                        inv_target_states = {
                            v: k for k, v in target_states.iteritems()}
                        new_g = [set(selectedstate) for selectedstate in target.values()]
                        done = False
                        # Get all the partitions of destgroups
                        queue = [set([x for x in target_states.values()])]
                        while queue:
                            top = queue.pop(0)
                            (group1, group2, distinguish_string) = self._partition_group(top)
                            ng1 = self._reverse_to_source(
                                target, [inv_target_states[x] for x in group1])
                            ng2 = self._reverse_to_source(
                                target, [inv_target_states[x] for x in group2])
                            dist_string = character + distinguish_string

                            self.bookeeping.append((ng1, ng2, dist_string))

                            if len(group1) > 1:
                                queue.append(group1)
                            if len(group2) > 1:
                                queue.append(group2)
                        break
                new_groups += new_g

            # End of iteration for the k-equivalence
            # Assign new groups and check if any change occured
            self.groups = new_groups

        sm_vector = [
            i for (a, i) in sorted(
                self.access_strings_map.items(),
                key=lambda x: len(x[1]))]
        if not sfa:
            smi_vector = ['{}{}'.format(a, b)
                          for b in self.alphabet for a in sm_vector]
        else:
            smi_vector = self._init_smi(graph, self.access_strings_map)
        em_vector = [distinguish_string for (_, _, distinguish_string) in self.bookeeping]

        return sm_vector, smi_vector, em_vector
1313739
def graph_to_dimacs(g, f):
    
    # write comments
    f.write('c Created by medpy\n')
    f.write('c Oskar Maier, oskar.maier@googlemail.com\n')
    f.write('c\n')
    
    # write problem
    f.write('c problem line\n')
    f.write('p max {} {}\n'.format(g.get_node_count() + 2, len(g.get_edges()))) # +2 as terminal nodes also count in dimacs format # no-nodes / no-edges
    
    # denote source and sink
    f.write('c source descriptor\n')
    f.write('n 1 s\n')
    f.write('c sink descriptor\n')
    f.write('n 2 t\n')
    
    # write terminal arcs (t-weights)
    f.write('c terminal arcs (t-weights)\n')
    for node, weight in list(g.get_tweights().items()):
        # Note: the nodes ids of the graph start from 1, but 1 and 2 are reserved for source and sink respectively, therefore add 2
        if not 0 == weight[0]: # 0 weights are implicit
            f.write('a 1 {} {}\n'.format(node + 2, weight[0]))
        if not 0 == weight[1]: # 0 weights are implicit
            f.write('a {} 2 {}\n'.format(node + 2, weight[1]))
    
    # write inter-node arcs (n-weights)
    f.write('c inter-node arcs (n-weights)\n')
    for edge, weight in list(g.get_nweights().items()):
        if not 0 == weight[0]: # 0 weights are implicit
            f.write('a {} {} {}\n'.format(edge[0] + 2, edge[1] + 2, weight[0]))
        # reversed weights have to follow directly in the next line
        if not 0 == weight[1]: # 0 weights are implicit
            f.write('a {} {} {}\n'.format(edge[1] + 2, edge[0] + 2, weight[1]))
            
    # end comment
    f.write('c end-of-file')
774009
def fc(self, output_nodes, keep_prob=1, activation_fn=tf.nn.relu, b_value=0.0, s_value=1.0, bn=True,
           trainable=True):
        
        self.count['fc'] += 1
        scope = 'fc_' + str(self.count['fc'])
        with tf.variable_scope(scope):

            # Flatten if necessary
            if len(self.input.get_shape()) == 4:
                input_nodes = tf.Dimension(
                    self.input.get_shape()[1] * self.input.get_shape()[2] * self.input.get_shape()[3])
                output_shape = tf.stack([-1, input_nodes])
                self.input = tf.reshape(self.input, output_shape)

            # Matrix Multiplication Function
            input_nodes = self.input.get_shape()[1]
            output_shape = [input_nodes, output_nodes]
            w = self.weight_variable(name='weights', shape=output_shape, trainable=trainable)
            self.input = tf.matmul(self.input, w)

            if bn is True:  # batch normalization
                self.input = self.batch_norm(self.input, 'fc')
            if b_value is not None:  # bias value
                b = self.const_variable(name='bias', shape=[output_nodes], value=b_value, trainable=trainable)
                self.input = tf.add(self.input, b)
            if s_value is not None:  # scale value
                s = self.const_variable(name='scale', shape=[output_nodes], value=s_value, trainable=trainable)
                self.input = tf.multiply(self.input, s)
            if activation_fn is not None:  # activation function
                self.input = activation_fn(self.input)
            if keep_prob != 1:  # dropout function
                self.input = tf.nn.dropout(self.input, keep_prob=keep_prob)
        print(scope + ' output: ' + str(self.input.get_shape()))
218716
private <E> Collection<Block<S, L>> initialize(UniversalGraph<S, E, ?, L> graph,
                                                   Collection<? extends S> initialNodes) {
        Iterable<? extends S> origStates;
        if (initialNodes == null || initialNodes.isEmpty()) {
            origStates = graph.getNodes();
        } else {
            origStates = GraphTraversal.depthFirstOrder(graph, initialNodes);
        }

        Map<L, TransitionLabel<S, L>> transitionMap = new HashMap<>();

        stateStorage = graph.createStaticNodeMapping();

        int numStates = 0;
        for (S origState : origStates) {
            State<S, L> state = new State<>(numStates++, origState);
            stateStorage.put(origState, state);
            stateList.add(state);
        }

        InitialPartitioning<S, L> initPartitioning = new HashMapInitialPartitioning<>(graph);

        for (State<S, L> state : stateList) {
            S origState = state.getOriginalState();

            Block<S, L> block = initPartitioning.getBlock(origState);
            block.addState(state);

            for (E edge : graph.getOutgoingEdges(origState)) {
                S origTarget = graph.getTarget(edge);
                State<S, L> target = stateStorage.get(origTarget);
                L label = graph.getEdgeProperty(edge);
                TransitionLabel<S, L> transition = transitionMap.computeIfAbsent(label, TransitionLabel::new);
                Edge<S, L> edgeObj = new Edge<>(state, target, transition);
                state.addOutgoingEdge(edgeObj);
                target.addIncomingEdge(edgeObj);
            }
        }
        stateList.quickClear();

        return initPartitioning.getInitialBlocks();
    }
713236
def dfs(graph, func, head, reverse=None):
    
    todo = deque()
    todo.append(head)
    path = deque()
    done = set()
    while todo:
        node = todo.popleft()
        if node in done:
            path.pop()
            continue

        done.add(node)
        path.append(node)
        result = func(node, path, graph)
        if result:
            if reverse:
                children = graph.get_parents(node)
            else:
                children = graph.get_children(node)
            todo.extend(children)
726152
def legal_graph(graph):
    '''
    '''

    descriptor = graph.extract_descriptor()
    skips = descriptor.skip_connections
    if len(skips) != len(set(skips)):
        return False
    return True
683126
def filterGraph(graph, node_fnc):
		
		nodes = filter(lambda l: node_fnc(l), graph.nodes())
		edges = {}

		gedges = graph.edges()
		for u in gedges:
			if u not in nodes:
				continue
			for v in gedges[u]:
				if v not in nodes:
					continue
				try:
					edges[u].append(v)
				except KeyError:
					edges[u] = [v]

		return Graph(nodes, edges)
525951
def import_graph(hl_graph, tf_graph, output=None, verbose=False):
    
    # Get clean(er) list of nodes
    graph_def = tf_graph.as_graph_def(add_shapes=True)
    graph_def = tf.graph_util.remove_training_nodes(graph_def)

    # Dump list of TF nodes (DEBUG only)
    if verbose:
        dump_tf_graph(tf_graph, graph_def)

    # Loop through nodes and build the matching directed graph
    for tf_node in graph_def.node:
        # Read node details
        try:
            op,  uid, name, shape, params = import_node(tf_node, tf_graph, verbose)
        except:
            if verbose:
                logging.exception("Failed to read node {}".format(tf_node))
            continue

        # Add node
        hl_node = Node(uid=uid, name=name, op=op, output_shape=shape, params=params)
        hl_graph.add_node(hl_node)

        # Add edges
        for target_node in graph_def.node:
            target_inputs = target_node.input
            if uid in target_node.input:
                hl_graph.add_edge_by_id(uid, target_node.name, shape)
    return hl_graph
1268554
def BFS(G, start):
    
    if start not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (start,))
    color = {}
    pred = {}
    dist = {}
    queue = Queue()
    queue.put(start)
    for vertex in G.vertices:
        color[vertex] = 'white'
        pred[vertex] = None
        dist[vertex] = 0
    while queue.qsize() > 0:
        current = queue.get()
        for neighbor in G.vertices[current]:
            if color[neighbor] == 'white':
                color[neighbor] = 'grey'
                pred[neighbor] = current
                dist[neighbor] = dist[current] + 1
                queue.put(neighbor)
        color[current] = 'black'
    return pred
362295
def get_input_nodes(G: nx.DiGraph) -> List[str]:
    
    return [n for n, d in G.in_degree() if d == 0]
294876
private void dfs(Visitor visitor, int v, int[] cc, int id) {
        visitor.visit(v);
        cc[v] = id;
        for (Edge edge : graph[v]) {
            int t = edge.v2;
            if (!digraph && t == v) {
                t = edge.v1;
            }

            if (cc[t] == -1) {
                dfs(visitor, t, cc, id);
            }
        }
    }
1307189
def validate(self, graph=None):
        
        graph = graph if graph is not None else self.graph
        if len(self.ind_nodes(graph)) == 0:
            return (False, 'no independent nodes detected')
        try:
            self.topological_sort(graph)
        except ValueError:
            return (False, 'failed topological sort')
        return (True, 'valid')
1348856
def dfs_do_func_on_graph(node, func, *args, **kwargs):
    '''
    
    '''
    for _node in node.tree_iterator():
        func(_node, *args, **kwargs)
887660
function node2NFA(node,from) {
  if (node.repeat) {
    return repeatNFA(node,from);
  } else {
    return NFABuilders[node.type](node,from);
  }
}
225740
def dfs_tree(graph, start=0):
    
    to_visit = [start]
    prec = [None] * len(graph)
    while to_visit:              # an empty queue equals False
        node = to_visit.pop()
        for neighbor in graph[node]:
            if prec[neighbor] is None:
                prec[neighbor] = node
                to_visit.append(neighbor)
    return prec
1112786
def bfs(graph, start):
    
    # maintain a queue of paths
    queue = []
    visited = []
    # maintain a queue of nodes
    # push the first path into the queue
    queue.append([['', start]])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1][1]
        if node.stateid not in visited:
            visited.append(node.stateid)
            # path found
            if node.final != TropicalWeight(float('inf')):
                return "".join([mnode[0] for mnode in path])
            # enumerate all adjacent nodes, construct a new path and push
            # it into the queue
            for arc in node.arcs:
                char = graph.isyms.find(arc.ilabel)
                next_state = graph[arc.nextstate]
                # print next_state.stateid
                if next_state.stateid not in visited:
                    new_path = list(path)
                    new_path.append([char, next_state])
                    queue.append(new_path)
89385
def _dinic_step(graph, capacity, lev, flow, u, target, limit):
    
    if limit <= 0:
        return 0
    if u == target:
        return limit
    val = 0
    for v in graph[u]:
        residual = capacity[u][v] - flow[u][v]
        if lev[v] == lev[u] + 1 and residual > 0:
            z = min(limit, residual)
            aug = _dinic_step(graph, capacity, lev, flow, v, target, z)
            flow[u][v] += aug
            flow[v][u] -= aug
            val += aug
            limit -= aug
    if val == 0:
        lev[u] = None         # remove unreachable node
    return val