[R] Fast lookup in ragged array

[Seth Falcon]

Peter McMahan <peter.mcmahan at gmail.com> writes:

> Well, I hadn't ever seen RBGL before, so that's great. I've been  
> using igraph and sna mainly, but there are a few points lacking  
> between these two. RBGL solves a lot of problems for me!
>
> But I'm not sure it will solve this specific problem. Are you  
> suggesting I use RBGL to do a depth-first search of all the  
> subgraphs? For this particular depth-first search I'm not searching  
> every subgraph, but just those that are constructed from a minimal  
> cutset of the parent subgraph. At each level of the search, I have to  
> compute graph cohesion (vertex connectivity), which can take  
> considerable time. A lot of computation time is saved by only  
> searching subgraphs obtained through cutsets. So a complete search of  
> all the subgraphs won't work, but the redundancy I come across is I  
> think unavoidable.

Perhaps you will need a combination of graph/RBGL and some custom
memoization code to keep track of which subgraphs have already been
searched.

Some suggestions on that front:

Don't use a list, use an environment.  

     searchedBranched = new.env(hash=TRUE, parent=emptyenv(), size=X)

where X is an estimate of the number of branches you will search.
Using an environment implies you will need unique character names for
each subgraph.  Do you have that?  If not, you could concatenate node
names.  For a 200 node graph, that should be ok.

Hope that helps some.

+ seth

-- 
Seth Falcon | Computational Biology | Fred Hutchinson Cancer Research Center
http://bioconductor.org