Computes the maximal children of G when tier is added
        :param G: DiGraph, A directed graph
        :param tier: list of tuples which correspond to multiple edges with same max weight.
                    e.g. edges = [x for x in wmg2.keys() if wmg2[x] == max_weight]
        :param I: all nodes in G
        :param known_winners: PUT-winners found so far by RP
        :param stats: Stats object
        :param f_scc: set to 1 if the G and tier being considered are an SCC of the full graph due to SCC decomposition
        :return: set of graphs which correspond to maximum children of given parent: G

def explore_max_children_lp(self, G, tier, I, known_winners, stats, f_scc = 0):
        """
        Computes the maximal children of G when tier is added
        :param G: DiGraph, A directed graph
        :param tier: list of tuples which correspond to multiple edges with same max weight.
                    e.g. edges = [x for x in wmg2.keys() if wmg2[x] == max_weight]
        :param I: all nodes in G
        :param known_winners: PUT-winners found so far by RP
        :param stats: Stats object
        :param f_scc: set to 1 if the G and tier being considered are an SCC of the full graph due to SCC decomposition
        :return: set of graphs which correspond to maximum children of given parent: G
        """

        # self.output_graph(G)
        # self.output_graph(nx.DiGraph(tier))

        max_children = []
        cstack = []

        # print("start mc:", time.perf_counter() - self.BEGIN)

        hashtable = set()

        if self.debug_mode >= 1:
            print("Exploring max children")
            print("G:", G.edges())
            print("Tier:", tier)
            print("Known winners:", known_winners)
            print("---------------------------")

        in_deg = G.in_degree()
        nodes_with_no_incoming = set()
        for x in in_deg:
            if x[1] == 0:
                nodes_with_no_incoming.add(x[0])
        for x in I:
            if x not in G.nodes():
                nodes_with_no_incoming.add(x)

        root = Node(value=(self.edges2string(G.edges(), I), self.edges2string(tier, I), nodes_with_no_incoming))
        cstack.append(root)

        END = self.BEGIN + self.TIMEOUT

        while cstack:
            node = cstack.pop()
            (G_str, T_str, no_incoming) = node.value

            if time.perf_counter() > END:
                print("TIMEOUT")
                return max_children

            # Check hash. Doesn't ever happen if the below hash is included
            hash_G = hash(G_str)
            if hash_G in hashtable:
                stats.num_hashes += 1
                print('hash')
                if self.debug_mode >= 2:
                    print("hashed in hashtable")
                continue
            hashtable.add(hash_G)

            stats.num_nodes += 1

            G = nx.DiGraph(self.string2edges(G_str, I))
            T = self.string2edges(T_str, I)
            G.add_nodes_from(I)

            if self.debug_mode == 3:
                print("popped")
                print("G: ", G.edges())
                print("T: ", T)

            # goal state 2: if current G's possible winners is subset of known winners,
            # then directly ignore it.
            if no_incoming <= known_winners and not f_scc:
                stats.stop_condition_hits[2] += 1
                if self.debug_mode >= 3:
                    print("MC goal state 2: pruned")
                continue

            # goal state 1: if there are no edges to be added, then add the G_
            if len(T) == 0:
                max_children.append(G.copy())
                if self.debug_mode >= 2:
                    print("MC goal state 1: no more edges in tier")
                    print("max child: ", G.edges())
                continue

            # goal state 3: if current G has exactly one cand with in degree 0, it is a PUT-winner
            if len(no_incoming) == 1 and not f_scc:
                stats.stop_condition_hits[3] += 1
                if self.debug_mode >= 2:
                    print("MC goal state 3: only one cand in degree 0")
                    print("max child:", G.edges())
                self.add_winners(G, I, known_winners, stats, no_incoming)
                continue

            # goal state 4: if union of current G and edges is acyclic,
            # then directly add it to the max_children_set
            Gc = G.copy()
            Gc.add_edges_from(T)
            if nx.is_directed_acyclic_graph(Gc):
                stats.stop_condition_hits[4] += 1

                hash_temp_G = hash(self.edges2string(Gc.edges(), I))
                if hash_temp_G not in hashtable:
                    hashtable.add(hash_temp_G)
                    max_children.append(Gc)

                    if self.debug_mode >= 2:
                        print("MC goal state 4: G U T is acyclic")
                        print("max child:", Gc.edges())
                else:
                    stats.num_hashes += 1
                continue

            # Perform reductions every step:

            # Compute "bridge edges" which are not in any cycle
            Gc = G.copy()
            Gc.add_edges_from(T)
            scc = [list(g.edges()) for g in nx.strongly_connected_component_subgraphs(Gc, copy=True) if
                   len(g.edges()) != 0]
            bridges = set(Gc.edges()) - set(itertools.chain(*scc))
            G.add_edges_from(bridges)
            T = list(set(T) - bridges)

            G_tc = nx.transitive_closure(G)

            # Remove "inconsistent edges" that cannot be added to G without causing cycle
            reverse_G = nx.DiGraph.reverse(G_tc)
            T = list(set(T) - set(reverse_G.edges()))

            # Remove "redundant edges": if there is already path from e[0] to e[1], can immediately add e
            redundant_edges = set()
            for e in T:
                if G_tc.has_edge(e[0], e[1]):
                    redundant_edges.add(e)
                    G.add_edges_from([e])
            stats.num_redundant_edges += len(redundant_edges)
            T = list(set(T) - redundant_edges)

            # Flag for whether adding any edge from T causes G to remain acyclic
            f_isAcyclic = 0

            children = dict()

            # Used to break ties
            index = 0
            T = sorted(T)
            for e in T:
                G.add_edges_from([e])
                Gc_str = self.edges2string(G.edges(), I)
                if hash(Gc_str) in hashtable:
                    f_isAcyclic = 1

                    stats.num_hashes += 1
                    G.remove_edges_from([e])
                    continue

                if not nx.has_path(G, source=e[1], target=e[0]):
                    f_isAcyclic = 1

                    Tc = copy.deepcopy(T)
                    Tc.remove(e)

                    # Remove the head of the edge if it had no incoming edges previously
                    no_incoming_c = no_incoming.copy()
                    no_incoming_c.discard(e[1])

                    child = Node(value=(Gc_str, self.edges2string(Tc, I), no_incoming_c))

                    priority = len(no_incoming_c - known_winners)

                    children[child] = (priority, index)
                    index = index + 1

                    if self.debug_mode == 3:
                        print("add new child with edge ", e, " and priority ", priority)

                G.remove_edges_from([e])

            children_items = sorted(children.items(), key=lambda x: (x[1][0], x[1][1]))
            sorted_children = [key for key, value in children_items]
            cstack += sorted_children

            # goal state 5: adding all edges in T individually cause G to be cyclic
            if f_isAcyclic == 0:
                max_children.append(G.copy())

                if self.debug_mode >= 2:
                    print("MC goal state 5 - found max child")
                    print("max child: ", G.edges())
                continue

        if self.debug_mode >= 1:
            print("finished exploring max children")
            print("num max children:", len(max_children))
            print("PUT-winners:", known_winners)

        return max_children