OldGraphs.jl
OldGraphs.jl copied to clipboard
JuliaAttic
Edge/vertex removal missing from API?
I know I'm probably missing something here, but it appears there is currently nosupport in any of the graph APIs to allow edge/vertex removal?
Is this intentional or not implemented yet? My desired use case is MCMC over graphs so I plan on randomly adding and removing edges sequentially. Thanks!
Yes, the graph types currently implemented in the package do not support removal yet.
It is not trivial to design a data structure where one can efficiently (e.g. in O(1)) add and remove vertices and edges.
Is the idea then to only implement edge/vertex removal on graph types where it can be done in O(1)? Or would you be amenable to PR's implementing edge/node removal on existing graph types with the caveat that it has no performance guarantees.
Towards the former, but only for efficient edge addition/removal, would a sparse adjacency matrix parameterized on the edge type with a vector of nodes be acceptable for O(1) operations?
It is possible to implement graph types (under AdjacencyList, IncidenceList or GenericGraph) with efficient removal. What we need is a list type where elements can be removed efficiently.
But those wouldn't allow O(1) for edge removal right? As a linked list still has the search cost (to find the edge to be deleted), and a tree would be O(log(n)). I would think an adjacency matrix would be the only way to do O(1) edge removal (although it is times like these I wish I had taken an algorithms class or four).
And looking through the BGL documentation, it looks as though vertex removal is O(V+E) no matter what type of out-edge list is used. Whereas edge removal is at best O(log(E/V)) for set based out-edge lists.
Apologies if this sounds naive but in the meantime (while someone constructs an optimal algorithm), can we just treat the list of edges as an array and use something simple (like Binary search)? I feel that not having a method that removes edges greatly cripples Graphs.jl. I can do a PR if there is agreement.
@tfgit: that sounds like a good stop-gap. Such a PR would be most welcome.
Hmmm I was even more naive than I thought. Binary search requires order preservation between the elements of the array and the natural numbers. This is doable with ordered pairs of integers (using, say, Cantor's Pair Function) and the letters of the alphabet, but I'm afraid this strategy does not generalize to other data types. Would a PR of the naive O(E) algorithm be accepted?
Could we perhaps implement edge removal in a way similar to graph-tool? This is the approach (referenced here):
Removing a vertex is an O(N) operation. The vertices are internally stored in a STL vector, so removing an element somewhere in the middle of the list requires the shifting of the rest of the list. Thus, fast O(1) removals are only possible either if one can guarantee that only vertices in the end of the list are removed (the ones last added to the graph), or if the relative vertex ordering is invalidated. This last behavior can be achieved by passing the option fast == True, to remove_vertex(), which causes vertex being deleted to be ‘swapped’ with the last vertex (i.e. with the largest index), which will in turn inherit the index of the vertex being deleted.
Removing an edge is an O(ks+kt) operation, where ks is the out-degree of the source vertex, and kt is the in-degree of the target vertex. This can be made faster by setting set_fast_edge_removal() to True, in which case it becomes O(1), at the expense of additional data of size O(E).