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

Откуда:
Сообщений: 227
Leonid Kudryavtsev
Последние сообщения читал по диагонали, но или я не правильно понимаю задачу или Ваш код выглядит слишком просто (т.е. делает что-то не то).

Не очень понимаю, какие правила для того, что бы посчитать что ноды A и B можно схлопнуть и где данная проверка в Вашем коде (scale не знаю) ?




Слегка разбавил говнокод говнокоментами
import scala.annotation.tailrec

/*  
   Делаем замену типа вот так (ребра без стрелок считать направленными слева направо)

           1        6                       1   6                          
            \      /                         \ /                         
        2 -> 4 -> 5 -> 7       ====>     2 -> 4 -> 7                                               
            /      \                         / \                         
          3         8                      3    8      


  Суть реализации - сделать два словаря: для входящих и исходящих ребер каждого из узлов
  Т.е.  4->{1,2,3}, 5->{4}, 6->{5}, 7->{5}, 8->{5} - словать входов для каждого узла
        1->{4}, 2->{4}, 3->{4}, 4->{5}, 5->{6,7,8} - словарь выходов
  
  Потом найдем кандидата на удаление: в первом словаре есть 5->{4}, во втором 4->{5}
  Таким образом ребро 4->5 кандидат на схлопывание 



  Для незнающих синтаксис Scala
  val data : Type - объявление константы (Type data)
  (Int, Int) - кортеж их двух элементов типа  Int (Tuple<Int,Int>)
  _1 - первый элемент кортежа, _2 - второй и т.п. 
  Например: 
    val tuple = ("A","B") 
    tuple._1 ==  "A" // true
    tuple._2 == "B" // true

  Array[Type] - массив элементов типа Type (Type[])
  Map[Int, Array[Int]] - Map<Int,Int[]>
  

*/

// Ориентированный граф представлен в виде множества пар чисел,
// каждая пара - (вершина от которой направлено ребро, вершина к которой направлено ребро)

// вычитаем все ребра из файла в массив типа (Int, Int), преобразуя на ходу в Int
val data: Array[(Int, Int)] = {
  scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
    .map { l =>
      val arr = l.split(",").map(_.toInt)
      arr(0) -> arr(1)
    }.toArray
}

/**
 * Рекурсивная функция удаления пар вершин, связанных единственным ребром
 *
 * @param data - граф в виде массив связей между вершинами
 * @return - граф в виде массив связей между вершинами
 */
@tailrec
def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {

  // Хэш таблица с входящими связями для каждой вершины - вершина -> массив входящих ребер
  // т.е. 4 -> {1,2,3}, 5->{4}, 6->{5}, 7->{5}, 8->{5} 
  val inputs: Map[Int, Array[Int]] = data
    .groupBy(_._2) // группируем по врешине, в которую направлено ребро, на выходе Map[Int, Array[(Int,Int)]
    .map { case (k, v) => k -> v.map(_._1) } // оставляем в занчении  только входящие узлы, т.е. приводим к  Map[Int, Array[Int]]

  // Хэш таблица с исходящими связями для каждой вершины - вершина -> массив исходящих ребер
  // Аналогично inputs, только группировка относительно вершины, из которой выходит ребро
  // т.е. 1->{4}, 2->{4}, 3->{4}, 4->{5}, 5->{6,7,8}
  val outputs: Map[Int, Array[Int]] = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

  // Пары с одним входом и одним выходом - кандидаты на схлопывание
  // в outputs ищем вершины с единственным выходным ребром, для которых есть пара в inputs тем же ребром, но уже входным
  // т.е. надо найти 5->{4} из inputs и 4->{5} из outputs
  val singleLinks: Map[Int, Int] =
    outputs
      .filter(_._2.length == 1) // ищем вершины с одним выходом (т.е. такую верщину, у ктр. длина массива ввыходов == 1)
      .filter { case (from, Array(to)) => // ищем к найденой вершиние с одним выходом пару из хэш таблицы входов, такую, чтобы выход одной вершины == вход другой 
        Array(from).toList == inputs(to).toList 
      } 
      .map { case (from, Array(to)) => from -> to } // преобразуем из Map[Int, Array[Int]] в Map[Int, Int], т.к. связаннре ребро одно и массив не нужен
  
  // singleLinks = 4->5

  // если пар для удаления нет, от делать больше нечего, возвращаем исходный граф
  if (singleLinks.isEmpty) {
    return data
  }

  // сюда будем собирать новый схлопнутый граф, Set - для перестраховки от дубляжей
  val newData = collection.mutable.HashSet[(Int, Int)]()
  
  /* 
     Теперь перебираем все ребра графа и проверяем, можно-ли их удалить,
     т.е. входит-ли данное ребро в singleLinks
     Если ребро является кандидатом на удаление, то сохраняем только вершину из которой направлено ребро
     и перевпривязываем к ней выходые ребра второй вершины
     Если ребра в singleLinks нет,  то просто переносим его в результирующий граф 
                        
  */  
  data.foreach { case (from, to) =>
    // нашли пару вершин - кандидатов на удаление (4->5)
    if (singleLinks.get(from) == Option(to)) {
      // перепривязываем выходые ребра второй вершины к первой
      // т.е. вновь образованные пары 4->6, 4->7, 4->8
      outputs.get(to).foreach { outs =>
        outs.foreach { out =>
          newData.add((from, out))
        }
      }
    } else { // иначе просто переносим ребро в результат
      // проверка, чтобы исх ребра из удаленной вершины 
      // (которые мы переприцепили к вервой) не попали в результат
      // т.е. пары 5->6, 5->7, 5->8 нам уже не нужны
      if (!singleLinks.exists { case (f, t) => (t == from) }) { 
        newData.add((from, to))
      }
    }
  }

  processGraph(newData.toArray)

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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


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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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



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

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

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



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

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

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

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

а так же 2 и 7

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

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

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

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

а так же 2 и 7

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

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

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


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

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

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

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

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