Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
dimonz80

Таким образом ребро 4->5 кандидат на схлопывание

Где мы ишем факт того, что отстутвует другой путь из 4 в 5.

Т.е. не существует маршрута, например, 4 -> 3 -> 8 -> 5 ?
16 сен 20, 16:35    [22198562]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
Понятно, что ноду только с одной входящей связью всегда можно схлопнуть с предыдущей.

Но тогда задача какая-то черезчур простая.

Что в ситуации, когда в нодах больше одной входящей связи но они относятся к непересекающимся-несвязанным подграфам (с терминологией у меня все плохо). Я так подумал, что их тоже нужно схлопывать.
16 сен 20, 16:42    [22198566]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
Мой долг в части тест-кейсов растет. Я о нем помню. И я думаю сегодня их выложу.

Пока рисую в блокноте. Вот тривиальные случаи как раз закроем.
16 сен 20, 16:47    [22198573]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
ладно, пофиг, т.з. конечно замечательное " рёбра типа (4)->(5) как на картинке." )))

в любом случае, смысл сего действия мне не очень понятен
16 сен 20, 16:47    [22198574]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
Leonid Kudryavtsev
dimonz80

Таким образом ребро 4->5 кандидат на схлопывание

Где мы ишем факт того, что отстутвует другой путь из 4 в 5.

Т.е. не существует маршрута, например, 4 -> 3 -> 8 -> 5 ?


В условии такого вроде нету.
16 сен 20, 16:47    [22198575]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно
16 сен 20, 16:50    [22198577]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
Leonid Kudryavtsev
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно


Че ты начинаешь?! Нормально же общались! Зануда.

Иногда полезно делать такие экзерсисы. Просто чтобы размяться. Если ты вертишь графы, матрицы и т.п. каждый день на работе, то мы тут все тебе безмерно завидуем, честно.
16 сен 20, 16:55    [22198590]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
dimonz80
Leonid Kudryavtsev
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно


Че ты начинаешь?! Нормально же общались! Зануда.

Иногда полезно делать такие экзерсисы. Просто чтобы размяться. Если ты вертишь графы, матрицы и т.п. каждый день на работе, то мы тут все тебе безмерно завидуем, честно.


Это как отставной полковник иногда просыпается среди ночи и начинает разбирать и собирать наградной ПМ.
16 сен 20, 17:00    [22198595]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
Беря во внимание что большинство "кодеров для бизнеса" про графы слыхали только в универах,
я-бы сказал что этот "полковник" собирает и разбирает РСЗО.

Я делаю своё суждение на основани своего уже более чем 15 летнего присуствия на этом форуме.
16 сен 20, 17:05    [22198600]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
mayton
Беря во внимание что большинство "кодеров для бизнеса" про графы слыхали только в универах,
я-бы сказал что этот "полковник" собирает и разбирает РСЗО.

Я делаю своё суждение на основани своего уже более чем 15 летнего присуствия на этом форуме.


Для многих программирование - непыльное ремесло, чтобы кормить семью, во имя 1С, всемилостивого и милосердного, аминь.
16 сен 20, 17:25    [22198620]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
dimonz80,

мне понравилось что у нас в топике появился скалист. Есть повод потом собрать ваш исходник на scala-native
https://scala-native.readthedocs.io/en/v0.3.9-docs/

и посмотреть как вырастет перформанс. Но это - потом. Сначала - самолёты.
16 сен 20, 17:33    [22198629]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
Вот основные тестовые кейсы. 8 штук.

(1) и (3) это цепочка.
(2) это цикл. Не схлопывается.
(5) и (6) это ветка. Не схлопывается.
(7) это классический случай с которого мы начали
(8) это цикл. Тоже не схлопывается.

К сообщению приложен файл. Размер - 87Kb
16 сен 20, 20:33    [22198784]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
mayton
Вот основные тестовые кейсы. 8 штук.

(1) и (3) это цепочка.
(2) это цикл. Не схлопывается.
(5) и (6) это ветка. Не схлопывается.
(7) это классический случай с которого мы начали
(8) это цикл. Тоже не схлопывается.


Случаи 5 и 6 противоречат остальным
17 сен 20, 05:23    [22198885]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
Почему?
17 сен 20, 09:41    [22198929]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
mayton
Почему?



Ну например, соединив 5 и 6 получим 7, но 5 и 6 не схлопываются, а 7 схлопывается. Как так?

И еще проблема тест кейсов в отсутствии намека на остальную часть графа.
17 сен 20, 09:46    [22198932]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
dimonz80
mayton
Почему?



Ну например, соединив 5 и 6 получим 7, но 5 и 6 не схлопываются, а 7 схлопывается. Как так?

И еще проблема тест кейсов в отсутствии намека на остальную часть графа.

Я понял ваше сомнение. Действительно - надо хотя-бы обозначить прочие вершины.
17 сен 20, 10:24    [22198958]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
dimonz80
Случаи 5 и 6 противоречат остальным

а так же 2 и 7

т.к. лично я бы подумал, что кольцо должно схлопнутся в 1-н элемент. Почему оно не должно схлопываться, мне не понятно

в 7-ом, я бы подумал, что элементы 7->4 7->6 так же должны схлопнутся (см. картинку N1)

В общем, правила схлопывания мне совершенно не понятны. А предметную область я не знаю.
17 сен 20, 11:19    [22199030]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
Leonid Kudryavtsev
dimonz80
Случаи 5 и 6 противоречат остальным

а так же 2 и 7

т.к. лично я бы подумал, что кольцо должно схлопнутся в 1-н элемент. Почему оно не должно схлопываться, мне не понятно

в 7-ом, я бы подумал, что элементы 7->4 7->6 так же должны схлопнутся (см. картинку N1)

В общем, правила схлопывания мне совершенно не понятны. А предметную область я не знаю.


Ну на картинке преобразования после одной итерации, по идее. При следующей должно схлопнуться.
17 сен 20, 11:31    [22199052]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 237
Задача, похоже, мутирует в сторону поиска паттернов в графе.
17 сен 20, 11:44    [22199065]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9882
Задача еще никуда не сдвинулась.

То майтон какие-то заумные задачи с формулировками и терминами из теор-мата, теор-вероятностей и пр. публикует. что я даже таких слов в жизни не слышал.
То "типа как на картинке." )))
17 сен 20, 13:21    [22199164]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52942
Схлопывание?
17 сен 20, 13:45    [22199187]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
Все форумы / Java Ответить