Best data structure for DFS on large graphs

[Miheer Dewaskar]

On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list at tim.thechases.com> wrote:
> 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?

I want it to be a generic Game solver.So the number of states depends
on the game.
For a simple tic-tac-toe the upper bound is 3^9 states.But for more
complex games it could be much larger.
I would like to assume that the number of states can grow arbitrarily large.

> 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.

The state just has 'state data'.The transitions are obtained by
functions analyzing the state.
So that I should not be able to identify between two same states that
have been reached by different means.

For example in the tic-tac-toe game the states can be a 3x3 box of integers

 0 -> unoccupied
 1 -> x
 2-> o

(  (2,0,1),                 o   -   x
   (1,1,0),         ->     x  x   -
   (2,0,0) )                o  -    -



-- 
Miheer Dewaskar