Sunday, 2 June 2013

Another Scala code snippet for linearising a graph

This algorithm is more or less related to Topological sorting. It can be useful for computing DAG in parallel.....
  type ListMap = Map[Vertex, List[Vertex]]
  class Vertex {
    var children: List[Vertex] = List()
    def isLeaf = children.isEmpty
  }
  class Graph {
    def roots: List[Vertex] = List()
  }
  
  def lin(g: Graph): ListMap = {
    def dfs(n: Vertex):List[Vertex] = if (n.isLeaf) List() else (for(c <- n.children) yield c :: dfs(c)).flatten
    def shrink(dfsl: List[Vertex]): List[Vertex] = {
      def shrink(il: List[Vertex], ol: List[Vertex]): List[Vertex] =
        if (il.isEmpty) ol
        else if (!ol.contains(il.head)) shrink(il.tail, (ol ++ List(il.head)))
        else shrink(il.tail, ol diff List(il.head)) ::: List(il.head)
      if (dfsl.isEmpty) List() else shrink(dfsl, List())
   }
   (for(r <- g.roots) yield (r, shrink(dfs(r)))).toMap
  } 

2 comments:

Thierry Janaudy said...

From HS:

def linearize(graph: Graph) = {
def dfs(node: Node):List[Node] = if (node.children.isEmpty) List()
else (for(c <- node.children) yield c :: dfs(c)).flatten
(for(node <- graph.nodes if node.parents.isEmpty) yield (node,
node :: dfs(node).foldRight(List[Node]())(((x, list) => if(list.contains(x)) list else list.+:(x))))).toMap
}

Thierry Janaudy said...

From TJ to HS: Good, first useful use of foldRight I have seen :-)

Blog Archive