Резюме:
Я создал два решения как универсальные функции FP, которые обнаруживают циклы в ориентированном графе. И согласно вашему подразумеваемому предпочтению, использование раннего return для выхода из рекурсивной функции было исключено . Первый, isCyclic, просто возвращает логическое значение, как только DFS (поиск в глубину в первый раз) повторяет посещение узла. Второй, filterToJustCycles, возвращает копию входных данных Map, отфильтрованных по всем узлам, участвующим в любых / всех циклах, и возвращает пустой Map, когда циклы не найдены.
подробности:
Для следующего, пожалуйста, рассмотрим ориентированный граф, закодированный так:
val directedGraphWithCyclesA: Map[String, Set[String]] =
Map(
"A" -> Set("B", "E", "J")
, "B" -> Set("E", "F")
, "C" -> Set("I", "G")
, "D" -> Set("G", "L")
, "E" -> Set("H")
, "F" -> Set("G")
, "G" -> Set("L")
, "H" -> Set("J", "K")
, "I" -> Set("K", "L")
, "J" -> Set("B")
, "K" -> Set("B")
)
В обеих функциях ниже параметр типа N относится к любому типу «узла», который вы хотите указать. Важно, чтобы предоставленный тип "Node" был неизменным и имел стабильные реализации equals и hashCode (все они выполняются автоматически с использованием неизменяемых классов case).
Первая функция, isCyclic, по своей природе аналогична версии решения, предоставленной @ the-archetypal-paul. Предполагается, что ориентированный граф был преобразован в Map[N, Set[N]], где N - идентификатор узла в графе.
Если вам нужно узнать, как в целом преобразовать реализацию пользовательского ориентированного графа в Map[N, Set[N]], я обрисовал общее решение в конце этого ответа.
Вызов функции isCyclic как таковой:
val isCyclicResult = isCyclic(directedGraphWithCyclesA)
вернет:
`true`
Никакой дополнительной информации не предоставляется. И DFS (Поиск в глубину) прерывается при обнаружении первого повторного посещения узла.
def isCyclic[N](nsByN: Map[N, Set[N]]) : Boolean = {
def hasCycle(nAndNs: (N, Set[N]), visited: Set[N] = Set[N]()): Boolean =
if (visited.contains(nAndNs._1))
true
else
nAndNs._2.exists(
n =>
nsByN.get(n) match {
case Some(ns) =>
hasCycle((n, ns), visited + nAndNs._1)
case None =>
false
}
)
nsByN.exists(hasCycle(_))
}
Вторая функция, filterToJustCycles, использует метод сокращения набора для рекурсивной фильтрации корневых узлов без ссылок на карте. Если в предоставленном графе узлов нет циклов, то .isEmpty будет возвращено Map. Однако, если есть какие-либо циклы, все узлов, необходимых для участия в любом из циклов, возвращаются с отфильтровыванием всех других участвующих в цикле узлов.
Опять же, если вам нужно посмотреть, как в целом преобразовать реализацию пользовательского ориентированного графа в Map[N, Set[N]], я обрисовал общее решение в конце этого ответа.
Вызов функции filterToJustCycles как таковой:
val cycles = filterToJustCycles(directedGraphWithCyclesA)
вернет:
Map(E -> Set(H), J -> Set(B), B -> Set(E), H -> Set(J, K), K -> Set(B))
После этого просто создать обход по этому Map, чтобы произвести любой или все различные циклические пути через оставшиеся узлы.
def filterToJustCycles[N](nsByN: Map[N, Set[N]]): Map[N, Set[N]] = {
def recursive(nsByNRemaining: Map[N, Set[N]], referencedRootNs: Set[N] = Set[N]()): Map[N, Set[N]] = {
val (referencedRootNsNew, nsByNRemainingNew) = {
val referencedRootNsNewTemp =
nsByNRemaining.values.flatten.toSet.intersect(nsByNRemaining.keySet)
(
referencedRootNsNewTemp
, nsByNRemaining.collect {
case (t, ts) if referencedRootNsNewTemp.contains(t) && referencedRootNsNewTemp.intersect(ts.toSet).nonEmpty =>
(t, referencedRootNsNewTemp.intersect(ts.toSet))
}
)
}
if (referencedRootNsNew == referencedRootNs)
nsByNRemainingNew
else
recursive(nsByNRemainingNew, referencedRootNsNew)
}
recursive(nsByN)
}
Итак, как можно преобразовать реализацию пользовательского ориентированного графа в Map[N, Set[N]]?
По сути, «Классы Go Go Scala!»
Во-первых, давайте определим пример случая реального узла в ранее существующем ориентированном графе:
class CustomNode (
val equipmentIdAndType: String //"A387.Structure" - identity is embedded in a string and must be parsed out
, val childrenNodes: List[CustomNode] //even through Set is implied, for whatever reason this implementation used List
, val otherImplementationNoise: Option[Any] = None
)
Опять же, это всего лишь пример. Ваш может включать в себя создание подклассов, делегирование и т. Д. Цель состоит в том, чтобы получить доступ к чему-то, что сможет принести две важные вещи для этой работы:
- идентификатор узла; то есть что-то, что отличает его и делает его уникальным среди всех других узлов в одном и том же ориентированном графе
- коллекция идентификаторов непосредственных потомков определенного узла - если у определенного узла нет дочерних узлов, эта коллекция будет пустой
Далее мы определим вспомогательный объект DirectedGraph, который будет содержать инфраструктуру для преобразования:
Node: черта адаптера, которая обернет CustomNodetoMap: функция, которая возьмет List[CustomNode] и преобразует его в Map[Node, Set[Node]] (что эквивалентно нашему целевому типу Map[N, Set[N]])
Вот код:
object DirectedGraph {
trait Node[S, I] {
def source: S
def identity: I
def children: Set[I]
}
def toMap[S, I, N <: Node[S, I]](ss: List[S], transformSToN: S => N): Map[N, Set[N]] = {
val (ns, nByI) = {
val iAndNs =
ss.map(
s => {
val n =
transformSToN(s)
(n.identity, n)
}
)
(iAndNs.map(_._2), iAndNs.toMap)
}
ns.map(n => (n, n.children.map(nByI(_)))).toMap
}
}
Теперь мы должны сгенерировать фактический адаптер, CustomNodeAdapter, который обернет каждый экземпляр CustomNode.Этот адаптер использует класс case очень специфическим образом;т.е. указание двух списков параметров конструктора.Это гарантирует, что класс case соответствует Set требованию, чтобы Set член имел правильные реализации equals и hashCode.Подробнее о том, почему и как использовать класс case таким образом, см. Этот вопрос и ответ StackOverflow :
object CustomNodeAdapter extends (CustomNode => CustomNodeAdapter) {
def apply(customNode: CustomNode): CustomNodeAdapter =
new CustomNodeAdapter(fetchIdentity(customNode))(customNode) {}
def fetchIdentity(customNode: CustomNode): String =
fetchIdentity(customNode.equipmentIdAndType)
def fetchIdentity(eiat: String): String =
eiat.takeWhile(char => char.isLetter || char.isDigit)
}
abstract case class CustomNodeAdapter(identity: String)(customNode: CustomNode) extends DirectedGraph.Node[CustomNode, String] {
val children =
customNode.childrenNodes.map(CustomNodeAdapter.fetchIdentity).toSet
val source =
customNode
}
Теперь у нас есть инфраструктура.Давайте определим ориентированный граф «реального мира», состоящий из CustomNode:
val customNodeDirectedGraphWithCyclesA =
List(
new CustomNode("A.x", List("B.a", "E.a", "J.a"))
, new CustomNode("B.x", List("E.b", "F.b"))
, new CustomNode("C.x", List("I.c", "G.c"))
, new CustomNode("D.x", List("G.d", "L.d"))
, new CustomNode("E.x", List("H.e"))
, new CustomNode("F.x", List("G.f"))
, new CustomNode("G.x", List("L.g"))
, new CustomNode("H.x", List("J.h", "K.h"))
, new CustomNode("I.x", List("K.i", "L.i"))
, new CustomNode("J.x", List("B.j"))
, new CustomNode("K.x", List("B.k"))
, new CustomNode("L.x", Nil)
)
Наконец, теперь мы можем выполнить преобразование, которое выглядит следующим образом:
val transformCustomNodeDirectedGraphWithCyclesA =
DirectedGraph.toMap[CustomNode, String, CustomNodeAdapter](customNodes1, customNode => CustomNodeAdapter(customNode))
И мы можем взятьtransformCustomNodeDirectedGraphWithCyclesA, который имеет тип Map[CustomNodeAdapter,Set[CustomNodeAdapter]], и отправьте его двум исходным функциям.
Вызов функции isCyclic следующим образом:
val isCyclicResult = isCyclic(transformCustomNodeDirectedGraphWithCyclesA)
вернет:
`true`
Вызов функции filterToJustCycles как таковой:
val cycles = filterToJustCycles(transformCustomNodeDirectedGraphWithCyclesA)
вернет:
Map(
CustomNodeAdapter(B) -> Set(CustomNodeAdapter(E))
, CustomNodeAdapter(E) -> Set(CustomNodeAdapter(H))
, CustomNodeAdapter(H) -> Set(CustomNodeAdapter(J), CustomNodeAdapter(K))
, CustomNodeAdapter(J) -> Set(CustomNodeAdapter(B))
, CustomNodeAdapter(K) -> Set(CustomNodeAdapter(B))
)
И при необходимости этот Map может быть затем преобразован обратнона Map[CustomNode, List[CustomNode]]:
cycles.map {
case (customNodeAdapter, customNodeAdapterChildren) =>
(customNodeAdapter.source, customNodeAdapterChildren.toList.map(_.source))
}
Если у вас есть какие-либо вопросы, проблемы или проблемы, пожалуйста, дайте мне знать, и я рассмотрю их как можно скорее.