level20.lesson10.home09

Ребята, подскажите пожалуйста кто-нибудь где можно почитать что-нибудь толковое про эти графы? Что это вообще такое, и в часности применимо к java. А то вообще не понятно что в этом задании нужно сделать :(

55 комментариев

provisota
Нда, задачу я сдал, так ничего про графы и не узнав… причём тут вообще графы были?.. нутром чую что они имели отношение как раз к порядку следования данных.
SergeyKandalintsev
Если про графы еще интересно, можно почитать kpnemo.ws/ebook/2013/05/23/algoritmy-na-java-4-e-izdanie/
У этого дядьки еще есть 2 курса на курсере: www.coursera.org/course/algs4partI и www.coursera.org/course/algs4partII
Графы во втором курсе. Все примеры и задания на Java.
djfedor
Действительно а что нужно здесь делать?

Есть node — узел (кружок с цифрой), есть связанный список LinkedList. Получается надо создать объекты класса Solution с проставленными узлами как на рисунке и заполнить его list (чем заполнять в случае одного элемента?), затем все сериализовать?
jekamell
Классная задача :D
OPEOP
Решил.
Хм… чёт не понял прикол с задачей. Запутать хотите? )))
j_stud
Кто решил, подскажите, пожалуйста, надо ли создавать main и проводить десериализацию?
Nikaaner
  • Nikaaner
  • 0
  • Комментарий отредактирован 2014-05-15 01:07:48 пользователем Nikaaner
Если хочешь, то можешь и не создавать, и ничего не проводить, а решить без этого, и даже может только такое решение и предусмотрено, но в последнем не уверен.
Nikaaner
  • Nikaaner
  • +2
  • Комментарий отредактирован 2014-05-15 01:03:35 пользователем Nikaaner
Я сдал, но тоже так и не понял нужно было что-то создавать, или это прикол, и ничего не нужно создавать?
Или смысл в том, чтобы просто познакомить всех с графами, и все? :)
j_stud
Спасибо за подсказку, но как не ломаю голову пройти не могу. Может нужно использовать Externalizable?
Nikaaner
Я использовал Serializable
provisota
Я тоже использовал Serializable
AIRIZZIO
согласен, задание просто прикол какой то)
j_stud
Сдал благодаря private static final long serialVersionUID =1;
darkstone
Задача не протестирована и не понятна в описании. Добавил Serializable и serialVersionUID и всё прошло.
Явно не это нужно было донести до нас.
tanzwud
Да может быть однажды мы поймем причем графы к этой задаче)
Kverde
  • Kverde
  • 0
  • Комментарий отредактирован 2014-07-04 06:01:29 пользователем Kverde
Из статьи которая указанна в дополнительных материалах понятно причем здесь граф, и что имеется в виду.
eGarmin
Согласен, там как раз написано, почему надо использовать тот вариант сериализации, который работает, и почему второй вариант не канает
Santegra
В упор не вижу данной статьи в дополнительных материалах.
Artem
Как я понимаю, то это связь классов между собой. Если следовать этой логике, то какое бы дерево классов не было, serializable джава машины сериализует каждый класс всего один раз. Если даже рекурсия какая-то он её обойдет.
hubert , верно?
Dypemap
Ещё один способ заставить людей читать доп.литературу =)
superz600
Самая странная задача из всего курса.
IVa
  • IVa
  • 0
Мда! Хороший прикол! Кормена с перепугу начал читать :-)
timurnav
Задача так и называется «знакомство с графами», по-правильному (не пытаясь по-быстрее пройти курс, а реально разбираясь в каждой задаче), нужно было задать вопрос в гугле «сериализация графов» и почитать много (ну или хотя бы немного) про это дело… а потом только понять, насколько проста задача и решить ее ковыряя пальцем в носу, а не тупо попробовать первый пришедший вариант в голову(что скорей всего сделало большинство)… к сожалению, и я так сделал, теперь читать про графы желания особо нет, но если будет в курсе потом задача еще на графы, тогда я точно почитаю))))
Izhak
Gradus
Хорошее наглядное объяснение графов.
LyDjons
  • LyDjons
  • 0
  • Комментарий отредактирован 2015-02-26 13:40:28 пользователем LyDjons
В лекциях тоже интересное кое что можно найти ТЫЦ
pavel2107
Наверное, я когда-нибудь привыкну ставить везде serialVersionUID.
А вообще скипи читать очень полезно :)
Граф тут очень даже при чем. Скипи ведь писал, что когда не знаешь что делать, надо прекратить вымудриваться…
German_lbt
я не использовал serialVersionUID
добавил всего два слова
Lam-lam
«При сериализации связанных объектов имеет место граф сериализации. Сериализуется объект, если он содержит ссылки или массивы ссылок на сериализуемые объекты, то они сериализуются рекурсивно. При этом сериализуемые объекты помечаются, что исключает зацикливание при обходе графа.
Кроме того, для сериализуемых объектов создаются уникальные идентификаторы, которые необходимы для восстановления ссылок при десериализации. Т.е. при первой сериализации объект передается «по полной программе» и для него создается внутренний идентификатор, если алгоритм повторно «натыкается» на помеченный объект, то передается только его идентификатор.» ©

Сама статья
Overlord
Про графы и вообще структуры данных описано у Сэйджвика «Алгоритмы и данные в Java»
И да, у меня нет никакого графа по ссылке из условия задачи. Видимо, администрации надо перезалить картинку.
chekist
странное решение в два слова…
diagel
… чё за ерунда, ничего не понял! Подскажите кто нить! Сразу с наскоку сделал следующее: добавил implement Serializable, и в объявлении нового списка добавил тип содержимого Solution… результат — «Программа не компилируется на сервере», покубатурил ещё чутка — добавил private static final long serialVersionUID = 1L; — результат аналогичный! Я конечно могу реализовать методы добавления новых ссылок на другие объекты в ссылочныйСписок, НО жопой чую :) не в этом дело! Помогите пожалуйста!?
diagel
  • diagel
  • 0
  • Комментарий отредактирован 2015-07-19 10:50:12 пользователем diagel
… аааа, это сервак тупил — сволочь :))) ничего не сделал, повторил попытку и прошло блин! :))) с пятой попытки как лошара однопроцентный! Модераторы, удалите мой предыдущий комент пожалуйста! :)
Smolyanov
поставил serialVersionUID и имплиментировал Serializable, случайно отправил на проверку и… прошло)) так и не понял теперь, в чем смысл задачи был
kalenikov
Возможно, планиировали сделать нормальную задачу на графы, но так и не придумали как :)
Jinray
смеялся от души когда сдал задачу))))
С юмором разработчик, это точно.
А столько блин перекопал в инете про графы)))
arthur1729
  • arthur1729
  • +1
  • Комментарий отредактирован 2015-09-27 18:09:44 пользователем arthur1729
Я так понимаю, что в этой задачи надо было осознать что java.io.Serializable — не нарушает целостности графа, а вот java.io.Externalizable — нарушает (вся целостность графа лежит на совести разработчика! И вот тут проявляется ИССКУСТВО программирования =)) )…
molodets
а у меня задача принялась через Externalizable
Alxant
Жесть задача, не поверил что так легко и такого на изобретал, а оказалось решается в 2 строчки.
Roman_kh
В общем веселье да и только...
Я тут знаком отчасти с графами и думал, что будет какой-то механизм сложный. Почитал, подумал. Потом решил начать и сделать то, чтобы я сделал всегда, без дополнительных условий.
и все… оказалось этого достаточно :)
vetos_88
  • vetos_88
  • 0
  • Комментарий отредактирован 2016-01-31 17:09:08 пользователем vetos_88
Внимание! Смысл задачи: Прочитать как можно больше инфы про графы сериализацию и сериализацию графов!
Вообще в идеале, ИМХО, задачу нужно было решать придумав свой алгоритм сериализации списка edges.
monstric
  • monstric
  • 0
  • Комментарий отредактирован 2016-03-16 09:49:39 пользователем monstric
Судя по всему от нас хотят переписанный метод writeObject ))))
«The writeObject method (see Section 2.3, „The writeObject Method“) serializes the specified object and traverses its references to other objects in the object graph recursively to create a complete serialized representation of the graph. Within a stream, the first reference to any object results in the object being serialized or externalized and the assignment of a handle for that object. Subsequent references to that object are encoded as the handle. Using object handles preserves sharing and circular references that occur naturally in object graphs. Subsequent references to an object use only the handle allowing a very compact representation.»
docs.oracle.com/javase/8/docs/platform/serialization/spec/serial-arch.html

И если я правильно понял, то материал по этой теме в статье на которую есть ссылка в доп. материалах на javarush
Серилизация как она есть,
и касается темы серилизации объектов, в которых хранятся ссылки на другие объекты, в том числе и циклические. Т.е. в объекте А есть ссылка на объект В, а в объекте В ссылка на объект С, а объекте С ссылка на объекты А и В. )
Yurets_Y
Скажу так, от нас требуют подробно изучить мат часть и не лезть в дебри дискретной математики и теории граф. Информация есть в доп материалах и ответ достаточно прост.
Anastasia_Germanovich
ой, а мне только в радость в этом покопаться!
Yurets_Y
Могу вас обрадовать, либо огорчить. Ответ кроется в одной единственной строчке из второй части статьи по сериализации, конкретнее скажу в личку кто не найдет. Убив пол дня на изучение теории графов, и побродив по интернету где нашел безумные способы сериализации просто дописал одну строку в коде… и все(до этого правда написал кучу кода проверки по непонятным параметрам). Скажу так — на 20 уровне задачки стали явно с юмором. Решение простое, не ищите готового кода, не интересно, в статье все есть уверяю.
Joysi
и я могу Вас обрадовать, либо огорчить © :-)
Скоро у Вас в конце 20 левела будет (если уже не наступила) хорошая бонусная задача на дерево (с потомками, узлами и т.п. из мира графов ). Так что основы теории графов не повредят уж точно.
Shtramak
А коли тут почитать, то выходит что все же ресетить инпут нужно… Довольно таки интересный пример. Кстати, по сути мы все это время работаем с графами данных если так можно выразиться, когда ссылаемся на ссылки ссылочных объектов в ссылках ))) И в реальности теория графов — это необходимый инструмент в алгоритмистике, и, в принципе, хотя бы поверхностно, но узнать что это такое и с чем едят придется
novant
Да, задача называется почитай про графы, можнобыло сразу так и написать
rhasta
Ничего в нашей жизни просто так не бывает. Не прочитали сейчас. Потом столкнетесь — … и все-равно прочитаете :)
madalexfiesta
Задача на то чтобы ещё раз прочитать о сериализации )
markus
Думаю, основной смысл этой задачи содержался в первой строчке задания:
/*
Прочитать в дополнительных материалах о сериализации графов.
*/
По ссылке, при чтении описания механизма сериализации, мы видим пару предложений, имеющих непосредственное отношение к задаче:
Если бы вы создавали свой собственный механизм сериализации,
отслеживание всех присутствующих в объектах ссылок стало бы весьма нелегкой задачей.
Однако в Java никаких трудностей со ссылками нет — судя по всему,
в этот язык встроен достаточно эффективный алгоритм создания графов объектов.
V_efire
Нет слов… Смысл не ясен.
avedensky
Не читал, но смысл понял.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.