0 people like it.
Like the snippet!

Transitive Reduction of a graph

Implements a simple algorithm to compute the transitive reduction of a graph. The transitive reduction of a graph is the minimal set of edges with the same transitive closure

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68:

namespace Graph.TransitiveReduction

open System
open System.Collections
open System.Collections.Generic

/// Adjacency list representation of a graph, mapping each vertex to its successors
type Graph<'a when 'a : comparison> = Map<'a, 'a Set>

type Tree<'a when 'a : comparison> = 
    { root : 'a ; sub : Tree<'a> list }

    member this.ToSeq() =
        seq { yield this.root
              for t in this.sub do
                yield! t }

    interface IEnumerable<'a> with
        member this.GetEnumerator() : IEnumerator<'a> = 
           this.ToSeq().GetEnumerator()
        member this.GetEnumerator() : IEnumerator =
            (this.ToSeq() :> IEnumerable).GetEnumerator()

#nowarn "40"

module Graph = 
    /// Reachable nodes from the given root
    let reachableF (g: Graph<'a>) k (root:'a) = 
        match g.TryFind root with
        | None    -> Set.empty
        | Some nn -> Seq.map k nn |> Set.unionMany

    let rec fix f x = f (fix f) x

    let reachable g root = fix (reachableF g) root

    /// Builds a table of the dfs for every node in the graph
    let reachableAll g =
        let rec m = g |> Map.map (fun n _ -> lazy(reachableF g k n))
        and k   n  = m.[n].Value
        m |> Map.map(fun _ e -> e.Value)
                 
    /// The transitive reduction of a graph is the minimal set of edges with the same transitive closure
    let transitiveReductionHelper (dfss : Map<_,_>) (g:Graph<'a>) : Graph<'a> =

        let reachable n = Set.add n (dfss.[n])

        g |> Map.map(fun n ss -> 
                ss
                |> Seq.map (fun s -> 
                    if Seq.exists (fun s' -> s' <> s && reachable(s').Contains s) ss
                    then None
                     else Some s
                     )
                |> Seq.choose id
                |> Set.ofSeq)

    let transitiveReduction g = transitiveReductionHelper (reachableAll g) g

module Example =
    let g1 = Map.ofSeq <|
                [ 0, Set.ofSeq [|1;2;3|]
                  1, Set.ofSeq [|2|]
                  2, Set.ofSeq [|3|]
                  3, Set.ofSeq [| |]
                ]        

    let g1' = Graph.transitiveReduction g1

Multiple items
module Graph

from Graph.TransitiveReduction

--------------------
type Graph<'a (requires comparison)> = Map<'a,Set<'a>>

Full name: Graph.TransitiveReduction.Graph<_>

Adjacency list representation of a graph, mapping each vertex to its successors

namespace System

namespace System.Collections

namespace System.Collections.Generic

type Graph<'a (requires comparison)> = Map<'a,Set<'a>>

Full name: Graph.TransitiveReduction.Graph<_>

Adjacency list representation of a graph, mapping each vertex to its successors

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>

type Tree<'a (requires comparison)> =
  {root: 'a;
   sub: Tree<'a> list;}
  interface IEnumerable<'a>
  member ToSeq : unit -> seq<'a>

Full name: Graph.TransitiveReduction.Tree<_>

Tree.root: 'a

Tree.sub: Tree<'a> list

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val this : Tree<'a> (requires comparison)

member Tree.ToSeq : unit -> seq<'a>

Full name: Graph.TransitiveReduction.Tree`1.ToSeq

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val t : Tree<'a> (requires comparison)

Multiple items
type IEnumerable =
member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>

override Tree.GetEnumerator : unit -> IEnumerator<'a>

Full name: Graph.TransitiveReduction.Tree`1.GetEnumerator

Multiple items
type IEnumerator =
  member Current : obj
  member MoveNext : unit -> bool
  member Reset : unit -> unit

Full name: System.Collections.IEnumerator

--------------------
type IEnumerator<'T> =
  member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>

member Tree.ToSeq : unit -> seq<'a>

override Tree.GetEnumerator : unit -> IEnumerator

Full name: Graph.TransitiveReduction.Tree`1.GetEnumerator

val reachableF : g:Graph<'a> -> k:('a -> Set<'a0>) -> root:'a -> Set<'a0> (requires comparison and comparison)

Full name: Graph.TransitiveReduction.Graph.reachableF

Reachable nodes from the given root

val g : Graph<'a> (requires comparison)

val k : ('a -> Set<'a0>) (requires comparison and comparison)

val root : 'a (requires comparison)

member Map.TryFind : key:'Key -> 'Value option

union case Option.None: Option<'T>

val empty<'T (requires comparison)> : Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.empty

union case Option.Some: Value: 'T -> Option<'T>

val nn : Set<'a> (requires comparison)

module Seq

from Microsoft.FSharp.Collections

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val unionMany : sets:seq<Set<'T>> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.unionMany

val fix : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Graph.TransitiveReduction.Graph.fix

val f : (('a -> 'b) -> 'a -> 'b)

val x : 'a

val reachable : g:Graph<'a> -> root:'a -> Set<'b> (requires comparison and comparison)

Full name: Graph.TransitiveReduction.Graph.reachable

val reachableAll : g:Map<'a,Set<'a>> -> Map<'a,Set<'b>> (requires comparison and comparison)

Full name: Graph.TransitiveReduction.Graph.reachableAll

Builds a table of the dfs for every node in the graph

val g : Map<'a,Set<'a>> (requires comparison)

val m : Map<'a,Lazy<Set<'b>>> (requires comparison and comparison)

val map : mapping:('Key -> 'T -> 'U) -> table:Map<'Key,'T> -> Map<'Key,'U> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.map

val n : 'a (requires comparison)

val k : ('a -> Set<'b>) (requires comparison and comparison)

val e : Lazy<Set<'b>> (requires comparison)

property Lazy.Value: Set<'b>

val transitiveReductionHelper : dfss:Map<'a,Set<'a>> -> g:Graph<'a> -> Graph<'a> (requires comparison)

Full name: Graph.TransitiveReduction.Graph.transitiveReductionHelper

The transitive reduction of a graph is the minimal set of edges with the same transitive closure

val dfss : Map<'a,Set<'a>> (requires comparison)

val reachable : ('a -> Set<'a>) (requires comparison)

val add : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.add

val ss : Set<'a> (requires comparison)

val s : 'a (requires comparison)

val exists : predicate:('T -> bool) -> source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.exists

val s' : 'a (requires comparison)

val choose : chooser:('T -> 'U option) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.choose

val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id

val ofSeq : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofSeq

val transitiveReduction : g:Map<'a,Set<'a>> -> Graph<'a> (requires comparison)

Full name: Graph.TransitiveReduction.Graph.transitiveReduction

module Example

from Graph.TransitiveReduction

val g1 : Map<int,Set<int>>

Full name: Graph.TransitiveReduction.Example.g1

val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq

val g1' : Graph<int>

Full name: Graph.TransitiveReduction.Example.g1'

Previous Version Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/7Qj
Posted:	8 years ago
Author:	Jose Iborra
Tags:	graph , recursion