Subgraph Operations

[jpfairbanks]

I would like to kick around some ideas on supporting subgraphs.

It would be nice to have induced subgraphs accessible. If you are willing to copy out the subgraph, which is useful in some use cases, it is easy to implement. You just take a subset of integers in 1:n and iterate over the them grabbing their neighbors and renumbering everything based on scan(+, input).

For copy-free subgraphs like subarrays things are a bit more complicated.
A subtype is the way to go. If you take a subgraph as a Vector{Int} and the original graph it is a subgraph of, then you overload the basic operations like neighbors, edges, degree... to use one level of indirection.

type AbstractSubGraph <: AbstractGraph
vertices::Range
supergraph::AbstractGraph
vertexmap::AbstractArray 
inversevertexmap::AbstractArray
end

Where vertexmap maps from the subgraph index to the supergraph index and inversevertexmap maps from supergraph index to subgraph index.
So neighbors becomes something like

function neighbors(h::AbstractSubgraph, v)
    superneighbors = neighbors(h.supergraph, h.vertexmap[v])
    subneighbors = Array(Int,0)
    for u in superneighbors
        if u in h.inversevertexmap
            push!(subneighbors, h.inversevertexmap[u])
        end
    end
    return subneighbors
end

This approach leads to subgraphs which take time linear in the original graph size to use. So it would only be worth if it you had subgraphs which are almost the same size as the original graph. In this case the benefit is to avoid the space requirements of the copies. And would be useful if you had some function that required you to remove each vertex in a set and evaluate a function on the induced subgraph.

For non-induced subgraphs we could treat the property of being in the subgraph as an externally stored property like distance or edge weight and use a masking technique.

If anyone has other ideas they want to discuss just put them out there on this issue.

[sbromberger]

Copy-free subgraphs have their disadvantages, though: moving from a int range (O(1)) to a vector (O(n) access) or a set (O(logN) access, O(n) traversal) will slow down the algorithms substantially. The big gotcha with Graphs, for example, is the cost of vertex_index for non-simple graphs.

I see use cases for both types, though. The performance issues are what give me the most concern, since LightGraphs is designed to be as fast as possible.

The "copy" subgraph is expensive initially (actually, given how we structure the graphs, it should actually be fairly cost-effective, but expensive relative to everything else) and consumes more memory. What if we had a copy! that didn't do an in-place subgraph, but built the temporary subgraph and then just deleted the original one afterwards? That way you'd have up to a 2N memory hit, but it would be temporary.

Given that the graphs themselves are fairly lightweight, memory wise, it might make more sense to start with that. (Also, it's way easier. :) ) Thoughts?

[jpfairbanks]

I think that the copying based subgraph should definitely be the first step. Do you think that it will be faster to allocate an empty graph and fill it with the subgraph's edges or to copy the original and then delete edges? You have to renumber the vertices as you delete them so that everything is 1:n in the end.
My use case won't delete the original graph because I will want to take a partition of the vertex set and get all of the induced subgraphs.

[sbromberger]

I think there are tradeoffs to creating empty graphs: on the plus side, you won't have 0-degree vertices (you'd have these orphaned vertices if you just deleted edges), and graph creation can be very fast if we use the finclist vector-of-vectors for iterations. Edge removal is fairly costly.

On the downside, if your subgraph is approaching the size of a (very large) original graph, it might be more efficient to delete the edges. Also, you'd preserve the vertex mapping (vertex indices would remain the same). We could provide both functions, I guess.

[sbromberger]

PS: I can code this up, but it'll take a few days. Do you want to give it a try instead?

[jpfairbanks]

Ah you are thinking that deletions would not shift vertices down to replace
the deleted vertices.
I think those are the two cases, if you want to preserve the labeling, then
use the deletion approach you are thinking of.
If you want to compactify the labeling, then use the insertion approach,
since you have to touch every edge when relabeling anyway.

On Wed, Feb 25, 2015 at 12:41 PM Seth Bromberger notifications@github.com
wrote:

I think there are tradeoffs to creating empty graphs: on the plus side,
you won't have 0-degree vertices (you'd have these orphaned vertices if you
just deleted edges), and graph creation can be very fast if we use the
finclist vector-of-vectors for iterations. Edge removal is fairly costly.

On the downside, if your subgraph is approaching the size of a (very
large) original graph, it might be more efficient to delete the edges.
Also, you'd preserve the vertex mapping (vertex indices would remain the
same). We could provide both functions, I guess.

—
Reply to this email directly or view it on GitHub
#10 (comment)
.

[sbromberger]

Exactly: if you're not worried about preserving vertex indices, then I'd definitely advocate the "build from scratch" approach. I think it will be much faster for all but the most extreme cases.

Even if you needed to know the vertices, we could do that as well by returning a tuple (subgraph, mapping::Vector{Int}) that provided the vertex mapping from new to old.

[sbromberger]

So - do you want to take a stab at this or should I do it? (My schedule just got jammed so it might be a couple weeks.) The copy-based subgraphs should be relatively straightforward.

[jpfairbanks]

I sent pull request #18

[sbromberger]

Awesome - I think we've got it! Closing out. Thanks so much for your help!

[joseortiz3]

So painful to implement state-of-the-art algorithms when indices are not preserved. Such algorithms recursively subgraph and keep track of sets of nodes at each recursion layer.

[sbromberger]

@joseortiz3 assuming this is your post on SO, my advice is to try implementing the interface functions for a graph data structure of your choosing.

[joseortiz3]

@sbromberger I found that SimpleGraphs preserves node identity during subgraphing already, so am wondering if implementing the interface for a homebrewed graph structure would still result in LightGraphs consolidating node indices.