0 people like it.

# 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: ``` ``````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> #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 reachable nodes from every node in the graph let reachableAll g : Map<'a,Set<'a>> = let rec m = g |> Map.map (fun n _ -> lazy(Set.add n (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 |> Set.filter(fun s -> not <| Seq.exists (fun s' -> s' <> s && reachable(s').Contains s) ss) |> Set.ofSeq) let transitiveReduction g = transitiveReductionHelper (reachableAll g) g module Example = let g1 : Graph = 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>
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<'a>> (requires comparison)

Full name: Graph.TransitiveReduction.Graph.reachableAll

Builds a table of the reachable nodes from every node in the graph
val g : Map<'a,Set<'a>> (requires comparison)
val m : Map<'a,Lazy<Set<'a>>> (requires 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 add : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

val k : ('a -> Set<'a>) (requires comparison)
val e : Lazy<Set<'a>> (requires comparison)
property Lazy.Value: Set<'a>
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 ss : Set<'a> (requires comparison)
val filter : predicate:('T -> bool) -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.filter
val s : 'a (requires comparison)
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val exists : predicate:('T -> bool) -> source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.exists
val s' : 'a (requires comparison)
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 : Graph<int>

Full name: Graph.TransitiveReduction.Example.g1
Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
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'