Best data structure for DFS on large graphs

[Tim Chase]

On 07/03/12 08:39, Miheer Dewaskar wrote:
> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel <stefan_ml at behnel.de> wrote:
>>
>> Miheer Dewaskar, 03.07.2012 13:11:
>>> I am not sure,but if there are large number of states Dictionaries wont
>>> help much right?
>>
>> Dicts are fast for lookup, not for searching.
>>
> What do you mean by searching in the context of Dicts?

It took me a while to parse Stefan's post, and I *think* he means
that key-indexing (direct lookup) is fast O(1), and that by
"searching" he means something like "find all keys/values matching
property $FOO" such as between a range.

One of the important things you omit is how you define "large".  Is
this a couple thousand?  Hundreds of thousands?  Millions?

Also, what sort of information are you keeping in the state?  Just
available transitions?  Or do you want additional metadata?  If it's
just transition mappings (A->B) rather than complex objects, I'd try
using a dict first, and if it's too large, I'd reach for the
"anydbm" module to store them to disk.

-tkc