Scala: Recursively building all pathes in a graph?
- by DarqMoth
Trying to build all existing paths for an udirected graph defined as a map of edges using the following algorithm:
Start: with a given vertice A
Find an edge (X.A, X.B) or (X.B, X.A), add this edge to path
Find all edges Ys fpr which either (Y.C, Y.B) or (Y.B, Y.C) is true
For each Ys: A=B, goto Start
Providing edges are defined as the following map, where keys are tuples consisting of two vertices:
val edges = Map(
("n1", "n2") -> "n1n2",
("n1", "n3") -> "n1n3",
("n3", "n4") -> "n3n4",
("n5", "n1") -> "n5n1",
("n5", "n4") -> "n5n4")
As an output I need to get a list of ALL pathes where each path is a list of adjecent edges like this:
val allPaths = List(
List(("n1", "n2") -> "n1n2"),
List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"),
List(("n5", "n1") -> "n5n1"),
List(("n5", "n4") -> "n5n4"),
List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4"))
//...
//... more pathes to go
}
Note: Edge XY = (x,y) - "xy" and YX = (y,x) - "yx" exist as one instance only, either as XY or YX
So far I have managed to implement code that duplicates edges in the path, which is wrong and I can not find the error:
object Graph2 {
type Vertice = String
type Edge = ((String, String), String)
type Path = List[((String, String), String)]
val edges = Map(
//(("v1", "v2") , "v1v2"),
(("v1", "v3") , "v1v3"),
(("v3", "v4") , "v3v4")
//(("v5", "v1") , "v5v1"),
//(("v5", "v4") , "v5v4")
)
def main(args: Array[String]): Unit = {
val processedVerticies: Map[Vertice, Vertice] = Map()
val processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)] = Map()
val path: Path = List()
println(buildPath(path, "v1", processedVerticies, processedEdges))
}
/**
* Builds path from connected by edges vertices starting from given vertice
* Input: map of edges
* Output: list of connected edges like:
List(("n1", "n2") -> "n1n2"),
List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"),
List(("n5", "n1") -> "n5n1"),
List(("n5", "n4") -> "n5n4"),
List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4"))
*/
def buildPath(path: Path,
vertice: Vertice,
processedVerticies: Map[Vertice, Vertice],
processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)]): List[Path] = {
println("V: " + vertice + " VM: " + processedVerticies + " EM: " + processedEdges)
if (!processedVerticies.contains(vertice)) {
val edges = children(vertice)
println("Edges: " + edges)
val x = edges.map(edge => {
if (!processedEdges.contains(edge._1)) {
addToPath(vertice, processedVerticies.++(Map(vertice -> vertice)), processedEdges, path, edge)
} else {
println("ALready have edge: "+edge+" Return path:"+path)
path
}
})
val y = x.toList
y
} else {
List(path)
}
}
def addToPath(
vertice: Vertice,
processedVerticies: Map[Vertice, Vertice],
processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)],
path: Path,
edge: Edge): Path = {
val newPath: Path = path ::: List(edge)
val key = edge._1
val nextVertice = neighbor(vertice, key)
val x = buildPath (newPath,
nextVertice,
processedVerticies,
processedEdges ++ (Map((vertice, nextVertice) -> (vertice, nextVertice)))
).flatten // need define buidPath type
x
}
def children(vertice: Vertice) = {
edges.filter(p => (p._1)._1 == vertice || (p._1)._2 == vertice)
}
def containsPair(x: (Vertice, Vertice), m: Map[(Vertice, Vertice), (Vertice, Vertice)]): Boolean = {
m.contains((x._1, x._2)) || m.contains((x._2, x._1))
}
def neighbor(vertice: String, key: (String, String)): String = key match {
case (`vertice`, x) => x
case (x, `vertice`) => x
}
}
Running this results in:
List(List(((v1,v3),v1v3), ((v1,v3),v1v3), ((v3,v4),v3v4)))
Why is that?
