Неизменяемые графоподобные структуры в Scala

Question

Добрый день! Я пытаюсь построить неизменный граф в Scala 2.9.1. Это дано мне с Seq[BO], где BO может представлять один узел в графе, и BO.attr_bo: Seq[String], который представляет ребра для других узлов, заданных именем строки. И мне нужно построить «разрешенный» граф, представленный BO with ResolvedBO Возможную реализацию вы можете увидеть здесь:

trait BO {
  def name: String
  def attr_bo: Seq[String]
}

trait ResolvedBO {
  x: BO =>
  val uni: Universe
  lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))
}

class S_BO(val name: String, val attr_bo: Seq[String]) extends BO

class Universe(list: Seq[BO]) {
  val m_list: Map[String, BO] = list.map(x => (x.name, x))(collection.breakOut)
  val m_list_r: Map[String, BO with ResolvedBO] = ...???
}

val x: Uni = new Uni(Seq(new S_BO("a", Seq("b", "c")), new S_BO("b", Seq("a", "c")), new S_BO("c", Seq("a", "b"))))

где class Universe представляет график вообще (он также может быть отключен) Также, если это важно, я могу ограничить график без циклов.

Итак, мои основные вопросы:

1. Поскольку узлы (trait BO) могут быть довольно сложными объектами и могут быть реализованы с несколькими подтипами, каков наилучший способ реализации «разрешенных узлов» - то есть узлов с прямыми ссылками на другие узлы? (BO with ResolvedBO).
2. Если наилучшим способом является разрешение узлов самостоятельно (lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_)) в trait ResolvedBO), как я могу инициализировать ссылку на граф (val uni: Universe) в trait ResolvedBO?
3. Вообще, как лучше всего работать с графоподобными структурами в Scala?

спасибо

Answer 1

Для пункта 3 это зависит от вашего определения того, что означает «лучший». Я бы порекомендовал не реализовывать библиотеку самостоятельно и использовать scala-graph , который, кажется, соответствует вашим потребностям (неизменяемые графики).

Если вы действительно настаиваете на том, чтобы написать свою собственную библиотеку графов (это хороший способ улучшить свои знания в Scala), попробуйте избегать графа объектов (используя ссылки для представления связей). Скорее перейдите на класс Graph с общими операциями, такими как: myGraph.neighborsOf( myVertex ).

Хорошим представлением (легко реализуемым, но медленным для огромных графов) является представление графа в виде набора ребер. Чтобы добавить новое ребро, вы просто добавляете новый объект в набор. Чтобы получить набор всех вершин, вы просто сгладите набор ребер. Чтобы получить соседей вершины, вы выполняете итерации по всем ребрам и т. Д.

Более быстрое решение состоит в том, чтобы использовать более сложное представление, например Map, где ключи - это вершины, а значения - множество соседей.

Взгляните на исходный код скала-графика для вдохновения.