javascript - example - js diagram

¿Representa un gráfico familiar creado dinámicamente sin superposición utilizando una primera búsqueda de profundidad?

Question

Quiero generar esto:

Con esta estructura de datos (los identificadores son aleatorios, por cierto, no secuenciales):

var tree = [
    { "id": 1, "name": "Me", "dob": "1988", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [5,6] },
    { "id": 2, "name": "Mistress 1", "dob": "1987", "children": [4], "partners" : [1], level: 0, "parents": [] },
    { "id": 3, "name": "Wife 1", "dob": "1988", "children": [5], "partners" : [1], level: 0, "parents": [] },
    { "id": 4, "name": "son 1", "dob": "", "children": [], "partners" : [], level: -1, "parents": [1,2] },
    { "id": 5, "name": "daughter 1", "dob": "", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
    { "id": 6, "name": "daughter 1s boyfriend", "dob": "", "children": [7], "partners" : [5], level: -1, "parents": [] },
    { "id": 7, "name": "son (bottom most)", "dob": "", "children": [], "partners" : [], level: -2, "parents": [5,6] },
    { "id": 8, "name": "jeff", "dob": "", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
    { "id": 9, "name": "maggie", "dob": "", "children": [1], "partners" : [8], level: 1, "parents": [] },
    { "id": 10, "name": "bob", "dob": "", "children": [8], "partners" : [11], level: 2, "parents": [12] },
    { "id": 11, "name": "mary", "dob": "", "children": [], "partners" : [10], level: 2, "parents": [] },
    { "id": 12, "name": "john", "dob": "", "children": [10], "partners" : [], level: 3, "parents": [] },
    { "id": 13, "name": "robert", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [] },
    { "id": 14, "name": "jessie", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [15,16] },
    { "id": 15, "name": "raymond", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
    { "id": 16, "name": "betty", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
];

Para dar una descripción de la estructura de datos, se define el nodo raíz / inicial (me). Cualquier pareja (esposa, ex) está en el mismo nivel. Cualquier cosa debajo se convierte en nivel -1, -2. Todo lo anterior es de nivel 1, 2, etc. Hay propiedades para padres, hermanos, hijos y parejas que definen los identificadores para ese campo en particular.

En mi question anterior, eh9 described cómo resolvería esto. Estoy intentando hacer esto, pero como descubrí, no es una tarea fácil.

Mi primer intento es renderizar esto por niveles de arriba hacia abajo. En este intento más simplista, básicamente anilo a todas las personas por niveles y lo renderizo de arriba hacia abajo.

Mi segundo intento es renderizarlo con uno de los nodos ancestros usando una búsqueda de profundidad en primer lugar.

Mi pregunta principal es : ¿cómo puedo aplicar esa respuesta a lo que tengo actualmente? En mi segundo intento estoy tratando de hacer un primer recorrido profundo, pero ¿cómo puedo empezar a calcular las distancias necesarias para compensar las cuadrículas para que sea coherente con cómo quiero generar esto?

Además, ¿mi comprensión / implementación del ideal de profundidad es lo primero, o puedo atravesar esto de manera diferente?

Los nodos obviamente se superponen en mi segundo ejemplo, ya que no tengo código de cálculo de compensación / distancia, pero estoy perdido en cuanto a averiguar cómo puedo comenzar eso.

Aquí hay una descripción de la función de caminar que hice, donde estoy intentando un primer recorrido de profundidad:

// this is used to map nodes to what they have "traversed". So on the first call of "john", dict would internally store this:
// dict.getItems() = [{ ''12'': [10] }]
// this means john (id=10) has traversed bob (id=10) and the code makes it not traverse if its already been traversed. 
var dict = new Dictionary;

walk( nested[0][''values''][0] ); // this calls walk on the first element in the "highest" level. in this case it''s "john"

function walk( person, fromPersonId, callback ) {

    // if a person hasn''t been defined in the dict map, define them
    if ( dict.get(person.id) == null ) {
        dict.set(person.id, []);


        if ( fromPersonId !== undefined || first ) {

            var div = generateBlock ( person, {
                // this offset code needs to be replaced
                top: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css(''top''), 10 )+50,
                left: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css(''left''), 10 )+50
            });

            //append this to the canvas
            $(canvas).append(div);

            person.element = div;
        }
    }

    // if this is not the first instance, so if we''re calling walk on another node, and if the parent node hasn''t been defined, define it
    if ( fromPersonId !== undefined ) {
        if ( dict.get(fromPersonId) == null ) {
            dict.set(fromPersonId, []);
        }

        // if the "caller" person hasn''t been defined as traversing the current node, define them
        // so on the first call of walk, fromPersonId is null
        // it calls walk on the children and passes fromPersonId which is 12
        // so this defines {12:[10]} since fromPersonId is 12 and person.id would be 10 (bob)
        if ( dict.get(fromPersonId).indexOf(person.id) == -1 )
            dict.get(fromPersonId).push( person.id );
    }

    console.log( person.name );

    // list of properties which house ids of relationships
    var iterable = [''partners'', ''siblings'', ''children'', ''parents''];
    iterable.forEach(function(property) {
        if ( person[property] ) {
            person[property].forEach(function(nodeId) {
                // if this person hasnt been "traversed", walk through them
                if ( dict.get(person.id).indexOf(nodeId) == -1 )
                    walk( getNodeById( nodeId ), person.id, function() {
                        dict.get(person.id).push( nodeId );
                    });
            });
        }
    });


}

}

Requisitos / restricciones:

1. Esto es para un editor y sería similar a familyecho.com. Casi todas las reglas comerciales no definidas se pueden asumir a través de eso.
2. La crianza en familia no es compatible, ya que sería demasiado complejo. No te preocupes por esto
3. Se admiten múltiples socios, por lo que no es tan fácil como un "árbol genealógico" tradicional con solo 2 padres y 1 hijo.
4. Solo hay un nodo "raíz", que es solo el nodo inicial.

Notas : familyecho.com parece "esconder" una rama si hay muchos nodos hoja y hay una colisión. Puede necesitar implementar esto.

Answer 1

A medida que lo muestre, los datos de su árbol no le permitirán dibujar el diagrama. De hecho, falta información allí:

• tree debería ser realmente un objeto (diccionario) mapeando el id a los datos de la persona. De lo contrario, es costoso pasar de la identificación, tal como se da en los children por ejemplo, a los datos del niño.
• hay información duplicada ya que los niños están asociados con ambos padres. En realidad, esto conduce a datos incorrectos en el ejemplo enviado (''daugher1'' es hijo de ''esposa'', pero uno de los padres de ''yo'', y ''Mary'' es presumiblemente madre de ''jeff''; jessie es socia de Robert; también lo son raymond y betty)

En mi intento ( https://jsfiddle.net/61q2ym7q/ ), por lo tanto, estoy convirtiendo su árbol en un gráfico, y luego haciendo varias etapas de cálculo para lograr un diseño.

Esto está inspirado en el algoritmo Sugiyama, pero simplificado, ya que ese algoritmo es muy difícil de implementar. Aún así, las diversas etapas son:

• organizar los nodos en capas, utilizando la búsqueda de profundidad en primer lugar. Hacemos esto en dos pasos asegurándonos de que los padres estén siempre en una capa por encima de su padre, y luego tratando de acortar los enlaces cuando hay más de una capa entre el niño y el padre. Esta es la parte donde no estoy usando el algoritmo Sugiyama exacto, que utiliza una noción compleja de puntos de corte.

• luego clasifique los nodos en cada capa para minimizar el cruce de los bordes. Yo uso el método baricentro para esto

• finalmente, mientras conserva el orden anterior, asigne una coordenada x específica para cada nodo, nuevamente usando el método baricentro

There are lots of things that can be improved in this code (efficiency, by merging some of the loops for instance) and also in the final layout. But I tried to keep it simpler to make it easier to follow...

Answer 2

A pesar de que se ha publicado (y aceptado) una respuesta, pensé que no había nada malo en publicar lo que trabajé sobre este problema anoche.

Abordé este problema más desde un punto de vista novato en lugar de trabajar con los algoritmos existentes de cruce gráfico / árbol.

Mi primer intento es renderizar esto por niveles de arriba hacia abajo. En este intento más simplista, básicamente anilo a todas las personas por niveles y lo renderizo de arriba hacia abajo.

Este fue exactamente mi primer intento también. Puede atravesar el árbol de arriba hacia abajo, o de abajo hacia arriba o comenzando desde la raíz. Como ha sido inspirado por un sitio web en particular, comenzar desde la raíz parece ser una opción lógica. Sin embargo, encontré que el enfoque ascendente era más simple y más fácil de entender.

Aquí hay un intento crudo:

Trazando los datos:

1. Comenzamos desde la capa inferior y trabajamos hacia arriba. Como mencionamos en la pregunta que está tratando de resolver a través de un editor, podemos almacenar todas las propiedades relacionadas en la matriz de objetos a medida que construimos el árbol.

Cacheamos los niveles y usamos eso para caminar por el árbol:

// For all level starting from lowest one
levels.forEach(function(level) {
    // Get all persons from this level
    var startAt = data.filter(function(person) {
        return person.level == level;
    });
    startAt.forEach(function(start) {
        var person = getPerson(start.id);
        // Plot each person in this level
        plotNode(person, ''self'');
        // Plot partners
        plotPartners(person);
        // And plot the parents of this person walking up
        plotParents(person);
    });
});

Donde, getPerson obtiene el objeto de los datos en función de su id .

2. Mientras caminamos, trazamos el nodo en sí mismo, sus padres (recursivamente) y sus socios. Trazar parejas no es realmente necesario, pero lo hice aquí solo para que el trazado de los conectores sea fácil. Si un nodo ya ha sido trazado, simplemente salteamos esa parte.

Así es como trazamos a los socios:

/* Plot partners for the current person */
function plotPartners(start) {
    if (! start) { return; }
    start.partners.forEach(function(partnerId) {
        var partner = getPerson(partnerId);
        // Plot node
        plotNode(partner, ''partners'', start);
        // Plot partner connector
        plotConnector(start, partner, ''partners'');
    });
}

Y los padres recursivamente:

/* Plot parents walking up the tree */
function plotParents(start) {
    if (! start) { return; }
    start.parents.reduce(function(previousId, currentId) {
        var previousParent = getPerson(previousId), 
            currentParent = getPerson(currentId);
        // Plot node
        plotNode(currentParent, ''parents'', start, start.parents.length);
        // Plot partner connector if multiple parents
        if (previousParent) { plotConnector(previousParent, currentParent, ''partners''); }
        // Plot parent connector
        plotConnector(start, currentParent, ''parents'');
        // Recurse and plot parent by walking up the tree
        plotParents(currentParent);
        return currentId;
    }, 0);
}

Donde usamos reduce para simplificar el trazado de un conector entre dos padres como socios.

3. Así es como trazamos un nodo en sí mismo:

Donde, reutilizamos las coordenadas para cada nivel único a través de la función de utilidad findLevel . Mantenemos un mapa de niveles y lo controlamos para llegar a la posición top . El descanso se determina sobre la base de las relaciones.

/* Plot a single node */
function plotNode() {
    var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3], 
        node = get(person.id), relativeNode, element = {}, thisLevel, exists 
    ;
    if (node) { return; }
    node = createNodeElement(person); 
    // Get the current level
    thisLevel = findLevel(person.level);
    if (! thisLevel) { 
        thisLevel = { ''level'': person.level, ''top'': startTop }; 
        levelMap.push(thisLevel); 
    }
    // Depending on relation determine position to plot at relative to current person
    if (relationType == ''self'') {
        node.style.left = startLeft + ''px''; 
        node.style.top = thisLevel.top + ''px'';
    } else {
        relativeNode = get(relative.id);
    }
    if (relationType == ''partners'') {
        // Plot to the right
        node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + ''px'';    
        node.style.top = parseInt(relativeNode.style.top) + ''px''; 
    }
    if (relationType == ''children'') {
        // Plot below
        node.style.left = (parseInt(relativeNode.style.left) - size) + ''px'';    
        node.style.top = (parseInt(relativeNode.style.top) + size + gap) + ''px'';                            
    }
    if (relationType == ''parents'') {
        // Plot above, if single parent plot directly above else plot with an offset to left
        if (numberOfParents == 1) { 
            node.style.left = parseInt(relativeNode.style.left) + ''px''; 
            node.style.top = (parseInt(relativeNode.style.top) - gap - size) + ''px'';                        
        } else {
            node.style.left = (parseInt(relativeNode.style.left) - size) + ''px''; 
            node.style.top = (parseInt(relativeNode.style.top) - gap - size) + ''px'';                                            
        }
    }

    // Avoid collision moving to right
    while (exists = detectCollision(node)) { 
        node.style.left = (exists.left + size + (gap * 2)) + ''px''; 
    }

    // Record level position
    if (thisLevel.top > parseInt(node.style.top)) {
        updateLevel(person.level, ''top'', parseInt(node.style.top));
    }
    element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top); 
    elements.push(element);

    // Add the node to the DOM tree
    tree.appendChild(node); 
}

Aquí para simplificar, utilicé una detección de colisión muy cruda para mover los nodos a la derecha cuando ya existe uno. En una aplicación muy sofisticada, esto movería los nodos dinámicamente hacia la izquierda o hacia la derecha para mantener un equilibrio horizontal.

Por último, agregamos ese nodo al DOM.

4. El resto son todas las funciones auxiliares.

Los más importantes son:

function detectCollision(node) {
    var element = elements.filter(function(elem) { 
        var left = parseInt(node.style.left);
        return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
    });
    return element.pop();
}

Arriba hay una detección simple de colisión teniendo en cuenta la brecha entre los nodos.

Y, para trazar los conectores:

function plotConnector(source, destination, relation) {
    var connector = document.createElement(''div''), orientation, start, stop, 
        x1, y1, x2, y2, length, angle, transform
    ; 
    orientation = (relation == ''partners'') ? ''h'' : ''v'';
    connector.classList.add(''asset'');
    connector.classList.add(''connector'');
    connector.classList.add(orientation);
    start = get(source.id); stop = get(destination.id);
    if (relation == ''partners'') {
        x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
        x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
        length = (x2 - x1) + ''px'';

        connector.style.width = length;
        connector.style.left = x1 + ''px'';
        connector.style.top = y1 + ''px'';
    }
    if (relation == ''parents'') {
        x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
        x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);

        length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        angle  = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
        transform = ''rotate('' + angle + ''deg)''; 

        connector.style.width = length + ''px'';
        connector.style.left = x1 + ''px'';
        connector.style.top = y1 + ''px'';
        connector.style.transform = transform;
    }
    tree.appendChild(connector);
}

Usé dos conectores diferentes, uno horizontal para conectar a los socios, y uno en ángulo para conectar las relaciones entre padres e hijos. Esto resultó ser una parte muy difícil para mí, es decir, trazar conectores horizontales invertidos. Esta es la razón por la cual para mantenerlo simple, simplemente giré un div para que pareciera un conector en ángulo.

5. Una vez que se dibuja / traza todo el árbol, puede haber nodos que se salen de la pantalla debido a posiciones negativas (porque estamos cruzando de abajo hacia arriba). Para compensar esto, simplemente verificamos si hay posiciones negativas, y luego desplazamos todo el árbol hacia abajo.

Aquí está el código completo con una demostración de violín.

Demostración de Fiddle: http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/

Esto es para un editor y sería similar a

Creando un editor:

La mejor manera de probar si funciona es tener un editor que le permita crear tales árboles / gráficos sobre la marcha y ver si traza con éxito.

Entonces, también creé un editor simple para probar. El código sigue siendo exactamente el mismo, sin embargo, se ha vuelto a factorizar un poco para que coincida con las rutinas del editor.

Demo de Fiddle con el Editor: http://jsfiddle.net/abhitalks/56whqh0w/embedded/result

Demostración de fragmentos con Editor (ver pantalla completa):

var sampleData = [
  { "id":  1, "name": "Me", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [8,9] },
  { "id":  2, "name": "Mistress", "children": [4], "partners" : [1], level: 0, "parents": [] },
  { "id":  3, "name": "Wife", "children": [5], "partners" : [1], level: 0, "parents": [] },
  { "id":  4, "name": "Son", "children": [], "partners" : [], level: -1, "parents": [1,2] },
  { "id":  5, "name": "Daughter", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
  { "id":  6, "name": "Boyfriend", "children": [7], "partners" : [5], level: -1, "parents": [] },
  { "id":  7, "name": "Son Last", "children": [], "partners" : [], level: -2, "parents": [5,6] },
  { "id":  8, "name": "Jeff", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
  { "id":  9, "name": "Maggie", "children": [1], "partners" : [8], level: 1, "parents": [13,14] },
  { "id": 10, "name": "Bob", "children": [8], "partners" : [11], level: 2, "parents": [12] },
  { "id": 11, "name": "Mary", "children": [], "partners" : [10], level: 2, "parents": [] },
  { "id": 12, "name": "John", "children": [10], "partners" : [], level: 3, "parents": [] },
  { "id": 13, "name": "Robert", "children": [9], "partners" : [14], level: 2, "parents": [] },
  { "id": 14, "name": "Jessie", "children": [9], "partners" : [13], level: 2, "parents": [15,16] },
  { "id": 15, "name": "Raymond", "children": [14], "partners" : [16], level: 3, "parents": [] },
  { "id": 16, "name": "Betty", "children": [14], "partners" : [15], level: 3, "parents": [] },
 ], 
 data = [], elements = [], levels = [], levelMap = [], 
 tree = document.getElementById(''tree''), people = document.getElementById(''people''), selectedNode, 
 startTop, startLeft, gap = 32, size = 64
;

/* Template object for person */
function Person(id) {
 this.id = id ? id : '''';
 this.name = id ? id : '''';
 this.partners = [];
 this.siblings = [];
 this.parents = [];
 this.children = [];
 this.level = 0;
 this.root = false;
}

/* Event listeners */
tree.addEventListener(''click'', function(e) {
 if (e.target.classList.contains(''node'')) {
  selectedNode = e.target; 
  select(selectedNode);
  document.getElementById(''title'').textContent = selectedNode.textContent;
  fillPeopleAtLevel();
 }
});
document.getElementById(''save'').addEventListener(''click'', function() {
 var pname = document.getElementById(''pname'').value;
 if (pname.length > 0) {
  data.forEach(function(person) {
   if (person.id == selectedNode.id) {
    person.name = pname;
    selectedNode.textContent = pname;
    document.getElementById(''title'').textContent = pname;
   }
  });
 }
});
document.getElementById(''add'').addEventListener(''click'', function() {
 addPerson(document.getElementById(''relation'').value);
 plotTree();
}); 
document.getElementById(''addExisting'').addEventListener(''click'', function() {
 attachParent();
 plotTree();
}); 
document.getElementById(''clear'').addEventListener(''click'', startFresh); 
document.getElementById(''sample'').addEventListener(''click'', function() {
 data = sampleData.slice();
 plotTree();
}); 
document.getElementById(''download'').addEventListener(''click'', function() {
  if (data.length > 1) {
    var download = JSON.stringify(data, null, 4);
    var payload = "text/json;charset=utf-8," + encodeURIComponent(download);
    var a = document.createElement(''a'');
    a.href = ''data:'' + payload;
    a.download = ''data.json'';
    a.innerHTML = ''click to download'';
    var container = document.getElementById(''downloadLink'');
    container.appendChild(a);
  }
}); 

/* Initialize */
function appInit() {
 // Approximate center of the div
 startTop = parseInt((tree.clientHeight / 2) - (size / 2)); 
 startLeft = parseInt((tree.clientWidth / 2) - (size / 2)); 
}

/* Start a fresh tree */
function startFresh() {
 var start, downloadArea = document.getElementById(''downloadLink'');
 // Reset Data Cache
 data = []; 
    appInit();
    while (downloadArea.hasChildNodes()) { downloadArea.removeChild(downloadArea.lastChild); }
 
 // Add a root "me" person to start with
 start = new Person(''P01''); start.name = ''Me''; start.root = true;
 data.push(start);
 
 // Plot the tree
 plotTree();
 
 // Pre-select the root node
 selectedNode = get(''P01''); 
 document.getElementById(''title'').textContent = selectedNode.textContent;
}

/* Plot entire tree from bottom-up */
function plotTree() {
 // Reset other cache and DOM
 elements = [], levels = [], levelMap = []
 while (tree.hasChildNodes()) { tree.removeChild(tree.lastChild); }

 // Get all the available levels from the data
 data.forEach(function(elem) {
  if (levels.indexOf(elem.level) === -1) { levels.push(elem.level); }
 });
 
 // Sort the levels in ascending order
 levels.sort(function(a, b) { return a - b; });

 // For all level starting from lowest one
 levels.forEach(function(level) {
  // Get all persons from this level
  var startAt = data.filter(function(person) {
   return person.level == level;
  });
  startAt.forEach(function(start) {
   var person = getPerson(start.id);
   // Plot each person in this level
   plotNode(person, ''self'');
   // Plot partners
   plotPartners(person);
   // And plot the parents of this person walking up
   plotParents(person);
  });
  
 });
 
 // Adjust coordinates to keep the tree more or less in center
 adjustNegatives();
 
}

/* Plot partners for the current person */
function plotPartners(start) {
 if (! start) { return; }
 start.partners.forEach(function(partnerId) {
  var partner = getPerson(partnerId);
  // Plot node
  plotNode(partner, ''partners'', start);
  // Plot partner connector
  plotConnector(start, partner, ''partners'');
 });
}

/* Plot parents walking up the tree */
function plotParents(start) {
 if (! start) { return; }
 start.parents.reduce(function(previousId, currentId) {
  var previousParent = getPerson(previousId), 
   currentParent = getPerson(currentId);
  // Plot node
  plotNode(currentParent, ''parents'', start, start.parents.length);
  // Plot partner connector if multiple parents
  if (previousParent) { plotConnector(previousParent, currentParent, ''partners''); }
  // Plot parent connector
  plotConnector(start, currentParent, ''parents'');
  // Recurse and plot parent by walking up the tree
  plotParents(currentParent);
  return currentId;
 }, 0);
}

/* Plot a single node */
function plotNode() {
 var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3], 
  node = get(person.id), relativeNode, element = {}, thisLevel, exists 
 ;
 if (node) { return; }
 node = createNodeElement(person); 
 // Get the current level
 thisLevel = findLevel(person.level);
 if (! thisLevel) { 
  thisLevel = { ''level'': person.level, ''top'': startTop }; 
  levelMap.push(thisLevel); 
 }
 // Depending on relation determine position to plot at relative to current person
 if (relationType == ''self'') {
  node.style.left = startLeft + ''px''; 
  node.style.top = thisLevel.top + ''px'';
 } else {
  relativeNode = get(relative.id);
 }
 if (relationType == ''partners'') {
  // Plot to the right
  node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + ''px''; 
  node.style.top = parseInt(relativeNode.style.top) + ''px''; 
 }
 if (relationType == ''children'') {
  // Plot below
  node.style.left = (parseInt(relativeNode.style.left) - size) + ''px''; 
  node.style.top = (parseInt(relativeNode.style.top) + size + gap) + ''px'';        
 }
 if (relationType == ''parents'') {
  // Plot above, if single parent plot directly above else plot with an offset to left
  if (numberOfParents == 1) { 
   node.style.left = parseInt(relativeNode.style.left) + ''px''; 
   node.style.top = (parseInt(relativeNode.style.top) - gap - size) + ''px'';      
  } else {
   node.style.left = (parseInt(relativeNode.style.left) - size) + ''px''; 
   node.style.top = (parseInt(relativeNode.style.top) - gap - size) + ''px'';           
  }
 }
 
 // Avoid collision moving to right
 while (exists = detectCollision(node)) { 
  node.style.left = (exists.left + size + (gap * 2)) + ''px''; 
 }

 // Record level position
 if (thisLevel.top > parseInt(node.style.top)) {
  updateLevel(person.level, ''top'', parseInt(node.style.top));
 }
 element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top); 
 elements.push(element);
 
 // Add the node to the DOM tree
 tree.appendChild(node); 
}

/* Helper Functions */

function createNodeElement(person) {
 var node = document.createElement(''div''); 
 node.id = person.id; 
 node.classList.add(''node''); node.classList.add(''asset''); 
 node.textContent = person.name; 
 node.setAttribute(''data-level'', person.level);
 return node;
}

function select(selectedNode) {
 var allNodes = document.querySelectorAll(''div.node'');
 [].forEach.call(allNodes, function(node) {
  node.classList.remove(''selected'');
 });
 selectedNode.classList.add(''selected'');
}

function get(id) { return document.getElementById(id); }

function getPerson(id) {
 var element = data.filter(function(elem) {
  return elem.id == id;
 });
 return element.pop();
}

function fillPeopleAtLevel() {
 if (!selectedNode) return;
 var person = getPerson(selectedNode.id), level = (person.level + 1), persons, option;
 while (people.hasChildNodes()) { people.removeChild(people.lastChild); }
 data.forEach(function(elem) {
  if (elem.level === level) {
   option = document.createElement(''option'');
   option.value = elem.id; option.textContent = elem.name;
   people.appendChild(option);
  }
 });
 return persons;
}

function attachParent() {
 var parentId = people.value, thisId = selectedNode.id;
 updatePerson(thisId, ''parents'', parentId);
 updatePerson(parentId, ''children'', thisId);
}

function addPerson(relationType) {
 var newId = ''P'' + (data.length < 9 ? ''0'' + (data.length + 1) : data.length + 1), 
  newPerson = new Person(newId), thisPerson;
 ;
 thisPerson = getPerson(selectedNode.id);
 // Add relation between originating person and this person
 updatePerson(thisPerson.id, relationType, newId); 
 switch (relationType) {
  case ''children'': 
   newPerson.parents.push(thisPerson.id); 
   newPerson.level = thisPerson.level - 1; 
   break;
  case ''partners'': 
   newPerson.partners.push(thisPerson.id); 
   newPerson.level = thisPerson.level; 
   break;
  case ''siblings'': 
   newPerson.siblings.push(thisPerson.id); 
   newPerson.level = thisPerson.level; 
   // Add relation for all other relatives of originating person
   newPerson = addRelation(thisPerson.id, relationType, newPerson);
   break;
  case ''parents'': 
   newPerson.children.push(thisPerson.id); 
   newPerson.level = thisPerson.level + 1; 
   break;
 }
 
 data.push(newPerson);
}

function updatePerson(id, key, value) {
 data.forEach(function(person) {
  if (person.id === id) {
   if (person[key].constructor === Array) { person[key].push(value); }
   else { person[key] = value; }
  }
 });
}

function addRelation(id, relationType, newPerson) {
 data.forEach(function(person) { 
  if (person[relationType].indexOf(id) != -1) {
   person[relationType].push(newPerson.id);
   newPerson[relationType].push(person.id);
  }
 });
 return newPerson;
}

function findLevel(level) {
 var element = levelMap.filter(function(elem) {
  return elem.level == level;
 });
 return element.pop();
} 

function updateLevel(id, key, value) {
 levelMap.forEach(function(level) {
  if (level.level === id) {
   level[key] = value;
  }
 });
}

function detectCollision(node) {
 var element = elements.filter(function(elem) { 
  var left = parseInt(node.style.left);
  return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
 });
 return element.pop();
}

function adjustNegatives() { 
 var allNodes = document.querySelectorAll(''div.asset''), 
  minTop = startTop, diff = 0;
 for (var i=0; i < allNodes.length; i++) {
  if (parseInt(allNodes[i].style.top) < minTop) { minTop = parseInt(allNodes[i].style.top); }
 };
 if (minTop < startTop) {
  diff = Math.abs(minTop) + gap; 
  for (var i=0; i < allNodes.length; i++) {
   allNodes[i].style.top = parseInt(allNodes[i].style.top) + diff + ''px'';
  };
 }
}

function plotConnector(source, destination, relation) {
 var connector = document.createElement(''div''), orientation, start, stop, 
  x1, y1, x2, y2, length, angle, transform
 ; 
 orientation = (relation == ''partners'') ? ''h'' : ''v'';
 connector.classList.add(''asset'');
 connector.classList.add(''connector'');
 connector.classList.add(orientation);
 start = get(source.id); stop = get(destination.id);
 if (relation == ''partners'') {
  x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
  x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
  length = (x2 - x1) + ''px'';
  
  connector.style.width = length;
  connector.style.left = x1 + ''px'';
  connector.style.top = y1 + ''px'';
 }
 if (relation == ''parents'') {
  x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
  x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);
  
  length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  angle  = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
  transform = ''rotate('' + angle + ''deg)''; 
  
  connector.style.width = length + ''px'';
  connector.style.left = x1 + ''px'';
  connector.style.top = y1 + ''px'';
  connector.style.transform = transform;
 }
 tree.appendChild(connector);
}
  
/* App Starts Here */
appInit();
startFresh();

* { box-sizing: border-box; padding: 0; margin: 0; }
html, body { width: 100vw; height: 100vh; overflow: hidden; font-family: sans-serif; font-size: 0.9em; }
#editor { float: left; width: 20vw; height: 100vh; overflow: hidden; overflow-y: scroll; border: 1px solid #ddd; }
#tree { float: left; width: 80vw; height: 100vh; overflow: auto; position: relative; }
h2 { text-align: center; margin: 12px; color: #bbb; }
fieldset { margin: 12px; padding: 8px 4px; border: 1px solid #bbb; }
legend { margin: 0px 8px; padding: 4px; }
button, input, select { padding: 4px; margin: 8px 0px;  }
button { min-width: 64px; }
div.node {
 width: 64px; height: 64px; line-height: 64px;
 background-color: #339; color: #efefef;
 font-family: sans-serif; font-size: 0.7em;
 text-align: center; border-radius: 50%; 
 overflow: hidden; position: absolute; cursor: pointer;
} 
div.connector { position: absolute; background-color: #333; z-index: -10; }
div.connector.h { height: 2px; background-color: #ddd; }
div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }
div[data-level=''0''] { background-color: #933; }
div[data-level=''1''], div[data-level=''-1''] { background-color: #393; }
div[data-level=''2''], div[data-level=''-2''] { background-color: #333; }
div.node.selected { background-color: #efefef; color: #444; }

<div id="editor">
 <h2 id="title">Me</h2>
 <div>
  <fieldset>
   <legend>Change Name</legend>
   <label>Name: <input id="pname" type="text" /></label>
   <br /><button id="save">Ok</button>
  </fieldset>
  <fieldset>
   <legend>Add Nodes</legend>
   <label for="relation">Add: </label>
   <select id="relation">
    <option value="partners">Partner</option>
    <option value="siblings">Sibling</option>
    <option value="parents">Parent</option>
    <option value="children">Child</option>
   </select>
   <button id="add">Ok</button><br />
   <label for="relation">Add: </label>
   <select id="people"></select>
   <button id="addExisting">As Parent</button>
  </fieldset>
  <fieldset>
   <legend>Misc</legend>
   <button id="clear">Clear</button>&nbsp;&nbsp;<button id="sample">Load Sample</button>
            <br/><button id="download">Download Data</button>
  </fieldset>
        <fieldset id="downloadLink"></fieldset>
 </div>
</div>
<div id="tree"></div>

Todo esto es un intento muy crudo y más allá de dudas, una no optimizada. Lo que particularmente no pude hacer es:

1. Obtención de conectores horizontales invertidos [ o ] para relaciones entre padres e hijos.
2. Hacer que el árbol esté equilibrado horizontalmente. es decir, determinar dinámicamente cuál es el lado más pesado y luego desplazar esos nodos hacia la izquierda.
3. Lograr que el padre se alinee centralmente con respecto a los niños, especialmente a los múltiples niños. Actualmente, mi intento simplemente empuja todo a la derecha en orden.

Espero eso ayude. Y publicarlo aquí para que yo también pueda consultarlo cuando sea necesario.

Answer 3

From what I can see - without looking at the code you have there (for now) - you have a DAG (the visual representation is another matter, now I''m talking only about the data structure). Each node has a maximum of 2 incoming connections and no constraint on connections going to other nodes (one can have an arbitrary number of children but we have info on a maximum of 2 parents for each person/node).

That being said, there will be nodes that do not have parents (in this case are "john", "raymond", "betty", "mistress 1", "wife 1", and "daughter 1 boyfriend"). If you do a BFS on the graph starting from these nodes - which would compose level 0 - you get the nodes for each level. The correct level has to be updated on the fly though.

Regarding the visual representation, I''m no expert, but IMO it can be achieved via a grid (as in, a table-like one) view. Each row contains the nodes of a certain level. The elements in a given row are arranged based on the relationship with the other elements in the same row, in row x - 1 , and in row x + 1 .

Para explicar mejor la idea, creo que es mejor poner un pseudocódigo (no JS, ya que no es mi fuerza):

getItemsByLevel(Graph graph)
{
    Node[,] result = new Node[,];
    var orphans = graph.getOrphans();
    var visiting = new HashMap();
    var visited = new HashMap();
    var queue = new Queue<Node>();

    queue.pushAll(orphans);

    while(!queue.isEmpty())
    {
        var currentNode = queue.pop();

        if(currentNode.relatedNodes.areNotBeingVisited()) // the nodes that should be on the same level
        {
            // the level of the current node was not right
            currentNode.level++;
            queue.push(currentNode);
        }
        else
        {
            var children = currentNode.children;

            foreach(var child in children)
            {
                child.level = currentNode.level + 1;
                queue.push(child);
            }

            visited.insert(currentNode);
            result[currentNode.level, lastOfRow] = currentNode;
        }
    }

    return result;
}

Al final del procedimiento, tendrá una matriz de nodos donde row icontiene los nodos de nivel i. Solo tiene que representarlos en la vista de cuadrícula (o lo que elija como diseño).

Avíseme si algo no está claro.

Answer 4

This is not that far from how the Sugiyama algorithm is used to layout class hierarchies, so you might want to take a look at papers that discuss that. There''s a book chapter that covers Sugiyama and other hierarchical layout algorithms here .

I''d lay out the upper and lower halves of the tree independently. The thing to recognize about the upper half is that, in its fully populated form, it''s all powers of two, so you have two parents, four grandparents, sixteen great-grandparents, etc.

As you do your depth-first search, tag each node with a) it''s layer number and b) its collating order. Your data structure doesn''t include gender and you really need this both for stylistic reasons and to figure out the collating order. Fortunately, all genealogy data includes gender.

We''ll tag fathers with "A" and mothers with "B". Grandparents get another letter appended, so you get:

father jeff - A, layer 1
mother maggie - B, layer 1
paternal grandfather bob - AA, layer 2
paternal grandmother mary - AB, layer 2
paternal grandfather robert - BA, layer 2
paternal grandmother jessie - BB, layer 2
g-g-father john - AAA, layer 3
etc

Add the nodes to a list for each layer as you go. Sort each layer by their gender keys (unless using sorted lists). Start your layout at the layer with the highest number and lay out the nodes from left (AAAAA) to right (BBBBB), leaving gaps for any missing nodes. Stylistically, decide if you want to collapse around missing nodes and, if so, by how much (although I''d recommend implementing the simple-minded version first).

Lay out the layers in descending order. If there''s no collapsing/adjusting of positions, lower layer positions can be computed directly. If you''re adjusting, you''ll need to refer to the parents position in the previous layer and center the child under that.

The lower half of the diagram can be done in a similar fashion, except that instead of sorting by gender, you''d probably want to sort by birth order and build up your keys from that eg eldest child of eldest child has key "11" while eldest child of the second eldest child is "21" etc.

You could do this with a graph library like cola.js, but you''d only be using a sliver of its functionality and some of the stylistic elements that you want (eg keep father & mother close together), would probably need to be added separately, so I suspect it''s as easy to build from scratch unless you need other functionality from the library.

Speaking of style, it''s customary to use a different line style for the parent connector (traditionally it''s a double line). Also, you don''t want the "Mistress" node laid out on top of the "me" / "wife" edge.

ps With fixed size nodes, you can get away with a simple grid for your coordinate system.

Answer 5

This is not trivial question and it involves large corpus of research in graph drawing algorithms.

The most prominent approach for this problem is through constraints satisfaction. But don''t try to implement this on your own (unless you want to learn something new and spend months debugging)

I cannot recommend highly enough this library: cola.js ( GitHub )

The particular example that may be very close to what you need is grid layout.