{"action":"created","issue":{"url":"https://api.github.com/repos/mitchmindtree/daggy/issues/7","labels_url":"https://api.github.com/repos/mitchmindtree/daggy/issues/7/labels{/name}","comments_url":"https://api.github.com/repos/mitchmindtree/daggy/issues/7/comments","events_url":"https://api.github.com/repos/mitchmindtree/daggy/issues/7/events","html_url":"https://github.com/mitchmindtree/daggy/issues/7","id":119299938,"number":7,"title":"Use heuristic for quick accept without cycle check in `add_edge`","user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-11-28T15:04:45Z","updated_at":"2015-11-28T15:05:50Z","closed_at":null,"body":"The type invariant that the current DAG is acyclic can be used to speed up incremental checks. A full algorithm is still *O(|V| · |E|)* though.\r\n\r\nSome easy heuristics are:\r\n\r\n- is either `a` or `b` without prior edges?\r\n- is there already an edge from `a` to `b` with the same directionality?"},"comment":{"url":"https://api.github.com/repos/mitchmindtree/daggy/issues/comments/160308133","html_url":"https://github.com/mitchmindtree/daggy/issues/7#issuecomment-160308133","issue_url":"https://api.github.com/repos/mitchmindtree/daggy/issues/7","id":160308133,"user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"created_at":"2015-11-28T15:05:50Z","updated_at":"2015-11-28T15:05:50Z","body":"I saw add_child which says\r\n\r\n```\r\n    /// This is faster than using `add_node` and `add_edge`. This is because we don't have to check\r\n    /// if the graph would cycle when adding an edge to the new node, as we know it it will be the\r\n    /// only edge connected to that node.\r\n```\r\n\r\nbut that a node has no edges is something we can very easily check in add_edge too."}}