Returns 1. a list of all PUT-winners of profile under ranked pairs rule
        and 2. A Stats object of runtime statistics

        :ivar Profile profile: A Profile object that represents an election profile.

def getWinners(self, profile):
        """
        Returns 1. a list of all PUT-winners of profile under ranked pairs rule
        and 2. A Stats object of runtime statistics

        :ivar Profile profile: A Profile object that represents an election profile.
        """

        # Initialize
        stats = self.Stats()

        wmg = profile.getWmg()
        known_winners = set()
        I = list(wmg.keys())

        G = nx.DiGraph()
        G.add_nodes_from(I)

        E = nx.DiGraph()
        E.add_nodes_from(I)
        for cand1, cand2 in itertools.permutations(wmg.keys(), 2):
            if wmg[cand1][cand2] > 0:
                E.add_edge(cand1, cand2, weight=wmg[cand1][cand2])

        # print(wmg)
        # self.output_graph(E)

        # Sample
        num_samples = 200
        for i in range(num_samples):
            self.sample(E, I, known_winners, stats)


        stats.num_sampled = len(known_winners)
        stats.sampled = sorted(known_winners.copy())

        # Start search

        # Each node contains (G, E)
        root = Node(value=(G, E))
        stackNode = []
        stackNode.append(root)

        hashtable = set()

        while stackNode:
            # Pop new node to explore
            node = stackNode.pop()
            (G, E) = node.value

            # Check hash
            hash_state = hash(str(G.edges()) + str(E.edges()))
            if hash_state in hashtable:
                stats.num_hashes += 1
                if self.debug_mode == 3:
                    print("hashed in outer hashtable")
                continue
            hashtable.add(hash_state)

            stats.num_outer_nodes += 1
            stats.num_nodes += 1

            if self.debug_mode == 3:
                print("Popped new node: ")
                print("G:", G.edges())
                print("E:", E.edges())

            # Flag for whether expanding the current tier required finding max children
            f_found_max_children = 0

            # Continue performing RP on this state as long as tie-breaking order doesn't matter
            while len(E.edges()) != 0:
                if self.stop_conditions(G, E, I, known_winners, stats) != -1:
                    # Stop condition hit
                    break

                (max_weight, max_edge) = max([(d['weight'], (u, v)) for (u, v, d) in E.edges(data=True)])
                ties = [d['weight'] for (u, v, d) in E.edges(data=True)].count(max_weight)

                if ties == 1:
                    # Tier only has one edge
                    if self.debug_mode == 3:
                        print("Only 1 edge in tier")

                    E.remove_edges_from([max_edge])
                    if nx.has_path(G, max_edge[1], max_edge[0]) is False:
                        G.add_edges_from([max_edge])

                else:
                    # This tier has multiple edges with same max weight.
                    tier = [(u, v) for (u, v, d) in E.edges(data=True) if d['weight'] == max_weight]
                    if self.debug_mode == 3:
                        print("Tier =", tier)

                    E.remove_edges_from(tier)

                    # Compute "bridge edges" which are not in any cycle
                    Gc = G.copy()
                    Gc.add_edges_from(tier)
                    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)
                    tier = list(set(tier) - 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)
                    tier = list(set(tier) - 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 tier:
                        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)
                    tier = list(set(tier) - redundant_edges)

                    if len(tier) == 0:
                        # No need to find max children, as tier is now empty
                        continue

                    max_children = self.find_max_children_scc_decomposition(G, tier, scc, bridges, I, known_winners, stats)

                    # Determine priority ordering of maximal children
                    children = dict()
                    index = 0
                    for child in max_children:
                        # child_node = Node(value=(self.edges2string(child.edges(), I), self.edges2string(E.edges(), I)))
                        child_node = Node(value=(child, E.copy()))
                        c_in_deg = child.in_degree(I)
                        available = set([x[0] for x in c_in_deg if x[1] == 0])
                        priority = len(available - known_winners)
                        # children[child_node] = (priority, index)
                        children[child_node] = index
                        child.add_nodes_from(I)
                        index += 1
                        continue

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

            # f_found_max_children is needed since, if we just added more nodes to stack, then current (G, E) is not actual valid state
            if len(E.edges()) == 0 and f_found_max_children == 0:
                # E is empty
                if self.debug_mode >= 2:
                    print("E is empty")
                self.add_winners(G, I, known_winners, stats)

        return sorted(known_winners), stats