[JS KineticJS] Мащаб на семейното дърво


13
Колко голямо трябва да е дървото което трябва да се направи , да е както на примера максимум със 3 нива или трябва да работи при всякакви варианти . Защото ако е при всякакви вариант се налага рекурсивно обхождане и проверка за родители и т.н. и става доста по сложно и бяга от идеята за канвас домашно .
EDIT: Ето един тест , всички в него имат роднинска връзка, няма кръвосмешение и няма повтарящи се имена http://pastebin.com/PRXu047x Image : http://s24.postimg.org/pcfpt6zud/Family_Tree.png ПС : Не ме бива да рисувам :)



Отговори



11

Решение Демо

Даже няма звездичка тази задача :))

Първо си правя обекти от тип Human - имат си пол, партньор, деца, родител и име. Обхождам всички подадени обекти и им задавам тези стойности - понеже не съм сигурен че няма да са подадени разбъркано. Връщам освен масив със всички хора, масив с прародители - такива които си нямат родители (корени). 

После пак обхождам в широчина и добавям индекси на всеки човек - къде трябва да седи в дървото (дълбочина и Х координата).

Самото рисуване проверява пола и прави съответното квадратче. Ако човека няма партньор не се знае дали е жена или мъж - понеже по условие децата са само имена и пола им става ясен ако участват в семейство. Проверява се дали човека има партньор - ако да се рисува връзка между тях.

Когато се рисува всеки човек се проверява дали има родител - ако има се прави връзка между по-левия от родителя и партньора на родителя (така работи самото рисуване на тези криви линиики) и самото дете.

За да работи коректно не трябва да се повтарят имената - което лесно може да се промени ако се задава и ЕГН на всеки човек и проверките после ползват него.

В самото демо има 3 теста (3тия е с 100 нива на наследяване - зарежда 3 - 4 сек) и един бутон да си вкарвате вие масива в input-a :))

Надявам се кода да е достатъчно четим :))


от dzhenko (3893 точки)


0
Не съм ти чел кода , по принцип Павлина и Генади трябва да са на втория ред , това за да се постигне трябва да намериш най дългия път в йерархията , и от него да пуснеш рекурсивно да изчислява позициите по редове вече за да се наредят всяко поколение на един и същи ред . Предвид колко е извратена задача може и да не се занимаваш с това :)

от TeodorTunev (3061 точки)


0
До колкото разбрах, имаш масив от много семейства и твоята програма трябва да ги направи на родословно дърво.
Входните данни трябва да са като масива от примера, а самата картинка може да е подобна като на картинката. Виж лекцията на Дончо.
Това е една от тези задачи, с които те карат да прочетеш нещо ново за да я решиш.

от lithical (992 точки)


0
Това и аз го разбрах , ама ти представяш ли си да имаш родители които има по 3 деца , които всички са женени и на техните семейства родителите и на техните наследници и внуци и т.н. Трябва да се пишат алгоритми и изчисления и т.н. , а все пак домашното е за канвас :) за това питам ще има ли ограничения на дървото ...

от TeodorTunev (3061 точки)

0
Според мен трябва да се пишат.

от lithical (992 точки)


0
Снощи попитахме точно това на лекцията и отговорът беше, че трябва да се генерира само за колкото и големи входни данни да му дадем, така че трябва да работи при всякакви варианти, а не само при хардкоднати данни примерно от примера.

от kalbo_17 (2709 точки)


2

Ето тук четвъртата лекция е за обхождане на дървета - родословното е подобно, така че нямаш проблем. Лекцията е много интересна и тъкмо ще си напред с материала като стигнем до DSA. Построяването на дървото става доста лесно само като знаеш кой на кого е родител/дете. Ако искаш да го обхождаш, конкретно за родословното дърво според мен BFS алгоритъма ще ти свърши работа. Друг е въпросът как да стане всичко това на JS, но мисля че ще се справим :)

Виж и видеото с решаване на част от домашното от Ники - там си е описано едно към едно как се прави дървото.

Успех с домашното.


от wnvko (3123 точки)


0
Не е проблема да го обходя :) това е лесно , проблема е да го нарисуваш без да го омажеш :) Смисъл замисли се за някой труден примерер , да речем имаш едни родители които имат 2 деца , техните деца са женени , и техните съпрузи и съприги имат родители , които също имат по 3 дена които също са женени и техните съпрузи/съпруги имат родители :D , до тук обяснявам само първите 2 реда на дървото , ами като спуснеш надоло деца и семейства и т.н. :D става мазало което ако трябва да изчисляваш нещо ще стане , ама за домашно по канвас мисля , че трябва да има някво ограничение ...

от TeodorTunev (3061 точки)

0
ами ако гледаме на нещата от тази гледна точка родословното дърво ще е с около шест милиарда върха :) аз лично разбирам родословното дърво като леко разширено нормално дърво, т.е. имаш корен - двама човека. След това имаш техните деца и тук идва единствената разлика с нормално дърво, че те може да си имат мъж/жена. След това обаче трябва да продължаваш само на "долу", т.е. на децата на "корена" да потърсиш децата. След това те дали имат мъж/жена и т.н. и т.н. Не смятам, че е редно в родословното дърво да се връщаш на горе, но това е по-скоро въпрос на гледна точка. Според мен ако се връщаш на горе ще е родословен граф, а не дърво! Със сигурност има доста сложни житейски истории, който няма да може да опишем с нашето дърво, но със сигурност не е това целта.

от wnvko (3123 точки)



0
Днес 4 часа писах 20 реда код. Вече имам функция, която по тия данни които ни подават, изгражда масив от обекти. Всеки един елемент е един човек. Знае кои са му родителите, кой му е съпруга и кои са му децата. Остава ми да добавя поле, което да показва на кое ниво от дървото съм, което също е лесно - просто децата имат ниво +1, а родителите - ниво -1 от дадения човек. Тръгваш от този, който има най-малко ниво, слагаш го най-горе и почваш да слизаш надолу. Всички които имат едно и също ниво са на един ред от рисунката. Слизаш надолу, докато стигнеш до някой, който няма деца.
Нещата не са рекурсивни, или поне не е необходимо да са.
С моя начин нямам никакви ограничения за броя на нивата или широчината на дървото. Стига да има памет и място на екрана - ще се изрисуват.

от JulianG (5316 точки)


0
ок :) ще си поиграя 20 минути да ти напиша един тест :)

от TeodorTunev (3061 точки)

0
http://pastebin.com/PRXu047x бих се радвал да видя как излиза , няма повтаряне на имена , не съм слагал фамилии , но предполагам няма да е проблем :)

от TeodorTunev (3061 точки)



1
Според днешната лекция на Дончо, ако кода работи за 100 - 150 обекта, значи е ОК! А как ще го имплементираме, като се сетя ще кажа :).



0
100-150 нива :) обектите може да са доста повече :)

от DonchoMinkov (12706 точки)


3

Едно решение, което покрива на 90% (edit: вече на 100%) задачата.

HTML код, JS код

Към всички обекти добавям едно пропърти level и още едно - масив, в който съхранявам индексите на елементите с децата, за да мога после да им избутам level-ите.

Проверявам всеки родител дали не е дете и ако е - увеличавам level-а на обекта и на всички деца под него рекурсивно.

Накрая добавям правоъгълници и текста в масив, от който намирам и линиите и ги добавям в layer-a.

Кодът е ужасен, ще рефакторирам, почти сигурно може да има някой бъг.

Качете си .js файла и kinetic-v5.0.2.min.js в папка scripts.

 

Edit: Учудвам се, че тази задача не е със звездичка.


от Drago (711 точки)


0
Вероятно задачата е дадена за да видим, че с KineticJS не се прави лесно дърво/граф и вероятно в следващите лекции за SVG ще се разгледат библиотеки, с които става много по-лесно. :>
https://github.com/mbostock/d3/wiki/Gallery

от martin.nikolov (4535 точки)

0
Е да бяха дали и някоя друга да упражним Кинетика , така ако не можеш да направиш дървото оставаш без домашно ...

от TeodorTunev (3061 точки)



4

Аз я реших по следния начин. Използвах рекурсия и тествах с 15нива. Отне половин ден да я реша - гледах видеото за дървета и от него разбрах как да си намеря корена.
 

Търсене в масива:

1. Елементите са готов Node с Кеy - майката и бащата и  Value - децата. Когато търся Key, проверявам дали майката или бащата на един Node съвпадат с някое от децата на друг Node.

2. Намирам корена на дървото в масива, трия го от масива и изчертавам. Запазвам си къде са децата на екрана.

3. Намирам семействата на децата в масива, трия ги от масива и ги изчертавам. Запазвам си къде са им децата на екрана.

4. Повтарям третото до като семействата в масива свършат.

Изчертавяне:

Първите ги слагам най-горе и по средата на канваса, а за децата смятам цялата дължина като запазвам места за съпруга/съпругата и ги центрирам под тях и така за всички други. Нещата ще се объркат малко ако семейставата имат по много деца и трябва да се правят допълнителни сметки за това.... Пример: Първите деца на втория ред - има едно дете Boris Opanov без семейство, ако то имаше семейство неговите деца щяха да съвпадат с другите деца на третия ред. Аз не правя такива проверки, в моето решение в момента.


Ето масив с 15 нива http://pastebin.com/Ai71EYbP

Резултатът е това: http://i61.tinypic.com/1qhpg4.png


от lithical (992 точки)


0
Решението ти работи ли с няколко корена?

от Drago (711 точки)

0
само с един съм го пробвал.

от lithical (992 точки)



1

Работи някак си... ето го резултата с теста на pavelh:

http://i.imgur.com/z6PIvg4.jpg

Според мен задачата изобщо не беше за kineticjs ... 2 дена правя алгоритъма който да подреди баби, дядовци и внуци по вертикала, но хоризонталното подреждане ... просто нямам идея откъде да го почна. Намирисва ми на графи, оптимизации на маршрути и други такива нещица, дето хал-хабер си нямам откъде да ги почна.

 

P.S. Ето и решение по даните на Теодор Тунев

http://i.imgur.com/A2oUsdH.jpg


от JulianG (5316 точки)


0
Жените трябва да са различни от мъжете според картинката на условието. Update: На втория ред - Teodor Stamatov и Boriana Stamatova не са едно до друго като едно семейство .

от lithical (992 точки)


2
Ето решението на колегата Drago малко променено и довършено. Промених имената на някои променливи, цветове, изкарах ги във функции и добавих функционалност за децата без наследници. Какво правя за това :
1) Добавих един нов масив parentsWithHеirs - добавям в него всички С наследници
2) Пускам проверка за всички от familyMembers, като ако има member, който не е в parentsWithHеirs, то значи не е вече добавен и трябва да го добавим. Променил съм малко логиката за countEqualLevels, вече се казва countOfMembersInLevel и брои колко хора има на едно ниво, за да знае от къде да започне да поставя тези без наследници. По този начин те винаги са след тези с наследници по хоризонтала.
3) Добави и проверка за мъж-жена, като когато е Mother father, лесно се определя, а за тези без наследници следя последната буква :) Все пак е за български имена, така че (обикновено) дамите завършват на "а".
4) По този начин вече всички са в списъка и при Print се виждат всички връзки. При връзките съм добавил и един Circle, за по-добър изглед :)
 
Ето тук може да се види как изглежда. А това е кода.
 
Изказвам благодарности към Drago без който на дали щях да го направя :) Направо се чудех как да "захапя".
 
 
 

от penjurov (1466 точки)


0
Поздравления, че си ми разчел кода. Аз не търся разлики в пола - така кодът е по-универсален. Освен това модерните практики (визирам най-вече Холандия) показват, че еднополовите родители съществуват :)

от Drago (711 точки)

0
Кодът ти си беше много добре четим :) Не мисля, че някой не би го разчел. А за половете, добре че не сме в Астралия, че там официално си има и трети пол, та как щяхме да ги различаваме вече не зная :D

от penjurov (1466 точки)


7

Ето го и моето дръвце:

DEMO

SOURCE CODE

Тръгнах с идеята, че родословното дърво трябва да има само един корен и затова задачата работи само за 1 корен. Лесно може да се направи да работи за произволен брой корени, но самите връзки няма да се чертаят правилно, тъй като не е предназначена за този сценарий.

Реализирал съм го с търсене с широчина + queue, като father-mother е node, а децата им също са node от тип (father-mother).

За съжаление има и бъгове, не се разширяват правилно поддърветата и оттам цялото дърво -> може да има фигури една върху друга. Това е проблема на това решение (дърво, което се разширява отляво и отдясно), може да се избегне като се направи дърво, което се разширява само от едната страна.

Доста лесно може да се промени наклона на дървото, още по-силно да се обозначат поддърветата, но при големи дървеса става много широко.

Попринцип не съм гледал кода на колегите, но само надзърнах за да открадна на dzhenko функцията makeConnection() за линиите между родител-деца и стрелките, надявам се че не е в конфликт с лиценза на кода му. :D

Поздрави!


от martin.nikolov (4535 точки)


0
Колега каква е идеята да парсваш данните, когато те вече са в JSON формат ?

от Plamen_Petkov (1255 точки)

0
Добър въпрос, останало е като излишък и съм забравил да го махна. :>

от martin.nikolov (4535 точки)