模板搜索空间

class DynamicUnionPipeline(SearchSpace):
    def __init__(self, search_space : SearchSpace, max_estimators=None, allow_repeats=False ) -> None:
        """
        Takes in a list of search spaces. will produce a pipeline of Sequential length. Each step in the pipeline will correspond to the the search space provided in the same index.
        """

        self.search_space = search_space
        self.max_estimators = max_estimators
        self.allow_repeats = allow_repeats

    def generate(self, rng=None):
        rng = np.random.default_rng(rng)
        return DynamicUnionPipelineIndividual(self.search_space, max_estimators=self.max_estimators, allow_repeats=self.allow_repeats, rng=rng)

class DynamicUnionPipelineIndividual(SklearnIndividual):
    """
    Takes in one search space.
    Will produce a FeatureUnion of up to max_estimators number of steps.
    The output of the FeatureUnion will the all of the steps concatenated together.

    """

    def __init__(self, search_space : SearchSpace, max_estimators=None, allow_repeats=False, rng=None) -> None:
        super().__init__()
        self.search_space = search_space

        if max_estimators is None:
            self.max_estimators = np.inf
        else:
            self.max_estimators = max_estimators

        self.allow_repeats = allow_repeats

        self.union_dict = {}

        if self.max_estimators == np.inf:
            init_max = 3
        else:
            init_max = self.max_estimators

        rng = np.random.default_rng(rng)

        for _ in range(rng.integers(1, init_max)):
            self._mutate_add_step(rng)


    def mutate(self, rng=None):
        rng = np.random.default_rng(rng)
        mutation_funcs = [self._mutate_add_step, self._mutate_remove_step, self._mutate_replace_step, self._mutate_note]
        rng.shuffle(mutation_funcs)
        for mutation_func in mutation_funcs:
            if mutation_func(rng):
                return True

    def _mutate_add_step(self, rng):
        rng = np.random.default_rng(rng)
        max_attempts = 10
        if len(self.union_dict) < self.max_estimators:
            for _ in range(max_attempts):
                new_step = self.search_space.generate(rng)
                if new_step.unique_id() not in self.union_dict:
                    self.union_dict[new_step.unique_id()] = new_step
                    return True
        return False

    def _mutate_remove_step(self, rng):
        rng = np.random.default_rng(rng)
        if len(self.union_dict) > 1:
            self.union_dict.pop( rng.choice(list(self.union_dict.keys())))  
            return True
        return False

    def _mutate_replace_step(self, rng):
        rng = np.random.default_rng(rng)        
        changed = self._mutate_remove_step(rng) or self._mutate_add_step(rng)
        return changed

    #TODO mutate one step or multiple?
    def _mutate_note(self, rng):
        rng = np.random.default_rng(rng)
        changed = False
        values = list(self.union_dict.values())
        for step in values:
            if rng.random() < 0.5:
                changed = step.mutate(rng) or changed

        self.union_dict = {step.unique_id(): step for step in values}

        return changed


    def crossover(self, other, rng=None):
        rng = np.random.default_rng(rng)

        cx_funcs = [self._crossover_swap_multiple_nodes, self._crossover_node]
        rng.shuffle(cx_funcs)
        for cx_func in cx_funcs:
            if cx_func(other, rng):
                return True

        return False


    def _crossover_swap_multiple_nodes(self, other, rng):
        rng = np.random.default_rng(rng)
        self_values = list(self.union_dict.values())
        other_values = list(other.union_dict.values())

        rng.shuffle(self_values)
        rng.shuffle(other_values)

        self_idx = rng.integers(0,len(self_values))
        other_idx = rng.integers(0,len(other_values))

        #Note that this is not one-point-crossover since the sequence doesn't matter. this is just a quick way to swap multiple random items
        self_values[:self_idx], other_values[:other_idx] = other_values[:other_idx], self_values[:self_idx]

        self.union_dict = {step.unique_id(): step for step in self_values}
        other.union_dict = {step.unique_id(): step for step in other_values}

        return True


    def _crossover_node(self, other, rng):
        rng = np.random.default_rng(rng)

        changed = False
        self_values = list(self.union_dict.values())
        other_values = list(other.union_dict.values())

        rng.shuffle(self_values)
        rng.shuffle(other_values)

        for self_step, other_step in zip(self_values, other_values):
            if rng.random() < 0.5:
                changed = self_step.crossover(other_step, rng) or changed

        self.union_dict = {step.unique_id(): step for step in self_values}
        other.union_dict = {step.unique_id(): step for step in other_values}

        return changed

    def export_pipeline(self, **kwargs):
        values = list(self.union_dict.values())
        return sklearn.pipeline.make_union(*[step.export_pipeline(**kwargs) for step in values])

    def unique_id(self):
        values = list(self.union_dict.values())
        l = [step.unique_id() for step in values]
        # if all items are strings, then sort them
        if all([isinstance(x, str) for x in l]):
            l.sort()
        l = ["FeatureUnion"] + l
        return TupleIndex(frozenset(l))

class EstimatorNodeIndividual(SklearnIndividual):
    """
    Note that ConfigurationSpace does not support None as a parameter. Instead, use the special string "<NONE>". TPOT will automatically replace instances of this string with the Python None. 

    Parameters
    ----------
    method : type
        The class of the estimator to be used

    space : ConfigurationSpace|dict
        The hyperparameter space to be used. If a dict is passed, hyperparameters are fixed and not learned.

    """
    def __init__(self, method: type, 
                        space: ConfigurationSpace|dict, #TODO If a dict is passed, hyperparameters are fixed and not learned. Is this confusing? Should we make a second node type?
                        hyperparameter_parser: callable = None,
                        rng=None) -> None:
        super().__init__()
        self.method = method
        self.space = space

        if hyperparameter_parser is None:
            self.hyperparameter_parser = default_hyperparameter_parser
        else:
            self.hyperparameter_parser = hyperparameter_parser

        if isinstance(space, dict):
            self.hyperparameters = space
        else:
            rng = np.random.default_rng(rng)
            self.space.seed(rng.integers(0, 2**32))
            self.hyperparameters = dict(self.space.sample_configuration())

    def mutate(self, rng=None):
        if isinstance(self.space, dict): 
            return False

        rng = np.random.default_rng(rng)
        self.space.seed(rng.integers(0, 2**32))
        self.hyperparameters = dict(self.space.sample_configuration())
        return True

    def crossover(self, other, rng=None):
        if isinstance(self.space, dict):
            return False

        rng = np.random.default_rng(rng)
        if self.method != other.method:
            return False

        #loop through hyperparameters, randomly swap items in self.hyperparameters with items in other.hyperparameters
        for hyperparameter in self.space:
            if rng.choice([True, False]):
                if hyperparameter in other.hyperparameters:
                    self.hyperparameters[hyperparameter] = other.hyperparameters[hyperparameter]

        return True



    @final #this method should not be overridden, instead override hyperparameter_parser
    def export_pipeline(self, **kwargs):
        return self.method(**self.hyperparameter_parser(self.hyperparameters))

    def unique_id(self):
        #return a dictionary of the method and the hyperparameters
        method_str = self.method.__name__
        params = list(self.hyperparameters.keys())
        params = sorted(params)

        id_str = f"{method_str}({', '.join([f'{param}={self.hyperparameters[param]}' for param in params])})"

        return id_str

class FSSIndividual(SklearnIndividual):
    def __init__(   self,
                    subsets,
                    rng=None,
                ):

        """
        An individual for representing a specific FeatureSetSelector. 
        The FeatureSetSelector selects a feature list of list of predefined feature subsets.

        This instance will select one set initially. Mutation and crossover can swap the selected subset with another.

        Parameters
        ----------
        subsets : str or list, default=None
            Sets the subsets that the FeatureSetSeletor will select from if set as an option in one of the configuration dictionaries. 
            Features are defined by column names if using a Pandas data frame, or ints corresponding to indexes if using numpy arrays.
            - str : If a string, it is assumed to be a path to a csv file with the subsets. 
                The first column is assumed to be the name of the subset and the remaining columns are the features in the subset.
            - list or np.ndarray : If a list or np.ndarray, it is assumed to be a list of subsets (i.e a list of lists).
            - dict : A dictionary where keys are the names of the subsets and the values are the list of features.
            - int : If an int, it is assumed to be the number of subsets to generate. Each subset will contain one feature.
            - None : If None, each column will be treated as a subset. One column will be selected per subset.
        rng : int, np.random.Generator, optional
            The random number generator. The default is None.
            Only used to select the first subset.

        Returns
        -------
        None    
        """

        subsets = subsets
        rng = np.random.default_rng(rng)

        if isinstance(subsets, str):
            df = pd.read_csv(subsets,header=None,index_col=0)
            df['features'] = df.apply(lambda x: list([x[c] for c in df.columns]),axis=1)
            self.subset_dict = {}
            for row in df.index:
                self.subset_dict[row] = df.loc[row]['features']
        elif isinstance(subsets, dict):
            self.subset_dict = subsets
        elif isinstance(subsets, list) or isinstance(subsets, np.ndarray):
            self.subset_dict = {str(i):subsets[i] for i in range(len(subsets))}
        elif isinstance(subsets, int):
            self.subset_dict = {"{0}".format(i):i for i in range(subsets)}
        else:
            raise ValueError("Subsets must be a string, dictionary, list, int, or numpy array")

        self.names_list = list(self.subset_dict.keys())


        self.selected_subset_name = rng.choice(self.names_list)
        self.sel_subset = self.subset_dict[self.selected_subset_name]


    def mutate(self, rng=None):
        rng = np.random.default_rng(rng)
        #get list of names not including the current one
        names = [name for name in self.names_list if name != self.selected_subset_name]
        self.selected_subset_name = rng.choice(names)
        self.sel_subset = self.subset_dict[self.selected_subset_name]


    def crossover(self, other, rng=None):
        self.selected_subset_name = other.selected_subset_name
        self.sel_subset = other.sel_subset

    def export_pipeline(self, **kwargs):
        return FeatureSetSelector(sel_subset=self.sel_subset, name=self.selected_subset_name)


    def unique_id(self):
        id_str = "FeatureSetSelector({0})".format(self.selected_subset_name)
        return id_str

class FSSNode(SearchSpace):
    def __init__(self,                     
                    subsets,
                ):
        """
        A search space for a FeatureSetSelector. 
        The FeatureSetSelector selects a feature list of list of predefined feature subsets.

        Parameters
        ----------
        subsets : str or list, default=None
            Sets the subsets that the FeatureSetSeletor will select from if set as an option in one of the configuration dictionaries. 
            Features are defined by column names if using a Pandas data frame, or ints corresponding to indexes if using numpy arrays.
            - str : If a string, it is assumed to be a path to a csv file with the subsets. 
                The first column is assumed to be the name of the subset and the remaining columns are the features in the subset.
            - list or np.ndarray : If a list or np.ndarray, it is assumed to be a list of subsets (i.e a list of lists).
            - dict : A dictionary where keys are the names of the subsets and the values are the list of features.
            - int : If an int, it is assumed to be the number of subsets to generate. Each subset will contain one feature.
            - None : If None, each column will be treated as a subset. One column will be selected per subset.

        Returns
        -------
        None    

        """

        self.subsets = subsets

    def generate(self, rng=None) -> SklearnIndividual:
        return FSSIndividual(   
            subsets=self.subsets,
            rng=rng,
            )

class FeatureSetSelector(BaseEstimator, SelectorMixin):
    """
    Select predefined feature subsets.


    """

    def __init__(self, sel_subset=None, name=None):
        """Create a FeatureSetSelector object.

        Parameters
        ----------
        sel_subset: list or int
            If X is a dataframe, items in sel_subset list must correspond to column names
            If X is a numpy array, items in sel_subset list must correspond to column indexes
            int: index of a single column
        Returns
        -------
        None

        """
        self.name = name
        self.sel_subset = sel_subset


    def fit(self, X, y=None):
        """Fit FeatureSetSelector for feature selection

        Parameters
        ----------
        X: array-like of shape (n_samples, n_features)
            The training input samples.
        y: array-like, shape (n_samples,)
            The target values (integers that correspond to classes in classification, real numbers in regression).

        Returns
        -------
        self: object
            Returns a copy of the estimator
        """
        if isinstance(self.sel_subset, int) or isinstance(self.sel_subset, str):
            self.sel_subset = [self.sel_subset]

        #generate  self.feat_list_idx
        if isinstance(X, pd.DataFrame):
            self.feature_names_in_ = X.columns.tolist()
            self.feat_list_idx = sorted([self.feature_names_in_.index(feat) for feat in self.sel_subset])


        elif isinstance(X, np.ndarray):
            self.feature_names_in_ = None#list(range(X.shape[1]))

            self.feat_list_idx = sorted(self.sel_subset)

        n_features = X.shape[1]
        self.mask = np.zeros(n_features, dtype=bool)
        self.mask[np.asarray(self.feat_list_idx)] = True

        return self

    #TODO keep returned as dataframe if input is dataframe? may not be consistent with sklearn

    # def transform(self, X):

    def _get_tags(self):
        tags = {"allow_nan": True, "requires_y": False}
        return tags

    def _get_support_mask(self):
        """
        Get the boolean mask indicating which features are selected
        Returns
        -------
        support : boolean array of shape [# input features]
            An element is True iff its corresponding feature is selected for
            retention.
        """
        return self.mask

class GeneticFeatureSelectorNode(SearchSpace):
    def __init__(self,                     
                    n_features,
                    start_p=0.2,
                    mutation_rate = 0.1,
                    crossover_rate = 0.1,
                    mutation_rate_rate = 0, # These are still experimental but seem to help. Theory is that it takes slower steps as it gets closer to the optimal solution.
                    crossover_rate_rate = 0,# Otherwise is mutation_rate is too small, it takes forever, and if its too large, it never converges.
                    ):
        """
        A node that generates a GeneticFeatureSelectorIndividual. Uses genetic algorithm to select novel subsets of features.

        Parameters
        ----------
        n_features : int
            Number of features in the dataset.
        start_p : float
            Probability of selecting a given feature for the initial subset of features.
        mutation_rate : float
            Probability of adding/removing a feature from the subset of features.
        crossover_rate : float
            Probability of swapping a feature between two subsets of features.
        mutation_rate_rate : float
            Probability of changing the mutation rate. (experimental)
        crossover_rate_rate : float
            Probability of changing the crossover rate. (experimental)

        """

        self.n_features = n_features
        self.start_p = start_p
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate
        self.mutation_rate_rate = mutation_rate_rate
        self.crossover_rate_rate = crossover_rate_rate


    def generate(self, rng=None) -> SklearnIndividual:
        return GeneticFeatureSelectorIndividual(   mask=self.n_features,
                                                    start_p=self.start_p,
                                                    mutation_rate=self.mutation_rate,
                                                    crossover_rate=self.crossover_rate,
                                                    mutation_rate_rate=self.mutation_rate_rate,
                                                    crossover_rate_rate=self.crossover_rate_rate,
                                                    rng=rng
                                                )

class GraphKey():
    '''
    A class that can be used as a key for a graph.

    Parameters
    ----------
    graph : (nx.Graph)
        The graph to use as a key. Node Attributes are used for the hash.
    matched_label : (str)
        The node attribute to consider for the hash.
    '''

    def __init__(self, graph, matched_label='label') -> None:#['hyperparameters', 'method_class']) -> None:


        self.graph = graph
        self.matched_label = matched_label
        self.node_match = partial(node_match, matched_labels=[matched_label])
        self.key = int(nx.weisfeiler_lehman_graph_hash(self.graph, node_attr=self.matched_label),16) #hash(tuple(sorted([val for (node, val) in self.graph.degree()])))


    #If hash is different, node is definitely different
    # https://arxiv.org/pdf/2002.06653.pdf
    def __hash__(self) -> int:

        return self.key

    #If hash is same, use __eq__ to know if they are actually different
    def __eq__(self, other):
        return nx.is_isomorphic(self.graph, other.graph, node_match=self.node_match)

class GraphPipelineIndividual(SklearnIndividual):
    """
        Defines a search space of pipelines in the shape of a Directed Acyclic Graphs. The search spaces for root, leaf, and inner nodes can be defined separately if desired.
        Each graph will have a single root serving as the final estimator which is drawn from the `root_search_space`. If the `leaf_search_space` is defined, all leaves 
        in the pipeline will be drawn from that search space. If the `leaf_search_space` is not defined, all leaves will be drawn from the `inner_search_space`.
        Nodes that are not leaves or roots will be drawn from the `inner_search_space`. If the `inner_search_space` is not defined, there will be no inner nodes.

        `cross_val_predict_cv`, `method`, `memory`, and `use_label_encoder` are passed to the GraphPipeline object when the pipeline is exported and not directly used in the search space.

        Exports to a GraphPipeline object.

        Parameters
        ----------

        root_search_space: SearchSpace
            The search space for the root node of the graph. This node will be the final estimator in the pipeline.

        inner_search_space: SearchSpace, optional
            The search space for the inner nodes of the graph. If not defined, there will be no inner nodes.

        leaf_search_space: SearchSpace, optional
            The search space for the leaf nodes of the graph. If not defined, the leaf nodes will be drawn from the inner_search_space.

        crossover_same_depth: bool, optional
            If True, crossover will only occur between nodes at the same depth in the graph. If False, crossover will occur between nodes at any depth.

        cross_val_predict_cv: int, cross-validation generator or an iterable, optional
            Determines the cross-validation splitting strategy used in inner classifiers or regressors

        method: str, optional
            The prediction method to use for the inner classifiers or regressors. If 'auto', it will try to use predict_proba, decision_function, or predict in that order.

        memory: str or object with the joblib.Memory interface, optional
            Used to cache the input and outputs of nodes to prevent refitting or computationally heavy transformations. By default, no caching is performed. If a string is given, it is the path to the caching directory.

        use_label_encoder: bool, optional
            If True, the label encoder is used to encode the labels to be 0 to N. If False, the label encoder is not used.
            Mainly useful for classifiers (XGBoost) that require labels to be ints from 0 to N.
            Can also be a sklearn.preprocessing.LabelEncoder object. If so, that label encoder is used.

        rng: int, RandomState instance or None, optional
            Seed for sampling the first graph instance. 

        """

    def __init__(
            self,  
            root_search_space: SearchSpace, 
            leaf_search_space: SearchSpace = None, 
            inner_search_space: SearchSpace = None, 
            max_size: int = np.inf,
            crossover_same_depth: bool = False,
            cross_val_predict_cv: Union[int, Callable] = 0, #signature function(estimator, X, y=none)
            method: str = 'auto',
            use_label_encoder: bool = False,
            rng=None):

        super().__init__()

        self.__debug = False

        rng = np.random.default_rng(rng)

        self.root_search_space = root_search_space
        self.leaf_search_space = leaf_search_space
        self.inner_search_space = inner_search_space
        self.max_size = max_size
        self.crossover_same_depth = crossover_same_depth

        self.cross_val_predict_cv = cross_val_predict_cv
        self.method = method
        self.use_label_encoder = use_label_encoder

        self.root = self.root_search_space.generate(rng)
        self.graph = nx.DiGraph()
        self.graph.add_node(self.root)

        if self.leaf_search_space is not None:
            self.leaf = self.leaf_search_space.generate(rng)
            self.graph.add_node(self.leaf)
            self.graph.add_edge(self.root, self.leaf)

        if self.inner_search_space is None and self.leaf_search_space is None:
            self.mutate_methods_list = [self._mutate_node]
            self.crossover_methods_list = [self._crossover_swap_branch,]#[self._crossover_swap_branch, self._crossover_swap_node, self._crossover_take_branch]  #TODO self._crossover_nodes, 

        else:
            self.mutate_methods_list = [self._mutate_insert_leaf, self._mutate_insert_inner_node, self._mutate_remove_node, self._mutate_node, self._mutate_insert_bypass_node]
            self.crossover_methods_list = [self._crossover_swap_branch, self._crossover_nodes, self._crossover_take_branch ]#[self._crossover_swap_branch, self._crossover_swap_node, self._crossover_take_branch]  #TODO self._crossover_nodes, 

        self.merge_duplicated_nodes_toggle = True

        self.graphkey = None


    def mutate(self, rng=None):
        rng = np.random.default_rng(rng)
        rng.shuffle(self.mutate_methods_list)
        for mutate_method in self.mutate_methods_list:
            if mutate_method(rng=rng):

                if self.merge_duplicated_nodes_toggle:
                    self._merge_duplicated_nodes()

                if self.__debug:
                    print(mutate_method)

                    if self.root not in self.graph.nodes:
                        print('lost root something went wrong with ', mutate_method)

                    if len(self.graph.predecessors(self.root)) > 0:
                        print('root has parents ', mutate_method)

                    if any([n in nx.ancestors(self.graph,n) for n in self.graph.nodes]):
                        print('a node is connecting to itself...')

                    if self.__debug:
                        try:
                            nx.find_cycle(self.graph)
                            print('something went wrong with ', mutate_method)
                        except:
                            pass

                self.graphkey = None

        return False




    def _mutate_insert_leaf(self, rng=None):
        rng = np.random.default_rng(rng)
        if self.max_size > self.graph.number_of_nodes():
            sorted_nodes_list = list(self.graph.nodes)
            rng.shuffle(sorted_nodes_list) #TODO: sort by number of children and/or parents? bias model one way or another
            for node in sorted_nodes_list:
                #if leafs are protected, check if node is a leaf
                #if node is a leaf, skip because we don't want to add node on top of node
                if (self.leaf_search_space is not None #if leafs are protected
                    and   len(list(self.graph.successors(node))) == 0 #if node is leaf
                    and  len(list(self.graph.predecessors(node))) > 0 #except if node is root, in which case we want to add a leaf even if it happens to be a leaf too
                    ):

                    continue

                #If node *is* the root or is not a leaf, add leaf node. (dont want to add leaf on top of leaf)
                if self.leaf_search_space is not None:
                    new_node = self.leaf_search_space.generate(rng)
                else:
                    new_node = self.inner_search_space.generate(rng)

                self.graph.add_node(new_node)
                self.graph.add_edge(node, new_node)
                return True

        return False

    def _mutate_insert_inner_node(self, rng=None):
        """
        Finds an edge in the graph and inserts a new node between the two nodes. Removes the edge between the two nodes.
        """
        rng = np.random.default_rng(rng)
        if self.max_size > self.graph.number_of_nodes():
            sorted_nodes_list = list(self.graph.nodes)
            sorted_nodes_list2 = list(self.graph.nodes)
            rng.shuffle(sorted_nodes_list) #TODO: sort by number of children and/or parents? bias model one way or another
            rng.shuffle(sorted_nodes_list2)
            for node in sorted_nodes_list:
                #loop through children of node
                for child_node in list(self.graph.successors(node)):

                    if child_node is not node and child_node not in nx.ancestors(self.graph, node):
                        if self.leaf_search_space is not None:
                            #If if we are protecting leafs, dont add connection into a leaf
                            if len(list(nx.descendants(self.graph,node))) ==0 :
                                continue

                        new_node = self.inner_search_space.generate(rng)

                        self.graph.add_node(new_node)
                        self.graph.add_edges_from([(node, new_node), (new_node, child_node)])
                        self.graph.remove_edge(node, child_node)
                        return True

        return False


    def _mutate_remove_node(self, rng=None):
        '''
        Removes a randomly chosen node and connects its parents to its children.
        If the node is the only leaf for an inner node and 'leaf_search_space' is not none, we do not remove it.
        '''
        rng = np.random.default_rng(rng)
        nodes_list = list(self.graph.nodes)
        nodes_list.remove(self.root)
        leaves = get_leaves(self.graph)

        while len(nodes_list) > 0:
            node = rng.choice(nodes_list)
            nodes_list.remove(node)

            if self.leaf_search_space is not None and len(list(nx.descendants(self.graph,node))) == 0 : #if the node is a leaf
                if len(leaves) <= 1:
                    continue #dont remove the last leaf
                leaf_parents = self.graph.predecessors(node)

                # if any of the parents of the node has one one child, continue
                if any([len(list(self.graph.successors(lp))) < 2 for lp in leaf_parents]): #dont remove a leaf if it is the only input into another node.
                    continue

                remove_and_stitch(self.graph, node)
                remove_nodes_disconnected_from_node(self.graph, self.root)
                return True

            else:
                remove_and_stitch(self.graph, node)
                remove_nodes_disconnected_from_node(self.graph, self.root)
                return True

        return False



    def _mutate_node(self, rng=None):
        '''
        Mutates the hyperparameters for a randomly chosen node in the graph.
        '''
        rng = np.random.default_rng(rng)
        sorted_nodes_list = list(self.graph.nodes)
        rng.shuffle(sorted_nodes_list)
        completed_one = False
        for node in sorted_nodes_list:
            if node.mutate(rng):
                return True
        return False

    def _mutate_remove_edge(self, rng=None):
        '''
        Deletes an edge as long as deleting that edge does not make the graph disconnected.
        '''
        rng = np.random.default_rng(rng)
        sorted_nodes_list = list(self.graph.nodes)
        rng.shuffle(sorted_nodes_list)
        for child_node in sorted_nodes_list:
            parents = list(self.graph.predecessors(child_node))
            if len(parents) > 1: # if it has more than one parent, you can remove an edge (if this is the only child of a node, it will become a leaf)

                for parent_node in parents:
                    # if removing the egde will make the parent_node a leaf node, skip
                    if self.leaf_search_space is not None and len(list(self.graph.successors(parent_node))) < 2:
                        continue

                    self.graph.remove_edge(parent_node, child_node)
                    return True
        return False   

    def _mutate_add_edge(self, rng=None):
        '''
        Randomly add an edge from a node to another node that is not an ancestor of the first node.
        '''
        rng = np.random.default_rng(rng)
        sorted_nodes_list = list(self.graph.nodes)
        rng.shuffle(sorted_nodes_list)
        for child_node in sorted_nodes_list:
            for parent_node in sorted_nodes_list:
                if self.leaf_search_space is not None:
                    if len(list(self.graph.successors(parent_node))) == 0:
                        continue

                # skip if
                # - parent and child are the same node
                # - edge already exists
                # - child is an ancestor of parent
                if  (child_node is not parent_node) and not self.graph.has_edge(parent_node,child_node) and (child_node not in nx.ancestors(self.graph, parent_node)):
                    self.graph.add_edge(parent_node,child_node)
                    return True

        return False

    def _mutate_insert_bypass_node(self, rng=None):
        """
        Pick two nodes (doesn't necessarily need to be connected). Create a new node. connect one node to the new node and the new node to the other node.
        Does not remove any edges.
        """
        rng = np.random.default_rng(rng)
        if self.max_size > self.graph.number_of_nodes():
            sorted_nodes_list = list(self.graph.nodes)
            sorted_nodes_list2 = list(self.graph.nodes)
            rng.shuffle(sorted_nodes_list) #TODO: sort by number of children and/or parents? bias model one way or another
            rng.shuffle(sorted_nodes_list2)
            for node in sorted_nodes_list:
                for child_node in sorted_nodes_list2:
                    if child_node is not node and child_node not in nx.ancestors(self.graph, node):
                        if self.leaf_search_space is not None:
                            #If if we are protecting leafs, dont add connection into a leaf
                            if len(list(nx.descendants(self.graph,node))) ==0 :
                                continue

                        new_node = self.inner_search_space.generate(rng)

                        self.graph.add_node(new_node)
                        self.graph.add_edges_from([(node, new_node), (new_node, child_node)])
                        return True

        return False


    def crossover(self, ind2, rng=None):
        '''
        self is the first individual, ind2 is the second individual
        If crossover_same_depth, it will select graphindividuals at the same recursive depth.
        Otherwise, it will select graphindividuals randomly from the entire graph and its subgraphs.

        This does not impact graphs without subgraphs. And it does not impacts nodes that are not graphindividuals. Cros
        '''

        rng = np.random.default_rng(rng)

        rng.shuffle(self.crossover_methods_list)

        finished = False

        for crossover_method in self.crossover_methods_list:
            if crossover_method(ind2, rng=rng):
                self._merge_duplicated_nodes()
                finished = True
                break

        if self.__debug:
            try:
                nx.find_cycle(self.graph)
                print('something went wrong with ', crossover_method)
            except:
                pass

        if finished:
            self.graphkey = None

        return finished


    def _crossover_swap_branch(self, G2, rng=None):
        '''
        swaps a branch from parent1 with a branch from parent2. does not modify parent2
        '''
        rng = np.random.default_rng(rng)

        if self.crossover_same_depth:
            pair_gen = select_nodes_same_depth(self.graph, self.root, G2.graph, G2.root, rng=rng)
        else:
            pair_gen = select_nodes_randomly(self.graph, G2.graph, rng=rng)

        for node1, node2 in pair_gen:
            #TODO: if root is in inner_search_space, then do use it?
            if node1 is self.root or node2 is G2.root: #dont want to add root as inner node
                continue

            #check if node1 is a leaf and leafs are protected, don't add an input to the leave
            if self.leaf_search_space is not None: #if we are protecting leaves,
                node1_is_leaf = len(list(self.graph.successors(node1))) == 0
                node2_is_leaf = len(list(G2.graph.successors(node2))) == 0
                #if not ((node1_is_leaf and node1_is_leaf) or (not node1_is_leaf and not node2_is_leaf)): #if node1 is a leaf
                #if (node1_is_leaf and (not node2_is_leaf)) or ( (not node1_is_leaf) and node2_is_leaf):
                if not node1_is_leaf:
                    #only continue if node1 and node2 are both leaves or both not leaves
                    continue

            temp_graph_1 = self.graph.copy()
            temp_graph_1.remove_node(node1)
            remove_nodes_disconnected_from_node(temp_graph_1, self.root)

            #isolating the branch
            branch2 = G2.graph.copy()
            n2_descendants = nx.descendants(branch2,node2)
            for n in list(branch2.nodes):
                if n not in n2_descendants and n is not node2: #removes all nodes not in the branch
                    branch2.remove_node(n)

            branch2 = copy.deepcopy(branch2)
            branch2_root = get_roots(branch2)[0]
            temp_graph_1.add_edges_from(branch2.edges)
            for p in list(self.graph.predecessors(node1)):
                temp_graph_1.add_edge(p,branch2_root)

            if temp_graph_1.number_of_nodes() > self.max_size:
                continue

            self.graph = temp_graph_1

            return True
        return False


    def _crossover_take_branch(self, G2, rng=None):
        '''
        Takes a subgraph from Parent2 and add it to a randomly chosen node in Parent1.
        '''
        rng = np.random.default_rng(rng)

        if self.crossover_same_depth:
            pair_gen = select_nodes_same_depth(self.graph, self.root, G2.graph, G2.root, rng=rng)
        else:
            pair_gen = select_nodes_randomly(self.graph, G2.graph, rng=rng)

        for node1, node2 in pair_gen:
            #TODO: if root is in inner_search_space, then do use it?
            if node2 is G2.root: #dont want to add root as inner node
                continue


            #check if node1 is a leaf and leafs are protected, don't add an input to the leave
            if self.leaf_search_space is not None and len(list(self.graph.successors(node1))) == 0:
                continue

            #icheck if node2 is graph individual
            # if isinstance(node2,GraphIndividual):
            #     if not ((isinstance(node2,GraphIndividual) and ("Recursive" in self.inner_search_space or "Recursive" in self.leaf_search_space))):
            #         continue

            #isolating the branch
            branch2 = G2.graph.copy()
            n2_descendants = nx.descendants(branch2,node2)
            for n in list(branch2.nodes):
                if n not in n2_descendants and n is not node2: #removes all nodes not in the branch
                    branch2.remove_node(n)

            #if node1 plus node2 branch has more than max_children, skip
            if branch2.number_of_nodes() + self.graph.number_of_nodes() > self.max_size:
                continue

            branch2 = copy.deepcopy(branch2)
            branch2_root = get_roots(branch2)[0]
            self.graph.add_edges_from(branch2.edges)
            self.graph.add_edge(node1,branch2_root)

            return True
        return False



    def _crossover_nodes(self, G2, rng=None):
        '''
        Swaps the hyperparamters of one randomly chosen node in Parent1 with the hyperparameters of randomly chosen node in Parent2.
        '''
        rng = np.random.default_rng(rng)

        if self.crossover_same_depth:
            pair_gen = select_nodes_same_depth(self.graph, self.root, G2.graph, G2.root, rng=rng)
        else:
            pair_gen = select_nodes_randomly(self.graph, G2.graph, rng=rng)

        for node1, node2 in pair_gen:

            #if both nodes are leaves
            if len(list(self.graph.successors(node1)))==0 and len(list(G2.graph.successors(node2)))==0:
                if node1.crossover(node2):
                    return True


            #if both nodes are inner nodes
            if len(list(self.graph.successors(node1)))>0 and len(list(G2.graph.successors(node2)))>0:
                if len(list(self.graph.predecessors(node1)))>0 and len(list(G2.graph.predecessors(node2)))>0:
                    if node1.crossover(node2):
                        return True

            #if both nodes are root nodes
            if node1 is self.root and node2 is G2.root:
                if node1.crossover(node2):
                    return True


        return False

    #not including the nodes, just their children
    #Finds leaves attached to nodes and swaps them
    def _crossover_swap_leaf_at_node(self, G2, rng=None):
        rng = np.random.default_rng(rng)

        if self.crossover_same_depth:
            pair_gen = select_nodes_same_depth(self.graph, self.root, G2.graph, G2.root, rng=rng)
        else:
            pair_gen = select_nodes_randomly(self.graph, G2.graph, rng=rng)

        success = False
        for node1, node2 in pair_gen:
            # if leaves are protected node1 and node2 must both be leaves or both be inner nodes
            if self.leaf_search_space is not None and not (len(list(self.graph.successors(node1)))==0 ^ len(list(G2.graph.successors(node2)))==0):
                continue
            #self_leafs = [c for c in nx.descendants(self.graph,node1) if len(list(self.graph.successors(c)))==0 and c is not node1]
            node_leafs = [c for c in nx.descendants(G2.graph,node2) if len(list(G2.graph.successors(c)))==0 and c is not node2]

            # if len(self_leafs) >0:
            #     for c in self_leafs:
            #         if random.choice([True,False]):
            #             self.graph.remove_node(c)
            #             G2.graph.add_edge(node2, c)
            #             success = True

            if len(node_leafs) >0:
                for c in node_leafs:
                    if rng.choice([True,False]):
                        G2.graph.remove_node(c)
                        self.graph.add_edge(node1, c)
                        success = True

        return success



    #TODO edit so that G2 is not modified
    def _crossover_swap_node(self, G2, rng=None):
        '''
        Swaps randomly chosen node from Parent1 with a randomly chosen node from Parent2.
        '''
        rng = np.random.default_rng(rng)

        if self.crossover_same_depth:
            pair_gen = select_nodes_same_depth(self.graph, self.root, G2.graph, G2.root, rng=rng)
        else:
            pair_gen = select_nodes_randomly(self.graph, G2.graph, rng=rng)

        for node1, node2 in pair_gen:
            if node1 is self.root or node2 is G2.root: #TODO: allow root
                continue

            #if leaves are protected
            if self.leaf_search_space is not None:
                #if one node is a leaf, the other must be a leaf
                if not((len(list(self.graph.successors(node1)))==0) ^ (len(list(G2.graph.successors(node2)))==0)):
                    continue #only continue if both are leaves, or both are not leaves


            n1_s = self.graph.successors(node1)
            n1_p = self.graph.predecessors(node1)

            n2_s = G2.graph.successors(node2)
            n2_p = G2.graph.predecessors(node2)

            self.graph.remove_node(node1)
            G2.graph.remove_node(node2)

            self.graph.add_node(node2)

            self.graph.add_edges_from([ (node2, n) for n in n1_s])
            G2.graph.add_edges_from([ (node1, n) for n in n2_s])

            self.graph.add_edges_from([ (n, node2) for n in n1_p])
            G2.graph.add_edges_from([ (n, node1) for n in n2_p])

            return True

        return False


    def _merge_duplicated_nodes(self):

        graph_changed = False
        merged = False
        while(not merged):
            node_list = list(self.graph.nodes)
            merged = True
            for node, other_node in itertools.product(node_list, node_list):
                if node is other_node:
                    continue

                #If nodes are same class/hyperparameters
                if node.unique_id() == other_node.unique_id():
                    node_children = set(self.graph.successors(node))
                    other_node_children = set(self.graph.successors(other_node))
                    #if nodes have identical children, they can be merged
                    if node_children == other_node_children:
                        for other_node_parent in list(self.graph.predecessors(other_node)):
                            if other_node_parent not in self.graph.predecessors(node):
                                self.graph.add_edge(other_node_parent,node)

                        self.graph.remove_node(other_node)
                        merged=False
                        graph_changed = True
                        break

        return graph_changed


    def export_pipeline(self, memory=None, **kwargs):
        estimator_graph = self.graph.copy()

        #mapping = {node:node.method_class(**node.hyperparameters) for node in estimator_graph}
        label_remapping = {}
        label_to_instance = {}

        for node in estimator_graph:
            this_pipeline_node = node.export_pipeline(memory=memory, **kwargs)
            found_unique_label = False
            i=1
            while not found_unique_label:
                label = "{0}_{1}".format(this_pipeline_node.__class__.__name__, i)
                if label not in label_to_instance:
                    found_unique_label = True
                else:
                    i+=1

            label_remapping[node] = label
            label_to_instance[label] = this_pipeline_node

        estimator_graph = nx.relabel_nodes(estimator_graph, label_remapping)

        for label, instance in label_to_instance.items():
            estimator_graph.nodes[label]["instance"] = instance

        return tpot2.GraphPipeline(graph=estimator_graph, memory=memory, use_label_encoder=self.use_label_encoder, method=self.method, cross_val_predict_cv=self.cross_val_predict_cv)


    def plot(self):
        G = self.graph.reverse()
        #TODO clean this up
        try:
            pos = nx.planar_layout(G)  # positions for all nodes
        except:
            pos = nx.shell_layout(G)
        # nodes
        options = {'edgecolors': 'tab:gray', 'node_size': 800, 'alpha': 0.9}
        nodelist = list(G.nodes)
        node_color = [plt.cm.Set1(G.nodes[n]['recursive depth']) for n in G]

        fig, ax = plt.subplots()

        nx.draw(G, pos, nodelist=nodelist, node_color=node_color, ax=ax,  **options)


        '''edgelist = []
        for n in n1.node_set:
            for child in n.children:
                edgelist.append((n,child))'''

        # edges
        #nx.draw_networkx_edges(G, pos, width=3.0, arrows=True)
        '''nx.draw_networkx_edges(
            G,
            pos,
            edgelist=[edgelist],
            width=8,
            alpha=0.5,
            edge_color='tab:red',
        )'''



        # some math labels
        labels = {}
        for i, n in enumerate(G.nodes):
            labels[n] = n.method_class.__name__ + "\n" + str(n.hyperparameters)


        nx.draw_networkx_labels(G, pos, labels,ax=ax, font_size=7, font_color='black')

        plt.tight_layout()
        plt.axis('off')
        plt.show()


    def unique_id(self):
        if self.graphkey is None:
            #copy self.graph
            new_graph = self.graph.copy()
            for n in new_graph.nodes:
                new_graph.nodes[n]['label'] = n.unique_id()

            new_graph = nx.convert_node_labels_to_integers(new_graph)
            self.graphkey = GraphKey(new_graph)

        return self.graphkey