{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/364","repository_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/364/labels{/name}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/364/comments","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/364/events","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/issues/364","id":153898007,"number":364,"title":"Removing vertices in phylogenies","user":{"login":"Ward9250","id":3399309,"avatar_url":"https://avatars.githubusercontent.com/u/3399309?v=3","gravatar_id":"","url":"https://api.github.com/users/Ward9250","html_url":"https://github.com/Ward9250","followers_url":"https://api.github.com/users/Ward9250/followers","following_url":"https://api.github.com/users/Ward9250/following{/other_user}","gists_url":"https://api.github.com/users/Ward9250/gists{/gist_id}","starred_url":"https://api.github.com/users/Ward9250/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Ward9250/subscriptions","organizations_url":"https://api.github.com/users/Ward9250/orgs","repos_url":"https://api.github.com/users/Ward9250/repos","events_url":"https://api.github.com/users/Ward9250/events{/privacy}","received_events_url":"https://api.github.com/users/Ward9250/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2016-05-10T00:15:37Z","updated_at":"2016-05-10T13:03:56Z","closed_at":null,"body":"Hi,\r\n\r\nI'm making progress over at Bio.jl creating phylogenies and I've got to the point where I'd like to code function that will prune a clade (vertex with one parent and multiple (typically two, children)) from a tree. I've had a look at the rem_vertex method and understand it swaps v with n and so you have to be careful with indexing. For the phylogenies it's slightly more complex as they have an order to the vertices. The n leaves are vertices 1:n, the root being n + 1 and the internals being (n + 1) until whatever. So I'd like some advice on perhaps the best way to maintain this numerical order. The best thing I've come up with so far is as follows:\r\n\r\n```julia\r\njulia> using LightGraphs\r\n\r\njulia> g = DiGraph(9)\r\n{9, 0} directed graph\r\n\r\njulia> add_edge!(g, 6, 7)\r\nedge 6 - 7\r\n\r\njulia> add_edge!(g, 7, 1)\r\nedge 7 - 1\r\n\r\njulia> add_edge!(g, 7, 2)\r\nedge 7 - 2\r\n\r\njulia> add_edge!(g, 6, 8)\r\nedge 6 - 8\r\n\r\njulia> add_edge!(g, 8, 3)\r\nedge 8 - 3\r\n\r\njulia> add_edge!(g, 8, 9)\r\nedge 8 - 9\r\n\r\njulia> add_edge!(g, 9, 4)\r\nedge 9 - 4\r\n\r\njulia> add_edge!(g, 9, 5)\r\nedge 9 - 5\r\n\r\njulia> g\r\n{9, 8} directed graph\r\n\r\njulia> collect(edges(g))\r\n8-element Array{Pair{Int64,Int64},1}:\r\n edge 6 - 7\r\n edge 6 - 8\r\n edge 7 - 1\r\n edge 7 - 2\r\n edge 8 - 3\r\n edge 8 - 9\r\n edge 9 - 4\r\n edge 9 - 5\r\n\r\n# This creates a phylogeny with structure represented by Newick string: ((1,2)7,(3,(4,5)9)8)6;\r\n# i.e. 6 is root, 7 is internal clade parent of tips, 1 & 2, 8 is internal parent of tip 3 and another internal clade 9, which is parent of tips 4 and 5.\r\n```\r\n\r\nSay I want to prune off clade 7, (and with it 1 and 2 as they are connected). I can use `rem_vertex!(g, 7)` which yields:\r\n\r\n```julia\r\ncollect(edges(g))\r\n5-element Array{Pair{Int64,Int64},1}:\r\n edge 6 - 8\r\n edge 7 - 4\r\n edge 7 - 5\r\n edge 8 - 3\r\n edge 8 - 7\r\n```\r\n\r\nI can see that basically 7 was removed, and clade 9 renamed to 7, because it was `nv(g)` and > 7. This is a simple enough thing to account for in any indexed data. But I now have the problem that 1, and 2 are still there, they're just not connected to anything! My initial solution I can think of is to take the min of the tips (3), and since the diff is 2 to get one, minus that diff of 2 from every vertex, basically shifting the connected vertices to start from 1 again, reindexing data as I go. Is this reasonable or are there better ways?\r\n\r\nMany thanks,\r\nBen. "},"comment":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/comments/218150624","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/issues/364#issuecomment-218150624","issue_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/364","id":218150624,"user":{"login":"sbromberger","id":941359,"avatar_url":"https://avatars.githubusercontent.com/u/941359?v=3","gravatar_id":"","url":"https://api.github.com/users/sbromberger","html_url":"https://github.com/sbromberger","followers_url":"https://api.github.com/users/sbromberger/followers","following_url":"https://api.github.com/users/sbromberger/following{/other_user}","gists_url":"https://api.github.com/users/sbromberger/gists{/gist_id}","starred_url":"https://api.github.com/users/sbromberger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sbromberger/subscriptions","organizations_url":"https://api.github.com/users/sbromberger/orgs","repos_url":"https://api.github.com/users/sbromberger/repos","events_url":"https://api.github.com/users/sbromberger/events{/privacy}","received_events_url":"https://api.github.com/users/sbromberger/received_events","type":"User","site_admin":false},"created_at":"2016-05-10T13:03:56Z","updated_at":"2016-05-10T13:03:56Z","body":"In general you don't want to muck around with the internal data structures like fadjlist and badjlist. Lots of things depend on properties of those structures that, if they break or become nonconformant will cause undefined behavior in the rest of the module. "}}