familyGraph.js

let tree = [];
function findPerson(json, id){
   for(personIndex in json){
         if(json[personIndex].id == id){
            return json[personIndex];
         }
   }
}
/**
 * conversion du json en paramètre en json pour l'outil de graphe généalogique
 */
function createJsonGlobal(json){
   let jsonFamily = JSON.parse(JSON.stringify(json)); //clone de l'objet
   for(personIndex in jsonFamily){
         person = jsonFamily[personIndex];
         person.parents = !person.hasOwnProperty('parents') ? new Array() : person.parents;
         person.sex = !person.hasOwnProperty('sex') ? "person" : person.sex; // sexe indéfini pour l'instant
         person.children = !person.hasOwnProperty('children') ? new Array() : person.children;
         person.partners = !person.hasOwnProperty('partners') ? new Array() : person.partners;
         if(person.prenom != null){
            person.name = person.prenom;
            delete person.prenom;
         }
         if(person.nom != null){
            person.name += ' ' + person.nom;
            delete person.nom;
         }
         if(person.mere != null && person.pere != null && person.mere !== "" && person.pere !== ""){
            let mere = findPerson(jsonFamily, person.mere);
            let pere = findPerson(jsonFamily, person.pere);

            mere.partners.indexOf(pere.id) === -1 ? mere.partners.push(pere.id) :1;
            pere.partners.indexOf(mere.id) === -1 ? pere.partners.push(mere.id) :1;
         }
         if(person.mere != null && person.mere !== ""){
            let mere = findPerson(jsonFamily, person.mere);

            person.parents = !person.hasOwnProperty('parents') ? new Array() : person.parents;
            mere.sex = !mere.hasOwnProperty('sex') || mere.sex === "person" ? "female" : mere.sex;
            person.parents.indexOf(mere.id) === -1 ? person.parents.push(mere.id) :1;
            

            mere.children = !mere.hasOwnProperty('children') ? new Array() : mere.children;
            mere.partners = !mere.hasOwnProperty('partners') ? new Array() : mere.partners;
            mere.children.indexOf(person.id) === -1 ? mere.children.push(person.id) :1;
      
            delete person.mere;
         }
         if(person.pere != null && person.pere !== ""){
            let pere = findPerson(jsonFamily, person.pere);

            person.parents = !person.hasOwnProperty('parents') ? new Array() : person.parents;
            pere.sex = !pere.hasOwnProperty('sex') || pere.sex === "person" ? "male" : pere.sex;
            person.parents.indexOf(pere.id) === -1 ? person.parents.push(pere.id) :1;
            pere.children = !pere.hasOwnProperty('children') ? new Array() : pere.children;
            pere.partners = !pere.hasOwnProperty('partners') ? new Array() : pere.partners;
            pere.children.indexOf(person.id) === -1 ? pere.children.push(person.id) :1;

            delete person.pere;
         }
   }

   window.jsonGlobal = jsonFamily;
}


   /**
    * On crée un graphe à partir des données du JSON "tree". On créé 1 noeud "meta" pour
    * pour chaque père/mère - enfant ou noeud partenaire, enfant. Ne représente pas une
    * vraie généalogie mais fait une recherche en profondeur pour mettre en ordre les
    * personnes "noeuds" plus pertinemment puisqu'on s'assure que tous les enfants sont
    * vus avant les parents.
    * On mappe un identifiant à l'index correspondant dans l'arbre du JSON.
    */
   
   let graph = {};
   let node_width = 135;
   let node_height = 45;
   let horiz_margin = 75;
   let vert_margin = 45;
   
   function build_graph() {
      for (let t = 0 ; t < tree.length; t++) {
         graph[tree[t].id] = {id: tree[t].id,
                              index: t,
                              children: [],
                              partners: [],
                              parents: [],
                              layer: 0,
                              name: tree[t].name};
      }
      for (let t = 0 ; t < tree.length; t++) {
         let person = tree[t];
         let person_node = graph[person.id];
         for (let c= 0; c < person.children.length; c++) {
            let child_node = graph[person.children[c]];
            if(child_node)
            {
               person_node.children.push(child_node);
               child_node.parents.push(person_node);
            }
            
         }
         for (let p = 0; p < person.partners.length; p++) {
            person_node.partners.push(graph[person.partners[p]]);
         }
      }
   }
   
   function dfs() {
      /* Recherche en profondeur dans le graphe. Chaque noeud est l'id d'une personne.
         Retourne un tableau avec les id dans l'ordre où si u est un enfant de v,
         u apparaît après v.
      */
      let result = [];
      let seen = [];
   
      function impl(node) {
         seen[node.id] = true;
         for (let out = 0; out < node.children.length; out++) {
            let child = node.children[out];
            if (!seen[child.id]) {
               impl(child);
            }
         }
         result.push(node);
      }
      for (let id in graph) {
         if (!seen[Number(id)]) {
            impl(graph[id]);
         }
      }
      return result;
   }
   
   /**
    * Retourne le min et max entre A et B
    */
   function min(a, b) {
      if (a === undefined) {
         return b;
      } else {
         return Math.min(a, b);
      }
   }
   function max(a, b) {
      if (a === undefined) {
         return b;
      } else {
         return Math.max(a, b);
      }
   }
   
   
   /**
    * On attribue un rang (niveau) à chaque personne.
    * On commence par l'enfant et on assigne à chaque personne un niveau
    * de telle sorte que la personne est au-dessus de ses enfants.
    */
   function rank() {
      let nodes = dfs();
   
      /**
      *  On attribue le niveau 0 aux personnes sans enfants puis on met
      *  leurs parents au niveau du dessus et ainsi de suite.
      */
      for (let id = 0; id < nodes.length; id++) {
         let node = nodes[id];
         if (!node.children.length) {
            node.layer = 0;
         } else {
            // Si le niveau a été défini sur un partenaire :
            node.layer = 1;
            for (let p = 0; p < node.partners.length; p++) {
               if (node.partners[p].layer !== undefined) {
                  node.layer = node.partners[p].layer;
                  break;
               }
            }
   
            for (let c = 0; c < node.children.length; c++) {
               node.layer = max(node.layer, node.children[c].layer + 1);
            }
         }
      }
      /**
      * Avec l'algo suivant il est possible d'avoir un enfant au niveau 0
      *  tandis que son parent est au niveau 2 ou plus pour être au niveau
      *  de son partenaire.
      */
      let changed = true;
   
      while (changed) {
         changed = false;
   
         for (let id = 0; id < nodes.length; id++) {
            let node = nodes[id];
            let parents_layer = undefined;
            for (let p = 0; p < node.parents.length; p++) {
               parents_layer = min(parents_layer, node.parents[p].layer);
            }
   
            if (parents_layer !== undefined && parents_layer - 1 > node.layer) {
               node.layer = parents_layer - 1;
               changed = true;
            }
         }
      }
   }
   
   /**
    * Normalise les niveaux
    */
   function normalize_layers() {
      let max_layer = undefined;
   
      for (let id in graph) {
         let node = graph[id];
         max_layer = max(max_layer, node.layer);
      }
      for (let id in graph) {
         let node = graph[id];
         node.layer = max_layer - node.layer;
      }
   }
   
   /**
    * Pour chaque niveau, on liste les personnes présentes à ce niveau
    * et on leur attribue une position de gauche à droite dans ce niveau.
    */
   function per_layer() {
      let layers = [];
      for (let id in graph) {
         let node = graph[id];
         if (!layers[node.layer]) {
            layers[node.layer] = [];
         }
         layers[node.layer].push(node);
         node.pos_in_layer = layers[node.layer].length;
      }
      return layers;
   }
   
   /**
    * On trie les noeuds pour chaque niveau
    */ 
   
   function sort_nodes_in_layers() {
      let layers = per_layer();
      
      for (let l = 1; l < layers.length; l++) {
         for (let c = 0; c < layers[l - 1].length; c++) {
            let child_node = layers[l - 1][c];
            let total = 0;
            let count = 1;
   
            for (let p = 0; p < child_node.parents.length; p++) {
               let parent_node = child_node.parents[p];
               total += parent_node.pos_in_layer;
               count ++;
            }
            for (let p = 0; p < child_node.children.length; p++) {
               let children = child_node.children[p];
               total += children.pos_in_layer;
               count ++;
            }
            child_node.weight_in_layer = total / count;
         }
         
         // on trie les noeuds du niveau
         layers[l - 1].sort(
            function(c1, c2) { return c1.weight_in_layer < c2.weight_in_layer});
            
         for (let c = 0; c < layers[l - 1].length; c++) {
            let child_node = layers[l - 1][c];
            child_node.pos_in_layer = c;
         }
      }
   }
   
   
   /**
    * Assigne les bonnes coordonnées à chaque noeud de personne
    */
   
   function assign_coordinates() {
      for (let id in graph) {
         let node = graph[id];
         tree[node.index].x = (node_width + horiz_margin) * node.pos_in_layer;
         tree[node.index].y = (node_height + vert_margin) * node.layer;

      }
   
      
      let layers = per_layer();
      for (let iteration = 0 ; iteration < 1; iteration++) {
   
         // on calcule en fonction des parents
         for (let l = 1; l < layers.length; l++) {
            let min_x = 0;
   
            for (let c = 0; c < layers[l].length; c++) {
               let child_node = layers[l][c];
               let total = 0;
               let count = 0;
   
               for (let p = 0; p < child_node.parents.length; p++) {
                  let parent_node = child_node.parents[p];
                  total += tree[parent_node.index].x;
                  count ++;
               }
   
               if (count != 0) {
                  tree[child_node.index].x = max(min_x, total / count);
               } else {
                  tree[child_node.index].x = max(min_x, tree[child_node.index].x)
               }
               min_x = tree[child_node.index].x + node_width + horiz_margin;
            }
         }
   
         // on calcule en fonction des enfants
         for (let l = layers.length - 2; l >= 0; l--) {
            let min_x = 0;
   
            for (let c = 0; c < layers[l].length; c++) {
               let parent_node = layers[l][c];
               let total = 0;
               let count = 0;
   
               for (let p = 0; p < parent_node.children.length; p++) {
                  let child_node = parent_node.children[p];
                  total += tree[child_node.index].x;
                  count ++;
               }
   
               if (count != 0) {
                  tree[parent_node.index].x = max(min_x, total / count);
               } else {
                  tree[parent_node.index].x = max(min_x, tree[parent_node.index].x);
               }
               min_x = tree[parent_node.index].x + node_width + horiz_margin;
            }
         }
      }
   
      /**
       * Normalise les coordonnées, pour que l'enfant le plus à gauche soit à x=0
       * Ensuite décale les personnes de pour faire un effet d'arbre généalogique.
      */
   
      let min_x = undefined;
      for (let l = 0; l < layers.length; l++) {
         min_x = min(min_x, tree[layers[l][0].index].x);
      }
      for (let id in graph) {
         tree[graph[id].index].x -= min_x;
   
      }
      let x = 0;
      for(let i in layers){
         for(let j in layers[i]){
            tree[layers[i][j].index].x += x*node_width;
         }
         x++;
      }
      let min_xx = undefined;
      for (let l = 0; l < layers.length; l++) {
         min_xx = min(min_xx, tree[layers[l][0].index].x);
      }
      for (let id in graph) {
         tree[graph[id].index].x -= min_xx;
      }
   }
   
   /**
    * Va à la ligne pour tous les noms des personnes si le nom ou prénom est supérieur à la taille "width".
    */
   function wrap(text, width) {
     text.each(function() {
       let text = d3.select(this),
         words = text.text().split(/\s+/).reverse(),
         word,
         line = [],
         lineNumber = 0,
         lineHeight = 1.1, // ems
         x = text.attr("x"),
         y = text.attr("y"),
         dy = 1.1,
         tspan = text.text(null).append("tspan").attr("x", x).attr("y", y).attr("dy", dy + "em");
         
      words = words.reverse();
       for (word of words) {
         line.push(word);
         tspan.text(line.join(" "));
         if (tspan.node().getComputedTextLength() > width) {
           line.pop();
           tspan.text(line.join(" "));
           line = [word];
           tspan = text.append("tspan").attr("x", x).attr("y", y).attr("dy", ++lineNumber * lineHeight + dy + "em").text(word);
         }
       }
       words = [];
     });
   }
   
   function estDirigeant(preNom)
   {
      let estDirig = false;
      window.souverainete.forEach(function(lien)
      {
         let souverain = lien.idSouverain;
         window.listePersonnes.forEach(function(personne)
         {
            if(personne.id == souverain)
            {
               if(preNom === personne.prenom + " " + personne.nom)
                  estDirig = true;
            }
         });
      });
      return estDirig;
   }
   /**
    * retourne un string du pays du dirigeant au nom donné en paramètre
    */
   function paysDirigeant(preNom)
   {
      let pays = null;
      window.souverainete.forEach(function(lien)
      {
         let souverain = lien.idSouverain;
         window.listePersonnes.forEach(function(personne)
         {
            if(personne.id == souverain)
            {
               if(preNom === personne.prenom + " " + personne.nom)
                  pays = lien.idPays;
            }
         });
      });
      return pays;
   }

   /**
    * retourne si la personne au nom donné en paramètre est dirigeante du pays donné
    */
   function isCurrentLeader(preNom, pays)
   {
      let p = getPersonne(document.querySelector('#slider').value, pays);
      if(p && preNom === p.prenom + " " + p.nom) return "Actuel";
      else return "";
   }

   /**
    * récupère seulement les personnes de la famille de la personne dont le nom est donné en paramètre
    */
   function getFamily(nomPersonne){
      let family = [];
      let seen = [];

      const dirigeant = getPersByName(nomPersonne);
      family.push(dirigeant);
      seen[dirigeant.id] = true;

      for(let i of dirigeant.parents)
      {   
         let parent = getPersById(i);
         if(!seen[i]){
            family.push(parent);
            seen[i] = true;
            for(let j of parent.parents){                      // grands-parents dirigeant
               let grandparent = getPersById(j);
               if(!seen[j]){
                  family.push(grandparent);
                  seen[j] = true;
                  for(let u of grandparent.children){          // oncles et tantes du dirigeant
                     let uncle = getPersById(u);
                     if(!seen[u]){
                        family.push(uncle);
                        seen[u] = true;
                        for(let jU of uncle.children){         // cousins du dirigeant
                           let nephew = getPersById(jU);
                           if(!seen[jU]){ family.push(nephew); seen[jU] = true;}
                        }
                        for(let jP of uncle.partners){        // femmes et maris des oncles et tantes
                           let partner = getPersById(jP);
                           if(!seen[jP]){ family.push(partner); seen[jP] = true;}
                        }
                     }
                  }

               }
            }
            for(let broId of parent.children){            // freres soeurs du dirigeant
               let bro = getPersById(broId);
               if(!seen[broId]){
                  family.push(bro);
                  seen[broId] = true;
                  for(let nephewId of bro.children){         // neveux et nièces du dirigeant
                     let nephew = getPersById(nephewId);
                     if(!seen[nephewId]){ family.push(nephew); seen[nephewId] = true;}
                  }
                  for(let j of bro.partners){         // mari ou femme des freres et soeur du dirigeant
                     let partner = getPersById(j);
                     if(!seen[j]){  family.push(partner); seen[j] = true;}
                  }
               }
            }
         }
      }
      for(let j of dirigeant.children){                  //enfants dirigeant
         let enfantDirigeant = getPersById(j);
         if(!seen[j]){
            family.push(enfantDirigeant);
            seen[j] = true;
            for(let gchId of enfantDirigeant.children){  //petits enfants dirigeant
               let gch = getPersById(gchId);
               if(!seen[gchId]){
                  family.push(gch);
                  seen[gchId] = true;

                  for(let spId of gch.partners){         // époux des petits enfants du dirigeant
                     let sp = getPersById(spId);
                     if(!seen[gchId]){
                        family.push(sp);
                        seen[spId] = true;
                     }
                  }
               }
            }
         }
         for(let chSpId of enfantDirigeant.partners){    // gendre et bru du dirigeant
            let chSp = getPersById(chSpId);
            if(!seen[chSpId]){
               family.push(chSp);
               seen[chSpId] = true;
            }
         }
      }
      for(let j of dirigeant.partners){         // mari ou femme du dirigeant
         let partner = getPersById(j);
         if(!seen[j]){
            family.push(partner);
            seen[j] = true;
         }
      }

      // on enlève les liens vers des personnes extérieures au graphe choisi précédemment
      let identifiants = [];
      for(let p of family){
         identifiants.push(p.id);
      }
      for(let p of family){
         for(let i in p.children){
            if(identifiants.indexOf(p.children[i]) == -1){
               p.children.splice(i, 1);
            }
         }
         for(let i in p.partners){
            if(identifiants.indexOf(p.partners[i]) == -1){
               p.partners.splice(i, 1);
            }
         }
         for(let i in p.parents){
            if(identifiants.indexOf(p.parents[i]) == -1){
               p.parents.splice(i, 1);
            }
         }
      }
      return family;
   }

   function getMultipleFamily(leaders){
      if(leaders.length == 1){
         return getFamily(leaders[0]);
      }
      else{
         let bigFamily = [];
         for(let leader of leaders){
            const family = getFamily(leader);
            for(let p of family){
               bigFamily.push(p)
            }
         }
         
         // on enlève les doublons
         for(let i = 0; i < bigFamily.length; i++){
            for(let j = 0; j < bigFamily.length; j++){
               if(bigFamily[i] && bigFamily[j] && bigFamily[i] !== bigFamily[j] && bigFamily[i].id === bigFamily[j].id){
                  let set = new Set(bigFamily[i].children.concat(bigFamily[j].children));
                  bigFamily[i].children = Array.from(set);
                  set = new Set(bigFamily[i].parents.concat(bigFamily[j].parents));
                  bigFamily[i].parents = Array.from(set);
                  set = new Set(bigFamily[i].partners.concat(bigFamily[j].partners));
                  bigFamily[i].partners = Array.from(set);
                  bigFamily.splice(j,1);
               }
            }
         }
         return bigFamily;
      }
   }
   
   /*
   function getAllFamily(person){
      person = getPersByName(person);
      let listFamily = [];
      let listIdFamily = [];
      function recursFamily(p){ // fonction récursive qui permet à la méthode parente de récupérer les ancêtres
         listFamily.push(p);
         listIdFamily.push(p.id)
         if(p.partners){
            for(let i of p.partners){
               if(!listIdFamily.includes(i)){
                  const partner = getPersById(i);
                  recursFamily(partner);
               }
            }
         }
         if(p.parents){
            for(let i of p.parents){
               if(!listIdFamily.includes(i)){
                  const parent = getPersById(i);
                  recursFamily(parent);
               }
            }
         }
         if(p.children){
            for(let i of p.children){
               if(!listIdFamily.includes(i)){
                  const child = getPersById(i);
                  recursFamily(child);
               }
            }
         }
      };
      recursFamily(person); // exécution récursive
      return listFamily;
   }*/



   /*
      méthode pour savoir si une personne est de la même famille
   let degree;
   let relations;
   function isInFamily(person1, person2, list){
      if(person1.name === person2.name){
         return true;
      }
      let trouve = false;
      if(list.indexOf(person1.id) < 0){
         list.push(person1.id)
         if(person1.hasOwnProperty('parents')){
            for(let idParent of person1.parents){
               let parent = getPersById(idParent);
               if(list.indexOf(parent.id) < 0 && (parent.hasOwnProperty('parents') || parent.hasOwnProperty('children'))){
                  if(isInFamily(parent, person2, list)){
                     relations.push("parent's");
                     trouve = true;
                     return trouve;
                  }
               }
            }
         }
         
         if(person1.hasOwnProperty('children')){
            for(let idChildren of person1.children){
               let child = getPersById(idChildren);
               if(list.indexOf(child.id) < 0 && (child.hasOwnProperty('children') || child.hasOwnProperty('parents'))){
                  if(isInFamily(child, person2, list)){
                     relations.push("child's");
                     trouve = true;
                     return trouve;
                  }
               }
            }
         }
         if(person1.hasOwnProperty('partners')){
            for(let idPartner of person1.partners){
               let partner = getPersById(idPartner);
               if(list.indexOf(partner.id) < 0 && (partner.hasOwnProperty('parents') || partner.hasOwnProperty('children'))){
                  if(isInFamily(partner, person2, list)){
                     relations.push("partner's");
                     trouve = true;
                     return trouve;
                  }
               }

            }
         }
         
      }
      return trouve;

   }*/

   /**
    * Récupère une personne par son nom
    */
   function getPersByName(nom){
      for(let i of window.jsonGlobal){
         if(i.name === nom){
            return JSON.parse(JSON.stringify(i)); // copie pour éviter de modifier l'objet
         }
      }
   }

   /**
    * Récupère une personne par son id
    */
   function getPersById(id){
      for(let i of window.jsonGlobal){
         if(i.id === id){
            return JSON.parse(JSON.stringify(i));  // copie pour éviter de modifier l'objet
         }
      }
   }

   /*--------------------------------------------------------------------------*/
   /*             1ère méthode pour trouver le lien de parenté                    
   * On utilise Dijkstra pour trouver le lien le plus court en une personne
   * et une autre. On regarde ensuite pour chaque personne qui ont été parcourues
   * durant ce plus court chemin, quels étaient leurs liens. On factorise puis cela
   *  nous donne un lien de parenté entre deux personnes.                      */
   /*--------------------------------------------------------------------------*/


   /**
    * Retourne une liste qui remplace un trajet d'une personne à l'autre
    * par une liste qui associe ce trajet à une relation.
    */
   function listRelations(traveled){
      let list = [];
      for(let i = 0; i < traveled.length-1; i++){
         const pers = traveled[i];
         for(let idParent of pers.parents){
            const parent = getPersById(idParent);
            if(parent.name === traveled[i+1].name){
               list.push("parent"); // relation parent
            }
         }
         for(let idChild of pers.children){
            const child = getPersById(idChild);
            if(child.name === traveled[i+1].name){
                  list.push("enfant"); // relation enfant
            }
         }
         for(let idPartner of pers.partners){
            const partner = getPersById(idPartner);
            if(partner.name === traveled[i+1].name){
               list.push("partenaire"); // relation partenaire
            }
         }
      }
      return list;
   }

   /**
    * Retourne la relation entre la personne p1 et la personne p2 sous forme de chaîne de caractères
    * Concrètement, on factorise les relations.
    */
   function litteralRelations(relations, p1, p2){
      relations = relations.replace(" parent parent parent "," arrière-grand-parent ");
      relations = relations.replace(" parent parent "," grand-parent ");
      relations = relations.replace(" enfant enfant enfant "," arrière-petit-enfant ");

      relations = relations.replace(" enfant enfant "," petit-enfant ");
      relations = relations.replace(" parent enfant "," frère-ou-soeur ");
      relations = relations.replace(" grand-parent enfant "," oncle-ou-tante ");
      relations = relations.replace(" grand-parent petit-enfant ", " cousin ")
      relations = relations.replace(" parent petit-enfant ", " neveu-ou-nièce ")
      relations = relations.replace(" cousin parent ", " oncle-ou-tante ")
      relations = relations.replace(" enfant partenaire ", " beau-fils ")
      relations = relations.replace(" partenaire parent ", " beau-parent ")

      relations = relations.split(' ');
      relations.shift();
      relations.pop();
      relations.reverse();
      relations = p2.name + ' est le ' +relations.join(' du ') + ' de ' + p1.name;

      const voyelles = ['a','e','i','o','u'];
      voyelles.forEach(v=>{
         relations = relations.replace(" le "+v, " l'"+v)
         relations = relations.replace(" du "+v, " de l'"+v)

      })
      return relations;
   }



   /*--------------------------------------------------------------------------*/
   /*          2ème méthode pour trouver le lien de parenté                    */
   /*--------------------------------------------------------------------------*/
   /**
    * Fonction permettant de récupérer les ancêtres d'une personne (en prenant en compte sa belle famille
    * On attribue un niveau à chaque personne pour savoir sa relation avec la personne
    * level 0 : la personne et ses partenaires
    * level 1 : les parents de la personne
    * level 2 : les parents de parents (grands-parents) de la personne
    * level n : les parents (* n) de la personne
    */
   function getAncestors(person){
      let listAncestors = [];
      let listIdAncestors = [];
      function recursAncestor(p){ // fonction récursive qui permet à la méthode parente de récupérer les ancêtres
         listAncestors.push(p);
         listIdAncestors.push(p.id)
         if(p.partners){
            for(let i of p.partners){
               if(!listIdAncestors.includes(i)){
                  const partner = getPersById(i);
                  if(p.level == 0){
                     partner.level = 0.3; // on choisit arbitrairement 0.3 pour désigner que l'on passe dans la belle-famille
                  }
                  else{
                     partner.level = p.level;
                  }
                  recursAncestor(partner);
               }
            }
         }
         if(p.parents){
            for(let i of p.parents){
               if(!listIdAncestors.includes(i)){
                  const parent = getPersById(i);
                  parent.level = p.level + 1 ;
                  recursAncestor(parent);
               }
            }
         }
      };
      person.level = 0; // on initialise à zéro la personne dont on recherche ses ancêtres
      recursAncestor(person); // exécution récursive
      return listAncestors;
   }

   /**
    * Retourne le plus petit ancêtre commun entre deux personnes ainsi que la hauteur de
    * parenté depuis ces deux personnes jusqu'à l'ancêtre commun.
    */
   function getLowestCommonAncestor(person1, person2){
      const listAncestorsP1 = getAncestors(person1);
      const listAncestorsP2 = getAncestors(person2);
      
      let lowestCommonAncestor = -1; // si non trouvé -1
      let lcaLevelP1 = -1; // si non trouvé -1
      let lcaLevelP2 = -1; // si non trouvé -1

      listAncestorsP1.forEach(person1 => {
         listAncestorsP2.forEach(person2 => {
            if(person1.id == person2.id){
               lowestCommonAncestor = person1;
               lcaLevelP1 = person1.level;
               lcaLevelP2 = person2.level;
            }
         });
      });

      return [lowestCommonAncestor, lcaLevelP1, lcaLevelP2];
   }

   function getRelationshipBetween(person1, person2){
      let [lowestCommonAncestor, lcaLevelP1, lcaLevelP2] = getLowestCommonAncestor(person1,person2);
      if(lowestCommonAncestor == -1){  // pas d'ancêtre commun => pas de la même famille selon cette méthode
         return ["no relationship", false];
      }
      let inlaw = false;
      if((lcaLevelP1%1).toFixed(2) == 0.3 || (lcaLevelP2%1).toFixed(2) == 0.3){
         inlaw = true;
         if((lcaLevelP1%1).toFixed(2) == 0.3){
            lcaLevelP1 = parseInt(lcaLevelP1 - 0.3)
         }
         if((lcaLevelP2%1).toFixed(2) == 0.3){
            lcaLevelP2 = parseInt(lcaLevelP2 - 0.3)
         }
      }
      let relationship = "no relationship";
      switch(lcaLevelP1){
         case 0: // ancêtre commun = soi-même
            switch(lcaLevelP2){
               case 0: // partenaire
                  relationship = "époux/épouse";
                  break;
               case 1: // parent
                  relationship = "père/mère";
                  break;
               case 2: // grand-parent
                  relationship = "grand-père/grand-mère";
                  break;
               case 3: // arrière-grand-parent
                  relationship = "arrière-grand-père/arrière-grand-mère";
                  break;
            }
            break;
         case 1: // plus petit ancêtre commun de la 1ère personne : parent
            switch(lcaLevelP2){
               case 1: // plus petit ancêtre commun de la 2nde personne : parent
                  relationship = "frère/soeur";
                  break;
               case 2: // plus petit ancêtre commun de la 2nde personne : grand-parent
                  relationship = "oncle/tante";
                  break;
               case 3: // plus petit ancêtre commun de la 2nde personne : arrière-grand-parent
                  relationship = "grand-oncle/grande-tante";
                  break;
               case 4: // plus petit ancêtre commun de la 2nde personne : arrière-arrière-grand-parent
                  relationship = "arrière-grand-oncle/arrière-grande-tante";
                  break;
            }
            break;
         case 2: // plus petit ancêtre commun de la 1ère personne : grand-parent
            switch(lcaLevelP2){
               case 1: // plus petit ancêtre commun de la 2nde personne : parent
                  relationship = "neveu/nièce";
                  break;
               case 2: // plus petit ancêtre commun de la 2nde personne : grand-parent
                  relationship = "cousin germain/cousine germaine";
                  break;
               case 3: // plus petit ancêtre commun de la 2nde personne : arrière-grand-parent
                  relationship = "cousin germain éloigné au 1er degré/cousine germaine éloignée au 1er degré";
                  break;
               case 4: // plus petit ancêtre commun de la 2nde personne : arrière-arrière-grand-parent
                  relationship = "cousin germain éloigné au 2ème degré/cousine germaine éloignée au 2ème degré";
                  break;
            }
            break;
         case 3: // plus petit ancêtre commun de la 1ère personne : arrière-grand-parent
            switch(lcaLevelP2){
               case 1: // plus petit ancêtre commun de la 2nde personne : parent
                  relationship = "petit-neveu/petite-nièce";
                  break;
               case 2: // plus petit ancêtre commun de la 2nde personne : grand-parent
                  relationship = "cousin germain éloigné au 1er degré/cousine germaine éloignée au 1er degré";
                  break;
               case 3: // plus petit ancêtre commun de la 2nde personne : arrière-grand-parent
                  relationship = "cousin issu de germain/cousine issue de germain";
                  break;
               case 4: // plus petit ancêtre commun de la 2nde personne : arrière-arrière-grand-parent
                  relationship = "cousin issu de germain éloigné au 1er degré/cousine issue de germain éloignée au 1er degré";
                  break;
            }
            break;
         case 4: // plus petit ancêtre commun de la 1ère personne : arrière-arrière-grand-parent
            switch(lcaLevelP2){
               case 1: // plus petit ancêtre commun de la 2nde personne : parent
                  relationship = "arrière-petit-neveu/arrière-petite-nièce";
                  break;
               case 2: // plus petit ancêtre commun de la 2nde personne : grand-parent
                  relationship = "cousin germain éloigné au 2ème degré/cousine germaine éloignée au 2ème degré";
                  break;
               case 3: // plus petit ancêtre commun de la 2nde personne : arrière-grand-parent
                  relationship = "cousin issu de germain éloigné au 1er degré/cousine issue de germain éloignée au 1er degré";
                  break;
               case 4: // plus petit ancêtre commun de la 2nde personne : arrière-arrière-grand-parent
                  relationship = "petit-cousin/petite-cousine";
                  break;
            }
            break;
      }
      if(inlaw && relationship === "époux/épouse"){
         inlaw = false;
      }
      return [relationship, inlaw];
   }


   let selectedLeaders;
   function setSelected(leaders){
      leaders.forEach(l => {
         selectedLeaders.push(getPersByName(l))
      });
   }
   function isSelected(name){
      for(let leader of selectedLeaders){
         if(name === leader.name){
            return true;
         }
      }
      return false;
   }

   /**
    * construction du graphe pour le dirigeant donné en paramètre 
    */
   function graph_main(leaders) {
      graph = {};
      tree = [];
      selectedLeaders = [];
      if(typeof(leaders) === "object"){ // s'il y a plus d'un leader sélectionné = tableau de noms de dirigeants
         tree = getMultipleFamily(leaders);

         setSelected(leaders)
         /* Récupère les relations entre dirigeants sélectionnés */
         let seen = {}; // pour éviter les doublons
         leaders.forEach(l => {
            const p1 = getPersByName(l);