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

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, это зависит от вашего определения того, что «лучшие» средства. Я бы рекомендовал не реализовывать lib самостоятельно и использовать scala-graph, который, по-видимому, подходит для ваших нужд (неизменяемые графики).

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

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

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

Посмотрите на исходный код scala-graph для вдохновения.