Friday, 4 May 2012

Transpose a graph

Transposing a directed graph simply reverses all of the edges and may be computed using a double fold as follows:
let invert xyzs =
  Map.fold (fun m x yzs ->
    Map.fold (fun m y z ->
      let m' = defaultArg (Map.tryFind y m) Map.empty
      Map.add y (Map.add x z m') m) m yzs) Map.empty xyzs
See the F#.NET Journal article Graph algorithms: topological sort and all-pairs shortest paths for more information.

No comments: