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: 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)

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'