Advertisement
Guest User

Untitled

a guest
Mar 28th, 2015
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
F# 8.06 KB | None | 0 0
  1. open NUnit.Framework
  2. (*20*)
  3. type IGraph =
  4.     abstract AddEdge : int -> int -> unit
  5.     abstract RemoveEdge : int -> int -> unit
  6.     abstract HasEdge : int -> int -> bool
  7.     abstract OutByEdge : int -> int list
  8.     abstract Size : int
  9.  
  10. (*21*)
  11. type MatrixGraph(n : int) =
  12.     let size = n
  13.     let mutable matrix = Array2D.zeroCreate<bool> n n
  14.  
  15.     interface IGraph with
  16.         member g.AddEdge s t =
  17.             matrix.[s, t] <- true
  18.         member g.RemoveEdge s t =
  19.             matrix.[s, t] <- false
  20.         member g.HasEdge s t =
  21.             matrix.[s, t]
  22.         member g.OutByEdge v =
  23.             List.fold (fun s i ->
  24.                         if matrix.[v, i] then i :: s else s)
  25.                         [] [0 .. size-1]
  26.         member g.Size =
  27.             size
  28.  
  29. (*22*)
  30. type ListGraph(n : int) =
  31.     let size = n
  32.     let mutable l = Array.create<int list> n []
  33.  
  34.     interface IGraph with
  35.         member g.AddEdge s t =
  36.             l.[s] <- t :: l.[s]
  37.         member g.RemoveEdge s t =
  38.             l.[s] <- List.filter (fun x -> x <> t) l.[s]
  39.         member g.HasEdge s t =
  40.             List.exists (fun x -> x = t) l.[s]
  41.         member g.OutByEdge v =
  42.             l.[v]
  43.         member g.Size =
  44.             size
  45.  
  46. let isVertice v x =
  47.     v=x
  48.  
  49. (*23*)
  50. let fromVertice (g : IGraph) v =
  51.     let byEdgeFromSet r =
  52.         List.concat (List.map g.OutByEdge r)
  53.     let exclude exclusionPredicate list =
  54.         List.filter (fun u -> not (exclusionPredicate u)) list
  55.     let excludeAll exclusionList list =
  56.         exclude (fun u -> List.exists (isVertice u) exclusionList) list
  57.     let rec fromVerticeSet r =
  58.         let p = excludeAll r (byEdgeFromSet r)
  59.         if p = [] then r else fromVerticeSet (p @ r)
  60.     fromVerticeSet [v]
  61.  
  62. (*24*)
  63. let toVertice (g : IGraph) v =
  64.     let destReachableFrom x =
  65.         List.exists (isVertice v) (fromVertice g x)
  66.     let accumulateVertice acc x =
  67.         if destReachableFrom x then x :: acc else acc
  68.     List.fold accumulateVertice [] [0 .. g.Size-1]
  69.  
  70. (*25*)
  71. type IMarkedGraph<'T> =
  72.    inherit IGraph
  73.    abstract SetMark : int -> 'T -> unit
  74.     abstract GetMark : int -> 'T
  75.  
  76. (*26*)
  77. type MarkedGraph<'T>(graph : IGraph) =
  78.     let mutable g = graph
  79.     let mutable mx = Array.zeroCreate<'T> g.Size
  80.  
  81.    interface IMarkedGraph<'T> with
  82.         member p.AddEdge s t =
  83.             g.AddEdge s t
  84.         member p.RemoveEdge s t =
  85.             g.RemoveEdge s t
  86.         member p.HasEdge s t =
  87.             g.HasEdge s t
  88.         member p.OutByEdge v =
  89.             g.OutByEdge v
  90.         member p.Size =
  91.             g.Size
  92.         member p.SetMark v m =
  93.             mx.[v] <- m
  94.         member p.GetMark v =
  95.             mx.[v]  
  96.  
  97. let randomNetwork sz =  
  98.     let getName k =
  99.         match k with
  100.         | 0 -> "Windows"
  101.         | 1 -> "MacOS"
  102.         | 2 -> "Linux"
  103.         | _ -> ""
  104.     let g = (MarkedGraph<string*bool>(ListGraph(sz)) :> IMarkedGraph<string*bool>)
  105.     let r = System.Random()
  106.     let k = r.Next(g.Size * (g.Size - 1) / 2)
  107.     List.iter (fun i -> g.AddEdge i (i + 1); g.AddEdge (i + 1) i) [0 .. sz - 2]
  108.     let e = List.init k (fun i -> (r.Next(sz), r.Next(sz)))
  109.     List.iter (fun (s,t) -> if not (g.HasEdge s t) then g.AddEdge s t; g.AddEdge t s) e
  110.     let m = List.init sz (fun i -> (i, getName (r.Next(3))))
  111.     List.iter (fun (v,m) -> g.SetMark v (m, false)) m
  112.     g
  113.  
  114. let simulateNet (g : IMarkedGraph<string * bool>) =
  115.     let r = System.Random()
  116.     let prob s =
  117.         match s with
  118.         | "Windows" -> 0.9
  119.         | "MacOS" -> 0.4
  120.         | "Linux" -> 0.01
  121.         | _ -> 0.0
  122.     let markName m =
  123.         match m with
  124.         | true -> "Infected"
  125.         | false -> "OK"
  126.     let printNet () =
  127.         List.iter (fun i -> let (os, mark) = (g.GetMark i);
  128.                             printfn "Computer %A with %A is %A" i os (markName mark)) [0 .. g.Size-1]
  129.     let someOfInfected l =
  130.         List.fold (fun s i -> (snd (g.GetMark i)) || s) false l
  131.     let allInfected () =
  132.         List.fold (fun s i -> (snd (g.GetMark i)) && s) true [0 .. g.Size-1]
  133.     let infect v =
  134.         let n = g.GetMark v
  135.         g.SetMark v (fst n, true)
  136.     let checkVertice v =
  137.         let x = (prob (fst ( g.GetMark v)))
  138.         let d = r.NextDouble()
  139.         if (someOfInfected (g.OutByEdge v)) && (d < x) then
  140.             infect v
  141.     let rec loop x =
  142.         if allInfected() then ()
  143.         else
  144.             printfn "Step %i" (x + 1)
  145.             List.iter checkVertice [0 .. g.Size-1]
  146.             if x % 10 = 0 then
  147.                 printNet()
  148.             loop (x + 1)
  149.     infect 0
  150.     loop 0
  151.     printNet()
  152.  
  153. (*27*)
  154. type IList<'T> =
  155.    abstract Prepend : 'T -> unit
  156.     abstract Append : 'T -> unit
  157.    abstract Insert : int -> 'T -> unit
  158.     abstract RemoveFirst : unit
  159.     abstract RemoveLast : unit
  160.     abstract Remove : int -> unit
  161.     abstract Find : ('T -> bool) -> 'T option
  162.     abstract Concat : 'T IList -> unit
  163.    abstract Size : int
  164.    abstract ToArray : 'T array
  165.  
  166. (*29*)
  167. type ArrayList<'T>() =
  168.    let mutable arr = Array.zeroCreate<'T> 0
  169.     let mutable size = 0
  170.  
  171.     interface IList<'T> with
  172.        member s.Size =
  173.            size
  174.  
  175.        member s.Prepend x =
  176.            let narr = Array.zeroCreate<'T> (size + 1)
  177.             Array.blit arr 0 narr 1 size
  178.             narr.[0] <- x
  179.             arr <- narr
  180.             size <- size + 1
  181.        
  182.         member s.Append x =
  183.             let narr = Array.zeroCreate<'T> (size + 1)
  184.            Array.blit arr 0 narr 0 size
  185.            narr.[size] <- x
  186.            arr <- narr
  187.            size <- size + 1
  188.  
  189.        member s.Insert i x =
  190.            let narr = Array.zeroCreate<'T> (size + 1)
  191.             Array.blit arr 0 narr 0 i
  192.             if i < size then
  193.                 Array.blit arr i narr (i + 1) (size - i)
  194.             narr.[i] <- x
  195.             arr <- narr
  196.             size <- size + 1
  197.  
  198.         member s.RemoveFirst =
  199.             if size > 0 then
  200.                 let narr = Array.zeroCreate<'T> (size - 1)
  201.                Array.blit arr 1 narr 0 size
  202.                arr <- narr
  203.                size <- size - 1
  204.  
  205.        member s.RemoveLast =
  206.            if size > 0 then
  207.                let narr = Array.zeroCreate<'T> (size - 1)
  208.                 Array.blit arr 0 narr 0 (size - 1)
  209.                 arr <- narr
  210.                 size <- size - 1
  211.  
  212.         member s.Remove i =
  213.             if size > 0 then
  214.                 let narr = Array.zeroCreate<'T> (size - 1)
  215.                if i > 0 then
  216.                    Array.blit arr 0 narr 0 (i - 1)
  217.                Array.blit arr (i + 1) narr i (size - i - 1)
  218.                arr <- narr
  219.                size <- size - 1
  220.  
  221.        member s.Find p =
  222.            Array.foldBack (fun i s -> if (p i) then (Some i) else s) arr None
  223.  
  224.        member s.Concat arrx =
  225.            let narr = Array.zeroCreate<'T> (size + arrx.Size)
  226.             Array.blit arr 0 narr 0 size
  227.             Array.blit arrx.ToArray 0 narr size size
  228.             arr <- narr
  229.             size <- size + arrx.Size
  230.  
  231.         member s.ToArray =
  232.             arr
  233. [<TestFixture>]
  234. type TestGraph () =
  235.     let mutable g = ListGraph (10) :> IGraph
  236.     do
  237.         g.AddEdge 0 1
  238.         g.AddEdge 2 3
  239.         g.AddEdge 1 2
  240.         g.AddEdge 4 5
  241.         g.AddEdge 6 7
  242.         g.AddEdge 7 8
  243.         g.AddEdge 8 6
  244.  
  245.     [<Test>]
  246.     member t.``From vertex`` () =
  247.         let f = fromVertice g 9
  248.         Assert.AreEqual (List.sort f, [9])
  249.         let f = fromVertice g 4
  250.         Assert.AreEqual (List.sort f, [4;5])
  251.         let f = fromVertice g 0
  252.         Assert.AreEqual (List.sort f, [0;1;2;3])
  253.         let f = fromVertice g 6
  254.         Assert.AreEqual (List.sort f, [6;7;8])
  255.  
  256.     [<Test>]
  257.     member t.``To vertex`` () =
  258.         let f = toVertice g 9
  259.         Assert.AreEqual (List.sort f, [9])
  260.         let f = toVertice g 5
  261.         Assert.AreEqual (List.sort f, [4;5])
  262.         let f = toVertice g 3
  263.         Assert.AreEqual (List.sort f, [0;1;2;3])
  264.         let f = toVertice g 6
  265.         Assert.AreEqual (List.sort f, [6;7;8])
  266.              
  267. [<EntryPoint>]
  268. let main argv =
  269.     0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement