class_docstr: The :class:`History` class helps to build a genealogy of all the
  individuals produced in the evolution. It contains two attributes,
  the :attr:`genealogy_tree` that is a dictionary of lists indexed by
  individual, the list contain the indices of the parents. The second
  attribute :attr:`genealogy_history` contains every individual indexed
  by their individual number as in the genealogy tree.
  
  The produced genealogy tree is compatible with `NetworkX
  <http://networkx.lanl.gov/index.html>`_, here is how to plot the genealogy
  tree ::
  
      history = History()
  
      # Decorate the variation operators
      toolbox.decorate("mate", history.decorator)
      toolbox.decorate("mutate", history.decorator)
  
      # Create the population and populate the history
      population = toolbox.population(n=POPSIZE)
      history.update(population)
  
      # Do the evolution, the decorators will take care of updating the
      # history
      # [...]
  
      import matplotlib.pyplot as plt
      import networkx
  
      graph = networkx.DiGraph(history.genealogy_tree)
      graph = graph.reverse()     # Make the graph top-down
      colors = [toolbox.evaluate(history.genealogy_history[i])[0] for i in graph]
      networkx.draw(graph, node_color=colors)
      plt.show()
  
  Using NetworkX in combination with `pygraphviz
  <http://networkx.lanl.gov/pygraphviz/>`_ (dot layout) this amazing
  genealogy tree can be obtained from the OneMax example with a population
  size of 20 and 5 generations, where the color of the nodes indicate their
  fitness, blue is low and red is high.
  
  .. image:: /_images/genealogy.png
     :width: 67%
  
  .. note::
     The genealogy tree might get very big if your population and/or the
     number of generation is large.
class_docstr_tok: ["The",":","class",":","`","History","`","class","helps","to","build","a","genealogy","of","all","the","individuals","produced","in","the","evolution",".","It","contains","two","attributes",",","the",":","attr",":","`","genealogy_tree","`","that","is","a","dictionary","of","lists","indexed","by","individual",",","the","list","contain","the","indices","of","the","parents",".","The","second","attribute",":","attr",":","`","genealogy_history","`","contains","every","individual","indexed","by","their","individual","number","as","in","the","genealogy","tree",".","The","produced","genealogy","tree","is","compatible","with","`","NetworkX","<","http",":","\/\/networkx.lanl.gov\/index.html",">","`","_",",","here","is","how","to","plot","the","genealogy","tree",":",":","history","=","History","(",")","#","Decorate","the","variation","operators","toolbox.decorate","(","``","mate","''",",","history.decorator",")","toolbox.decorate","(","``","mutate","''",",","history.decorator",")","#","Create","the","population","and","populate","the","history","population","=","toolbox.population","(","n=POPSIZE",")","history.update","(","population",")","#","Do","the","evolution",",","the","decorators","will","take","care","of","updating","the","#","history","#","[","...","]","import","matplotlib.pyplot","as","plt","import","networkx","graph","=","networkx.DiGraph","(","history.genealogy_tree",")","graph","=","graph.reverse","(",")","#","Make","the","graph","top-down","colors","=","[","toolbox.evaluate","(","history.genealogy_history","[","i","]",")","[","0","]","for","i","in","graph","]","networkx.draw","(","graph",",","node_color=colors",")","plt.show","(",")","Using","NetworkX","in","combination","with","`","pygraphviz","<","http",":","\/\/networkx.lanl.gov\/pygraphviz\/",">","`","_","(","dot","layout",")","this","amazing","genealogy","tree","can","be","obtained","from","the","OneMax","example","with","a","population","size","of","20","and","5","generations",",","where","the","color","of","the","nodes","indicate","their","fitness",",","blue","is","low","and","red","is","high",".","..","image",":",":","\/_images\/genealogy.png",":","width",":","67","%","..","note",":",":","The","genealogy","tree","might","get","very","big","if","your","population","and\/or","the","number","of","generation","is","large","."]
docstr: Provide the genealogy tree of an *individual*. The individual must
  have an attribute :attr:`history_index` as defined by
  :func:`~deap.tools.History.update` in order to retrieve its associated
  genealogy tree. The returned graph contains the parents up to
  *max_depth* variations before this individual. If not provided
  the maximum depth is up to the beginning of the evolution.
  
  :param individual: The individual at the root of the genealogy tree.
  :param max_depth: The approximate maximum distance between the root
                    (individual) and the leaves (parents), optional.
  :returns: A dictionary where each key is an individual index and the
            values are a tuple corresponding to the index of the parents.
docstr_tok: ["Provide","the","genealogy","tree","of","an","*","individual","*",".","The","individual","must","have","an","attribute",":","attr",":","`","history_index","`","as","defined","by",":","func",":","`","~deap.tools.History.update","`","in","order","to","retrieve","its","associated","genealogy","tree",".","The","returned","graph","contains","the","parents","up","to","*","max_depth","*","variations","before","this","individual",".","If","not","provided","the","maximum","depth","is","up","to","the","beginning","of","the","evolution",".",":","param","individual",":","The","individual","at","the","root","of","the","genealogy","tree",".",":","param","max_depth",":","The","approximate","maximum","distance","between","the","root","(","individual",")","and","the","leaves","(","parents",")",",","optional",".",":","returns",":","A","dictionary","where","each","key","is","an","individual","index","and","the","values","are","a","tuple","corresponding","to","the","index","of","the","parents","."]
code: def getGenealogy(self, individual, max_depth=float("inf")):
      """Provide the genealogy tree of an *individual*. The individual must
      have an attribute :attr:`history_index` as defined by
      :func:`~deap.tools.History.update` in order to retrieve its associated
      genealogy tree. The returned graph contains the parents up to
      *max_depth* variations before this individual. If not provided
      the maximum depth is up to the beginning of the evolution.
  
      :param individual: The individual at the root of the genealogy tree.
      :param max_depth: The approximate maximum distance between the root
                        (individual) and the leaves (parents), optional.
      :returns: A dictionary where each key is an individual index and the
                values are a tuple corresponding to the index of the parents.
      """
      gtree = {}
      visited = set()  # Adds memory to the breadth first search
  
      def genealogy(index, depth):
          if index not in self.genealogy_tree:
              return
          depth += 1
          if depth > max_depth:
              return
          parent_indices = self.genealogy_tree[index]
          gtree[index] = parent_indices
          for ind in parent_indices:
              if ind not in visited:
                  genealogy(ind, depth)
              visited.add(ind)
  
      genealogy(individual.history_index, 0)
      return gtree
  
imports: from bisect import bisect_right
  from collections import defaultdict
  from copy import deepcopy
  from functools import partial
  from itertools import chain
  from operator import eq
label_desc: Use image node_id 4 for calling the History obj's underlying member method code with example usage: obj.getGenealogy(individual, max_depth) and returns: gtree