Создать матрицу смежности на карте

Question

Я знаю, что это длинный вопрос :) Я пытаюсь реализовать гамильтонов цикл в наборе данных в Scala 2.11, в рамках этого я пытаюсь сгенерировать матрицу смежности из карты значений.

Объяснение:

Клавиши от 0 до 4 - это разные города, поэтому в переменной "allRoads" ниже

0 -> Set(1, 2) Means city0 is connected to city1 and city2
1 -> Set(0, 2, 3, 4) Means City1 is connected to city0,city2,city3,city4
.
.

Мне нужно сгенерировать прил. Матрицу для E.g: Мне нужно сгенерировать 1, если город подключен, или же мне нужно сгенерировать 0, что означает

for: "0 -> Set(1, 2)", I need to generate: Map(0 -> Array(0,1,1,0,0)) 

input-

var allRoads = Map(0 -> Set(1, 2), 1 -> Set(0, 2, 3, 4), 2 -> Set(0, 1, 3, 4), 3 -> Set(2, 4, 1), 4 -> Set(2, 3, 1)) 

Мой код:

val n: Int = 5
val listOfCities = (0 to n-1).toList
var allRoads = Map(0 -> Set(1, 2), 1 -> Set(0, 2, 3, 4), 2 -> Set(0, 1, 3, 4), 3 -> Set(2, 4, 1), 4 -> Set(2, 3, 1))
var adjmat:Array[Int] = Map()

  for( i <- 0 until allRoads.size;j <- listOfCities) {
    allRoads.get(i) match {
      case Some(elem) => if (elem.contains(j)) adjmat = adjmat:+1 else adjmat = adjmat :+0
      case _ => None
    }
  }

который выводит:

output: Array[Int] = Array(0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0)

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

Map(0 -> Array(0, 1, 1, 0, 0),1 -> Array(1, 0, 1, 1, 1),2 -> Array(1, 1, 0, 1, 1),3 -> Array(0, 1, 1, 0, 1),4 -> Array(0, 1, 1, 1, 0))

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

Answer 1

Попробуйте

val cities = listOfCities.toSet
allRoads.map { case (city, roads) =>
  city -> listOfCities.map(city => if ((cities diff roads).contains(city)) 0 else 1)
}

, который выводит

Map(0 -> List(0, 1, 1, 0, 0), 1 -> List(1, 0, 1, 1, 1), 2 -> List(1, 1, 0, 1, 1), 3 -> List(0, 1, 1, 0, 1), 4 -> List(0, 1, 1, 1, 0))