47 votes

Rendu d'un graphe de famille créé dynamiquement sans chevauchement à l'aide d'une première recherche de profondeur?

Je veux générer ce:

enter image description here

Avec cette structure de données (id aléatoire, btw non séquentielle):

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": [] },
];

Pour donner une description de la structure des données, la racine/noeud de départ (moi) est défini. Tout partenaire (femme,ex) est sur le même niveau. Tout devient-dessous du niveau -1, -2. Tout ce qui précède est de niveau 1, 2, etc. Il y a des propriétés pour les parents, les frères et sœurs, enfants et partenaires qui définissent les numéros pour ce domaine particulier.

Dans ma précédente question, eh9 décrit comment il allait régler ce. Je tente de le faire, mais comme je l'ai découvert, il n'est pas une tâche facile.

Ma première tentative est rendu présent par niveaux, de haut en bas. Dans ce plus simple tentative, j'ai essentiellement nid tous les gens par niveaux et de rendre ce de haut en bas.

Ma deuxième tentative est rendu avec cette une de l'ancêtre des nœuds à l'aide d'une profondeur d'abord de recherche.

Ma principale question est: Comment puis-je appliquer effectivement que la réponse à ce que j'ai actuellement? Dans ma deuxième tentative, j'ai essaye de faire un parcours en profondeur d'abord la traversée, mais comment puis-je commencer à compte pour le calcul de la distance nécessaire pour compenser les grilles pour le rendre compatible avec la façon dont je veux générer ce?

Aussi, c'est de ma compréhension et de mise en œuvre de la profondeur d'abord l'idéal, ou puis-je traverser autrement?

Les nœuds évidemment se chevauchent dans mon deuxième exemple, puisque je n'ai pas de compensation/calcul de la distance de code, mais je suis perdu à essayer de comprendre comment je peux commencer.

Voici une description de la marche de la fonction que j'ai fait, où je suis tenter de faire un parcours en profondeur d'abord de la traversée:

// 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 );
                    });
            });
        }
    });


}

}

Exigences et restrictions:

  1. C'est pour un éditeur et serait semblable à familyecho.com. Pratiquement toutes les règles commerciales ne peuvent être pris en charge au moyen que.
  2. En élevage familial n'est pas pris en charge comme il le ferait de cette façon trop complexe. Ne vous inquiétez pas à ce sujet.
  3. Plusieurs partenaires sont pris en charge si ce n'est pas aussi facile que d'un traditionnel "arbre généalogique" avec seulement 2 parents et 1 enfant.
  4. Il n'y a qu'un seul "root" nœud, ce qui est tout le nœud de départ.

Notes: familyecho.com l'air de "cacher" une branche si il y a beaucoup de nœuds feuilles et il y a une collision. Peut-être besoin de mettre en œuvre cette.

11voto

abhitalks Points 7068

Même si une réponse a été posté (et accepté), je pensais qu'il n'y a pas de mal à poster ce que j'ai travaillé sur ce problème la nuit dernière.

J'ai abordé ce problème à plus d'un novice point de vue plutôt que de travailler avec des algorithmes existants de graphique/l'arbre transversal.

Ma première tentative est rendu présent par niveaux, de haut en bas. Dans cette simple tentative, j'ai essentiellement nid de toutes les personnes en les niveaux et rendre cette, de haut en bas.

C'était exactement ma première tentative. Vous pourriez parcourir l'arbre de haut en bas ou de bas en haut, ou à partir de la racine. Comme vous avez été inspiré par un site web particulier, à partir de la racine semble être un choix logique. Cependant, j'ai trouvé l'approche bottom-up pour être plus simple et plus facile à comprendre.

Voici une grossière tentative:

La représentation des données:

  1. Nous commençons par le bas-couche et de travailler notre chemin vers le haut. Comme mentionné dans la question que vous essayer de s'en sortir par le biais d'un éditeur, on peut conserver toutes les propriétés liées dans le tableau d'objets que nous construisons l'arbre.

Nous cache les niveaux et les utiliser que pour marcher jusqu'à l'arbre:

// 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);
    });
});

Où, getPerson obtient l'objet à partir de la base de données sur sa id.

  1. Lorsque nous marchons, nous avons tracé le nœud lui-même, de ses parents (de manière récursive) et de ses partenaires. Traçage des partenaires n'est pas vraiment nécessaire, mais je l'ai fait ici simplement pour tracer les connecteurs peuvent être facile. Si un nœud a déjà été tracées, nous avons simplement sauter cette partie.

C'est la façon dont nous avons tracé les partenaires:

/* 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');
    });
}

Et les parents de manière récursive:

/* 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);
}

Lorsque nous utilisons reduce pour simplifier le tracé d'un connecteur entre les deux parents en tant que partenaires.

  1. C'est ainsi que nous tracer un nœud lui-même:

Où, nous réutilisons les coordonnées de chaque niveau unique via l' findLevel fonction d'utilité. Nous maintenons une carte de niveaux et de vérifier que pour arriver à l' top position. Le repos est déterminée sur la base de relations.

/* 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); 
}

Ici, pour faire simple, j'ai utilisé un très brut de détection de collision pour déplacer des nœuds à droite quand il en existe déjà un. Dans un plus sophistiqué de l'app, ce serait de déplacer des nœuds de façon dynamique vers la gauche ou la droite pour maintenir un équilibre horizontal.

Enfin, nous ajoutons que le nœud du DOM.

  1. Reste sont tous des fonctions d'assistance.

Les plus importants sont:

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();
}

Ci-dessus est une simple détection de collision en tenant compte de l'écart entre les nœuds.

Et, pour tracer les connecteurs:

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);
}

J'ai utilisé deux connecteurs, l'un horizontal, l'un pour connecter des partenaires, et à l'angle de l'un de connecter les relations parent-enfant. Ceci s'est avéré être très difficile pour moi, c'est à dire à la parcelle inversé ] horizontal connecteurs. C'est pourquoi, pour faire simple, j'ai simplement tourné un div pour la faire ressembler à un angle de connecteur.

  1. Une fois la totalité de l'arbre est dessiné/tracées, il pourrait y avoir des nœuds qui vont sortir de l'écran à cause de la détérioration des positions (parce que nous sommes traversant de bas en haut). Pour compenser cela, nous avons tout simplement vérifier s'il y a toute les positions négatives, et ensuite déplacer la totalité de l'arbre vers le bas.

Voici le code complet avec un violon de démonstration.

Violon de Démonstration: http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/


C'est pour un éditeur et serait semblable à

La création d'un éditeur:

La meilleure façon de tester si cela fonctionne, c'est d'avoir un éditeur qui permet de créer de tels arbres/graphiques à la volée et voir si elle parcelles avec succès.

Donc, j'ai également créé un éditeur simple à tester. Le code est exactement le même, cependant, a été re-compte un peu pour s'adapter avec les routines de l'éditeur.

Violon Démonstration par l'Éditeur: http://jsfiddle.net/abhitalks/56whqh0w/embedded/result

Extrait de la Démo avec de l'Éditeur (affichage plein écran):

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>

C'est une très grossière tentative et au-delà des doutes non-optimisé. Ce que je ne pouvais pas faire sont:

  1. Obtenir inversé [ ou ] de forme horizontale connecteurs pour les relations parent-enfant.
  2. L'obtention de l'arbre horizontalement de manière équilibrée. c'est à dire de façon dynamique déterminer qui est le plus lourd d'un côté, puis déplacer ces noeuds à gauche.
  3. L'obtention de la mère de façon centralisée les aligner à l'égard des enfants surtout plusieurs enfants. Actuellement, ma tentative pousse tout simplement tout à droite dans l'ordre.

Espérons que cela aide. Et de le poster ici pour que j'ai trop de pouvoir la consulter en cas de besoin.

10voto

manuBriot Points 1845

Comme vous le montrer, votre arbre de données ne vous permettra pas de dessiner le diagramme. Vous êtes en fait en manque quelques informations:

  • l'arbre doit vraiment être un objet (dictionnaire) cartographie de l'id de la personne. Sinon, c'est coûteux à aller de l'id, comme donné en children par exemple, le dos de l'enfant.
  • il est de dupliquer l'information, puisque les enfants sont associés avec les deux parents. De ce fait provoquer des erreurs de données dans l'exemple que vous avez envoyé ('daugher1' est un enfant de la "femme", mais les parents de 'moi', et 'marie' est sans doute la mère de 'jeff'; jessie est un partenaire de robert; il en est de raymond et betty)

Dans ma tentative (https://jsfiddle.net/61q2ym7q/), je suis donc la conversion de votre arbre d'un graphe, et ensuite de faire les différentes étapes du calcul pour obtenir une mise en page.

C'est inspiré par la Sugiyama algorithme, mais simplifiée, étant donné que l'algorithme est très difficile à mettre en œuvre. Encore, les différentes étapes sont les suivantes:

  • organiser les nœuds en couches, en utilisant la profondeur de la première recherche. Nous faisons cela en deux étapes, en faisant en sorte que les parents sont toujours sur un calque au-dessus de leur parent, puis en essayant de raccourcir les liens quand il y a plus d'un calque entre enfant et parent. C'est la partie où je ne suis pas en utilisant exactement les Sugiyama algorithme, qui utilise une notion complexe de points de coupe.

  • ensuite trier les nœuds dans chaque couche pour minimiser la traversée des arêtes. J'utilise la méthode du barycentre pour cette

  • enfin, tout en préservant l'ordre ci-dessus, d'attribuer des coordonnées x, pour chaque nœud, de nouveau à l'aide de la méthode du barycentre

Il y a beaucoup de choses qui peuvent être améliorées dans le présent code (efficacité, par la fusion de certaines des boucles par exemple) et aussi dans la mise en page finale. Mais j'ai essayé de le simplifier pour le rendre plus facile à suivre...

9voto

Tom Morris Points 6022

Ce n'est pas loin de la façon dont le Sugiyama algorithme est utilisé pour la mise en hiérarchies de classe, de sorte que vous voudrez peut-être jeter un oeil à des papiers qui en discuter. Il y a un chapitre de livre qui couvre Sugiyama et d'autres hiérarchique algorithmes de disposition ici.

J'aimerais disposer les moitiés supérieure et inférieure de l'arbre de façon indépendante. La chose à reconnaître sur la moitié supérieure est que, dans son entièrement rempli le formulaire, c'est toutes les puissances de deux, si vous avez deux parents, quatre grands-parents, seize arrière-grands-parents, etc.

Tant que vous faites votre recherche depth-first, étiquette de chaque nœud avec une) c'est le numéro de calque et b) de son ordre de classement des caractères. Votre structure de données n'inclut pas le sexe et que vous avez vraiment besoin de ce à la fois pour des raisons de style et de déterminer l'ordre de classement des caractères. Heureusement, toute la généalogie de données inclut le genre.

Nous allons tag pères avec "A" et les mères avec des "B". Les grands-parents reçois une autre lettre ajoutée, de sorte que vous obtenez:

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

Ajouter les nœuds à une liste pour chaque couche que vous allez. Trier chaque couche de par leur genre touches (sauf à l'aide de listes triées). Commencez votre disposition à la couche avec le plus grand nombre et de jeter les nœuds à partir de la gauche (AAAAA) à droite (BBBBB), laissant des lacunes qu'il ne manque aucun des nœuds. Stylistiquement, décider si vous souhaitez réduire autour des noeuds manquants et, si oui, de combien (bien que je recommande la mise en œuvre de la simple d'esprit en premier la version).

Disposer les couches dans l'ordre décroissant. Si il n'y a pas d'effondrement/réglage de positions, la couche inférieure, les positions peuvent être calculées directement. Si vous réglez, vous aurez besoin de consulter les parents de la position dans la couche précédente et le centre de l'enfant en vertu de cette.

La moitié inférieure du diagramme peut être fait de la même façon, sauf qu'au lieu d'effectuer un tri par genre, vous auriez probablement souhaitez trier par ordre de naissance, et de construire vos clés à partir, par exemple, aîné des enfants de l'aîné des enfants a la clé "11", tandis que le plus âgé des enfants de la deuxième enfant aîné est "21", etc.

Vous pouvez le faire avec un graphique de la bibliothèque comme cola.js mais vous ne être à l'aide d'un ruban de sa fonctionnalité et de certains des éléments de style que vous souhaitez (par exemple, de garder le père et la mère rapprochés), aurait sans doute besoin d'être ajouté séparément, donc je suppose que c'est aussi facile à construire à partir de zéro, sauf si vous avez besoin d'autres fonctionnalités de la bibliothèque.

En parlant de style, il est d'usage d'utiliser un autre style de ligne du parent connecteur (traditionnellement, c'est une double ligne). En outre, vous ne voulez pas que la "Maîtresse" nœud disposée sur le dessus du "moi" / "femme" au bord.

p.s. Avec une taille fixe de nœuds, vous pouvez vous en sortir avec une simple grille de votre système de coordonnées.

5voto

Anvaka Points 9296

Ce n'est pas anodin, et il comprend de grands corpus de la recherche dans les algorithmes de dessin de graphes.

Le plus éminent de l'approche de ce problème est par le biais de contraintes de satisfaction. Mais n'essayez pas d'appliquer ce sur votre propre (sauf si vous voulez apprendre quelque chose de nouveau et de passer des mois de débogage)

Je ne peux pas recommander assez fortement cette bibliothèque: cola.js (GitHub)

Le particulier exemple qui peut être très proche de ce que vous avez besoin est de la grille de mise en page.

5voto

Gentian Kasa Points 644

De ce que je peux voir sans regarder le code que vous avez là (pour l'instant) - vous avez un DAG (la représentation visuelle est une autre question, maintenant, je suis en parle seulement de la structure de données). Chaque nœud a un maximum de 2 connexions entrantes et aucune contrainte n'est imposée sur les connexions à d'autres nœuds (on peut avoir un nombre arbitraire d'enfants, mais nous avons des informations sur un maximum de 2 parents pour chaque personne/nœud).

Cela étant dit, il y aura des nœuds qui n'ont pas de parents (dans ce cas sont des "jean", "raymond", "betty", "maîtresse 1", "femme 1", et "fille de 1 copain"). Si vous faites un BFS sur le graphique à partir de ces nœuds qui composent le niveau 0, vous obtenez les nœuds pour chaque niveau. Le niveau approprié doit être mis à jour à la volée.

Concernant la représentation visuelle, je ne suis pas expert, mais IMO il peut être réalisé par l'intermédiaire d'une grille (comme dans un tableau) de la vue. Chaque ligne contient les nœuds d'un certain niveau. Les éléments dans une ligne donnée sont disposées basée sur la relation avec les autres éléments de la même ligne, en ligne x - 1, et dans la ligne x + 1.

Pour mieux expliquer l'idée, je suppose que c'est mieux de mettre en pseudo-code (pas de JS mais comme ce n'est pas mon fort):

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

À la fin de la procédure, vous allez avoir une matrice de nœuds où la rangée i contient les nœuds de niveau i. Vous avez juste à les représenter dans le contrôle gridview (ou ce que vous choisissez comme la mise en page).

Laissez-moi savoir si quelque chose n'est pas clair.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by: