{"action":"created","comment":{"url":"https://api.github.com/repos/RoRu/FSharp/pulls/comments/26901756","id":26901756,"diff_hunk":"@@ -0,0 +1,140 @@\n+﻿// Tasks 20-25\n+// Solution for graphs\n+// by Vladimir Yumatov\n+// SPBU, group 171\n+\n+// Expected execution time: 4 h.\n+// Real time: ~5.5 h\n+\n+\n+// Task 20 General graph interface\n+type IGraph<'A> =\n+  interface\n+    // returns number of nodes\n+    abstract Size     : unit -> int\n+    // returns value by index of node\n+    abstract Val      : int  -> 'A\n+    // returns true if there is edge between two nodes\n+    abstract IsEdge   : int  -> int -> bool // \n+    // return list of nodes that are available \n+    // from this one through only one edge\n+    abstract OutNodes : int  -> int list\n+    // prints the graph\n+    abstract Print    : unit -> unit\n+  end\n+\n+// Task 21 Graph with adjacency matrix\n+type AdjMxGraph<'A> (nodes : 'A list, e : (int * int) list) = \n+  class\n+    let size = nodes.Length\n+    let edges = Array2D.create size size false\n+\n+    do \n+      for (n1, n2) in e do\n+        edges.[n1, n2] <- true\n+\n+    interface IGraph<'A> with\n+      member this.Size () = size\n+      member this.Val ind = nodes.[ind]\n+      member this.IsEdge n1 n2 = edges.[n1, n2]\n+      member this.OutNodes nd = \n+        let mutable res : int list = []\n+        for i in 0 .. size - 1  do\n+          if edges.[nd, i] then res <- res @ [i]\n+        res\n+      member this.Print () = \n+        printfn \"Nodes: %A\" nodes\n+        printfn \"Edges: %A\" edges\n+  end\n+\n+\n+// Tack 22 Graph with adjacency list\n+type AdjListGraph<'A> (nodes : 'A list, e : (int * int) list) = \n+  class\n+    let size = nodes.Length\n+    let edges = Array.create size (Array.create 0 0)\n+\n+    do \n+      for (n1, n2) in e do\n+        Array.set edges n1 (Array.append edges.[n1] [|n2|])\n+\n+    interface IGraph<'A> with\n+      member this.Size () = size\n+      member this.Val ind = nodes.[ind]\n+      member this.IsEdge n1 n2 = \n+        Array.tryFind (fun k -> k = n2) edges.[n1] = Some n2\n+      member this.OutNodes nd = Array.toList edges.[nd]\n+      member this.Print () = \n+        printfn \"Nodes: %A\" nodes\n+        printfn \"Edges: %A\" edges\n+  end\n+\n+\n+// Task 23 Returns all the nodes\n+// to which there's a way from node 'n'\n+let NodesFrom (gr : IGraph<'A>) n = \n+  let s = gr.Size()\n+  let visited = Array.create s false\n+  let rec dfs n' = \n+    if not(visited.[n']) then\n+      visited.[n'] <- true\n+      for i in (gr.OutNodes n') do\n+        dfs i\n+    else ()\n+  dfs n\n+  (List.filter (Array.get visited) [0..s-1]).Tail\n+\n+\n+// Task 24 Returns all the nodes \n+// from which there's a way to node 'n'\n+let NodesTo (gr : IGraph<'A>) n = \n+  let s = gr.Size()\n+  let find a =   \n+    let visited = Array.create s false\n+    let rec dfs nd =\n+      if nd = n then\n+        true\n+      elif not(visited.[nd]) then\n+        visited.[nd] <- true\n+        List.fold (fun res nd -> res || (dfs nd)) false (gr.OutNodes nd)\n+      else false\n+    dfs a\n+  List.filter find [0..s-1]","path":"graph/Program.fs","position":102,"original_position":102,"commit_id":"4c75c982a5b0ec9dd5b94e8a401a419d07a4d349","original_commit_id":"4c75c982a5b0ec9dd5b94e8a401a419d07a4d349","user":{"login":"anlun","id":711192,"avatar_url":"https://avatars.githubusercontent.com/u/711192?v=3","gravatar_id":"","url":"https://api.github.com/users/anlun","html_url":"https://github.com/anlun","followers_url":"https://api.github.com/users/anlun/followers","following_url":"https://api.github.com/users/anlun/following{/other_user}","gists_url":"https://api.github.com/users/anlun/gists{/gist_id}","starred_url":"https://api.github.com/users/anlun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/anlun/subscriptions","organizations_url":"https://api.github.com/users/anlun/orgs","repos_url":"https://api.github.com/users/anlun/repos","events_url":"https://api.github.com/users/anlun/events{/privacy}","received_events_url":"https://api.github.com/users/anlun/received_events","type":"User","site_admin":false},"body":"Как-то очень сложно. Можно просто сделать обход по обратным ребрам.\r\n*Завести функцию InNodes*","created_at":"2015-03-22T10:59:20Z","updated_at":"2015-03-22T10:59:20Z","html_url":"https://github.com/RoRu/FSharp/pull/2#discussion_r26901756","pull_request_url":"https://api.github.com/repos/RoRu/FSharp/pulls/2","_links":{"self":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/comments/26901756"},"html":{"href":"https://github.com/RoRu/FSharp/pull/2#discussion_r26901756"},"pull_request":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/2"}}},"pull_request":{"url":"https://api.github.com/repos/RoRu/FSharp/pulls/2","id":31681257,"html_url":"https://github.com/RoRu/FSharp/pull/2","diff_url":"https://github.com/RoRu/FSharp/pull/2.diff","patch_url":"https://github.com/RoRu/FSharp/pull/2.patch","issue_url":"https://api.github.com/repos/RoRu/FSharp/issues/2","number":2,"state":"open","locked":false,"title":"Выполнено домашнее задание №3 (от 16.03)","user":{"login":"RoRu","id":2317358,"avatar_url":"https://avatars.githubusercontent.com/u/2317358?v=3","gravatar_id":"","url":"https://api.github.com/users/RoRu","html_url":"https://github.com/RoRu","followers_url":"https://api.github.com/users/RoRu/followers","following_url":"https://api.github.com/users/RoRu/following{/other_user}","gists_url":"https://api.github.com/users/RoRu/gists{/gist_id}","starred_url":"https://api.github.com/users/RoRu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoRu/subscriptions","organizations_url":"https://api.github.com/users/RoRu/orgs","repos_url":"https://api.github.com/users/RoRu/repos","events_url":"https://api.github.com/users/RoRu/events{/privacy}","received_events_url":"https://api.github.com/users/RoRu/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-03-22T01:26:11Z","updated_at":"2015-03-22T10:59:20Z","closed_at":null,"merged_at":null,"merge_commit_sha":"2b2570b0eb651a5dc8df8fa99db0c7dad4c75c09","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/RoRu/FSharp/pulls/2/commits","review_comments_url":"https://api.github.com/repos/RoRu/FSharp/pulls/2/comments","review_comment_url":"https://api.github.com/repos/RoRu/FSharp/pulls/comments{/number}","comments_url":"https://api.github.com/repos/RoRu/FSharp/issues/2/comments","statuses_url":"https://api.github.com/repos/RoRu/FSharp/statuses/4c75c982a5b0ec9dd5b94e8a401a419d07a4d349","head":{"label":"RoRu:hw03","ref":"hw03","sha":"4c75c982a5b0ec9dd5b94e8a401a419d07a4d349","user":{"login":"RoRu","id":2317358,"avatar_url":"https://avatars.githubusercontent.com/u/2317358?v=3","gravatar_id":"","url":"https://api.github.com/users/RoRu","html_url":"https://github.com/RoRu","followers_url":"https://api.github.com/users/RoRu/followers","following_url":"https://api.github.com/users/RoRu/following{/other_user}","gists_url":"https://api.github.com/users/RoRu/gists{/gist_id}","starred_url":"https://api.github.com/users/RoRu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoRu/subscriptions","organizations_url":"https://api.github.com/users/RoRu/orgs","repos_url":"https://api.github.com/users/RoRu/repos","events_url":"https://api.github.com/users/RoRu/events{/privacy}","received_events_url":"https://api.github.com/users/RoRu/received_events","type":"User","site_admin":false},"repo":{"id":30987621,"name":"FSharp","full_name":"RoRu/FSharp","owner":{"login":"RoRu","id":2317358,"avatar_url":"https://avatars.githubusercontent.com/u/2317358?v=3","gravatar_id":"","url":"https://api.github.com/users/RoRu","html_url":"https://github.com/RoRu","followers_url":"https://api.github.com/users/RoRu/followers","following_url":"https://api.github.com/users/RoRu/following{/other_user}","gists_url":"https://api.github.com/users/RoRu/gists{/gist_id}","starred_url":"https://api.github.com/users/RoRu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoRu/subscriptions","organizations_url":"https://api.github.com/users/RoRu/orgs","repos_url":"https://api.github.com/users/RoRu/repos","events_url":"https://api.github.com/users/RoRu/events{/privacy}","received_events_url":"https://api.github.com/users/RoRu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/RoRu/FSharp","description":"Learning F# in 2nd semester","fork":false,"url":"https://api.github.com/repos/RoRu/FSharp","forks_url":"https://api.github.com/repos/RoRu/FSharp/forks","keys_url":"https://api.github.com/repos/RoRu/FSharp/keys{/key_id}","collaborators_url":"https://api.github.com/repos/RoRu/FSharp/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/RoRu/FSharp/teams","hooks_url":"https://api.github.com/repos/RoRu/FSharp/hooks","issue_events_url":"https://api.github.com/repos/RoRu/FSharp/issues/events{/number}","events_url":"https://api.github.com/repos/RoRu/FSharp/events","assignees_url":"https://api.github.com/repos/RoRu/FSharp/assignees{/user}","branches_url":"https://api.github.com/repos/RoRu/FSharp/branches{/branch}","tags_url":"https://api.github.com/repos/RoRu/FSharp/tags","blobs_url":"https://api.github.com/repos/RoRu/FSharp/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/RoRu/FSharp/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/RoRu/FSharp/git/refs{/sha}","trees_url":"https://api.github.com/repos/RoRu/FSharp/git/trees{/sha}","statuses_url":"https://api.github.com/repos/RoRu/FSharp/statuses/{sha}","languages_url":"https://api.github.com/repos/RoRu/FSharp/languages","stargazers_url":"https://api.github.com/repos/RoRu/FSharp/stargazers","contributors_url":"https://api.github.com/repos/RoRu/FSharp/contributors","subscribers_url":"https://api.github.com/repos/RoRu/FSharp/subscribers","subscription_url":"https://api.github.com/repos/RoRu/FSharp/subscription","commits_url":"https://api.github.com/repos/RoRu/FSharp/commits{/sha}","git_commits_url":"https://api.github.com/repos/RoRu/FSharp/git/commits{/sha}","comments_url":"https://api.github.com/repos/RoRu/FSharp/comments{/number}","issue_comment_url":"https://api.github.com/repos/RoRu/FSharp/issues/comments{/number}","contents_url":"https://api.github.com/repos/RoRu/FSharp/contents/{+path}","compare_url":"https://api.github.com/repos/RoRu/FSharp/compare/{base}...{head}","merges_url":"https://api.github.com/repos/RoRu/FSharp/merges","archive_url":"https://api.github.com/repos/RoRu/FSharp/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/RoRu/FSharp/downloads","issues_url":"https://api.github.com/repos/RoRu/FSharp/issues{/number}","pulls_url":"https://api.github.com/repos/RoRu/FSharp/pulls{/number}","milestones_url":"https://api.github.com/repos/RoRu/FSharp/milestones{/number}","notifications_url":"https://api.github.com/repos/RoRu/FSharp/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/RoRu/FSharp/labels{/name}","releases_url":"https://api.github.com/repos/RoRu/FSharp/releases{/id}","created_at":"2015-02-18T21:21:05Z","updated_at":"2015-03-04T19:44:23Z","pushed_at":"2015-03-22T01:26:11Z","git_url":"git://github.com/RoRu/FSharp.git","ssh_url":"git@github.com:RoRu/FSharp.git","clone_url":"https://github.com/RoRu/FSharp.git","svn_url":"https://github.com/RoRu/FSharp","homepage":null,"size":212,"stargazers_count":0,"watchers_count":0,"language":"F#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"RoRu:hw02","ref":"hw02","sha":"34550d9f2492b3c30dc18e8e621e10e82b70c187","user":{"login":"RoRu","id":2317358,"avatar_url":"https://avatars.githubusercontent.com/u/2317358?v=3","gravatar_id":"","url":"https://api.github.com/users/RoRu","html_url":"https://github.com/RoRu","followers_url":"https://api.github.com/users/RoRu/followers","following_url":"https://api.github.com/users/RoRu/following{/other_user}","gists_url":"https://api.github.com/users/RoRu/gists{/gist_id}","starred_url":"https://api.github.com/users/RoRu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoRu/subscriptions","organizations_url":"https://api.github.com/users/RoRu/orgs","repos_url":"https://api.github.com/users/RoRu/repos","events_url":"https://api.github.com/users/RoRu/events{/privacy}","received_events_url":"https://api.github.com/users/RoRu/received_events","type":"User","site_admin":false},"repo":{"id":30987621,"name":"FSharp","full_name":"RoRu/FSharp","owner":{"login":"RoRu","id":2317358,"avatar_url":"https://avatars.githubusercontent.com/u/2317358?v=3","gravatar_id":"","url":"https://api.github.com/users/RoRu","html_url":"https://github.com/RoRu","followers_url":"https://api.github.com/users/RoRu/followers","following_url":"https://api.github.com/users/RoRu/following{/other_user}","gists_url":"https://api.github.com/users/RoRu/gists{/gist_id}","starred_url":"https://api.github.com/users/RoRu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoRu/subscriptions","organizations_url":"https://api.github.com/users/RoRu/orgs","repos_url":"https://api.github.com/users/RoRu/repos","events_url":"https://api.github.com/users/RoRu/events{/privacy}","received_events_url":"https://api.github.com/users/RoRu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/RoRu/FSharp","description":"Learning F# in 2nd semester","fork":false,"url":"https://api.github.com/repos/RoRu/FSharp","forks_url":"https://api.github.com/repos/RoRu/FSharp/forks","keys_url":"https://api.github.com/repos/RoRu/FSharp/keys{/key_id}","collaborators_url":"https://api.github.com/repos/RoRu/FSharp/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/RoRu/FSharp/teams","hooks_url":"https://api.github.com/repos/RoRu/FSharp/hooks","issue_events_url":"https://api.github.com/repos/RoRu/FSharp/issues/events{/number}","events_url":"https://api.github.com/repos/RoRu/FSharp/events","assignees_url":"https://api.github.com/repos/RoRu/FSharp/assignees{/user}","branches_url":"https://api.github.com/repos/RoRu/FSharp/branches{/branch}","tags_url":"https://api.github.com/repos/RoRu/FSharp/tags","blobs_url":"https://api.github.com/repos/RoRu/FSharp/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/RoRu/FSharp/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/RoRu/FSharp/git/refs{/sha}","trees_url":"https://api.github.com/repos/RoRu/FSharp/git/trees{/sha}","statuses_url":"https://api.github.com/repos/RoRu/FSharp/statuses/{sha}","languages_url":"https://api.github.com/repos/RoRu/FSharp/languages","stargazers_url":"https://api.github.com/repos/RoRu/FSharp/stargazers","contributors_url":"https://api.github.com/repos/RoRu/FSharp/contributors","subscribers_url":"https://api.github.com/repos/RoRu/FSharp/subscribers","subscription_url":"https://api.github.com/repos/RoRu/FSharp/subscription","commits_url":"https://api.github.com/repos/RoRu/FSharp/commits{/sha}","git_commits_url":"https://api.github.com/repos/RoRu/FSharp/git/commits{/sha}","comments_url":"https://api.github.com/repos/RoRu/FSharp/comments{/number}","issue_comment_url":"https://api.github.com/repos/RoRu/FSharp/issues/comments{/number}","contents_url":"https://api.github.com/repos/RoRu/FSharp/contents/{+path}","compare_url":"https://api.github.com/repos/RoRu/FSharp/compare/{base}...{head}","merges_url":"https://api.github.com/repos/RoRu/FSharp/merges","archive_url":"https://api.github.com/repos/RoRu/FSharp/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/RoRu/FSharp/downloads","issues_url":"https://api.github.com/repos/RoRu/FSharp/issues{/number}","pulls_url":"https://api.github.com/repos/RoRu/FSharp/pulls{/number}","milestones_url":"https://api.github.com/repos/RoRu/FSharp/milestones{/number}","notifications_url":"https://api.github.com/repos/RoRu/FSharp/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/RoRu/FSharp/labels{/name}","releases_url":"https://api.github.com/repos/RoRu/FSharp/releases{/id}","created_at":"2015-02-18T21:21:05Z","updated_at":"2015-03-04T19:44:23Z","pushed_at":"2015-03-22T01:26:11Z","git_url":"git://github.com/RoRu/FSharp.git","ssh_url":"git@github.com:RoRu/FSharp.git","clone_url":"https://github.com/RoRu/FSharp.git","svn_url":"https://github.com/RoRu/FSharp","homepage":null,"size":212,"stargazers_count":0,"watchers_count":0,"language":"F#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/2"},"html":{"href":"https://github.com/RoRu/FSharp/pull/2"},"issue":{"href":"https://api.github.com/repos/RoRu/FSharp/issues/2"},"comments":{"href":"https://api.github.com/repos/RoRu/FSharp/issues/2/comments"},"review_comments":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/2/comments"},"review_comment":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/RoRu/FSharp/pulls/2/commits"},"statuses":{"href":"https://api.github.com/repos/RoRu/FSharp/statuses/4c75c982a5b0ec9dd5b94e8a401a419d07a4d349"}}}}