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].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;
      }
   }

   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;

   }



   /**
    * getter de personne par nom
    */
   function getPersByName(nom){
      for(let i of window.jsonGlobal){
         if(i.name === nom){
            return JSON.parse(JSON.stringify(i));
         }
      }
   }
   /**
    * getter de personne par id
    */
   function getPersById(id){
      for(let i of window.jsonGlobal){
         if(i.id === id){
            return JSON.parse(JSON.stringify(i));
         }
      }
   }

   function listRelations(traveled){
      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){
               console.log("parent");
            }
         }
         for(let idChild of pers.children){
            const child = getPersById(idChild);
            if(child.name === traveled[i+1].name){
               console.log("child");
            }
         }
         for(let idPartner of pers.partners){
            const partner = getPersById(idPartner);
            if(partner.name === traveled[i+1].name){
               console.log("partner");
            }
         }
      }
   }


   /**
    * construction du graphe pour le dirigeant donné en paramètre 
    */
   function graph_main(leaders) {
      graph = {};
      tree = [];
      degree = 0;
      relations = [];
      roads = {}
      if(typeof(leaders) === "object"){
         tree = getMultipleFamily(leaders);
         console.log(isInFamily(getPersByName(leaders[0]),getPersByName(leaders[1]),new Array()));
         relations = relations.reverse().join(" ");
        /* relations = relations.replace("parent's parent's parent's","great-grandparent's");
         relations = relations.replace("parent's parent's","grandparent's");
         relations = relations.replace("child's child's child's","great-grandchild's");
         relations = relations.replace("child's child's","grandchild's");
         relations = relations.replace("parent's child's","sibling's");
         relations = relations.replace("grandparent's grandchild's", "cousin's")
         relations = relations.replace("cousin's parent's", "uncles or aunt 's")*/
         
         const p1 = getPersByName(leaders[0]);
         const p2 = getPersByName(leaders[1]);
         const traveled = Dijkstra(roads,p1.id + "", p2.id + "");
         listRelations(traveled)
        
      }
      else if(typeof(leaders) === "string"){
         tree = getFamily(leaders);
      }
      
      build_graph();
      rank();
      normalize_layers();
      sort_nodes_in_layers();
      assign_coordinates();
   
      d3.select('#canvas').select('svg')
      .remove()
      let svg = d3.select('#canvas')
        .append('svg')
        .attr('preserveAspectRatio', 'xMinYMin meet')
        .attr('viewBox', '0 0 1300 500')
        .append('g');
   
      let links = [];
      for (let id in graph) {
         let node = graph[id];
         let prefixM = 'M' + (tree[node.index].x + node_width / 2) +
                        ' ' + (tree[node.index].y + node_height / 2);
   
         let prefixCh = 'M' + (tree[node.index].x + node_width / 2) +
                        ' ' + (tree[node.index].y + node_height);
         for (let c = 0; c < node.partners.length; c++) {
            let partner = tree[node.partners[c].index];
            let path = prefixM + 'T' + (partner.x + node_width / 2) +
                                ' ' + (partner.y + node_height / 2);
            links.push({path: path, class:'partner'});
         }
         for (let c = 0; c < node.children.length; c++) {
            let child = tree[node.children[c].index];
            let path = prefixCh + 'T' + (child.x + node_width / 2) +
                                ' ' + (child.y + 0);
            links.push({path: path, class:'child'});
         }
      }
      // Dessine les liens entre personnes
   
      svg.selectAll('path')
         .data(links)
         .enter()
            .append('path')
            .attr('class', function(d) { return d.class})
            .attr('d', function(d) { return d.path});
   
      // Dessine les personnes
   
      let enter_g = svg.selectAll('g.person')
         .data(tree)
         .enter()
            .append('g')
            .attr('class', function(d){
               if(estDirigeant(d.name)){
                  return "leader";
               }
               return d.sex})
            .attr('transform', function(d) {return 'translate(' + d.x + ',' + d.y + ')'});
   
      enter_g
         .append('rect')
         .attr('width', node_width)
         .attr('height', node_height)
         .attr('rx', '0px')
         .attr('ry', '0px')
         .on("click", function(d) { window.open('https://fr.wikipedia.org/wiki/' + d.name); });
      
      enter_g
         .append('text')
         .attr('x', 2)
         .attr('y', 2)
         .text(function(d) {
            if(estDirigeant(d.name)){
               const pays = paysDirigeant(d.name);
               const actuelDirigeant = isCurrentLeader(d.name, pays);
               return d.name + "\n"+ actuelDirigeant +"("+pays +")";
            }
            
            return d.name;})
         .on("click", function(d) { window.open('https://fr.wikipedia.org/wiki/' + d.name); })
         .call(wrap, node_width);
      
      enter_g
         .each(function() {
            let w = this.getBBox().width,
            h = this.getBBox().height;
            d3.select(this).select('rect').attr('width', w).attr('height', h);
         });

         
      const taille = d3.select('#canvas').select('svg').select('g').node().getBBox();

      d3.select('#canvas').select('svg').attr('viewBox', '0 0 '+(taille.width)+' '+(taille.height));
      document.querySelector("#canvas > svg").style.width = taille.width;
   }