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:

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<int> 
             = 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)

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

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'

Previous Version Raw view Test code New version

More information

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