breadth first search

[News]

I am new in using Python

Anyone know how to implement breadth first search using Python? Can Python
create list dynamically, I want to implement a program which will read data
from a file and store each line into a list, is this possible?

Please send mail to me at nickyncy@yahoo. com.hk or reply this mail

Thanks a lot!

[Chris McDonough]

Re: breadth first search

News wrote:[color=blue]
> I am new in using Python
>
> Anyone know how to implement breadth first search using Python?[/color]

Breadth-first search of what? It depends what kind of tree you're
searching, but here's a page with a few implementations :

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/231503

Can Python[color=blue]
> create list dynamically, I want to implement a program which will read data
> from a file and store each line into a list, is this possible?[/color]

L = []
[L.append(line) for line in (open('filename .txt')]

- C

[Peter Otten]

Re: breadth first search

Chris McDonough wrote:
[color=blue][color=green]
>> Can Python
>> create list dynamically, I want to implement a program which will read
>> data from a file and store each line into a list, is this possible?[/color]
>
> L = []
> [L.append(line) for line in (open('filename .txt')][/color]

Why would you create two lists, one filled only with None entries just to
throw it away immediately? Don't use list comprehensions just because you
can.

Here are two sane approaches:

lines = open(filename). readlines()
lines = list(open(filen ame)) # a bit more generic

Finally, if you want to strip off the trailing newlines, a list
comprehension is in order:

lines = [line[:-1] for line in open(filename, "U")]

Peter

[mrmakent@cox.net]

Re: breadth first search

Chris McDonough wrote:
[color=blue]
> L = []
> [L.append(line) for line in (open('filename .txt')][/color]

Ouch.

Did you perhaps mean:

L = [ line for line in open('filename. txt') ]

Or, with better error handling:

try:
f = open('filename. txt')
except IOError:
# handle error here
else:
L = [ line for line in f ]

[Tim Chase]

Re: breadth first search

> Anyone know how to implement breadth first search using Python?

Yes. Granted, for more details, you'd have to describe the data
structure you're trying to navigate breadth-first.
[color=blue]
> Can Python create list dynamically[/color]

Is Perl write-only?
Does Lisp use too many parens?
Of course! :)

Not only can Python create lists dynamically, but it's one of
Python's strong points.

x = []
x.append(42)
x.append("hello ")
h = x.pop()
ft = x.pop()
[color=blue]
> I want to implement a program which will read data
> from a file and store each line into a list, is this possible?[/color]

x = [line[:-1] for line in open("file.txt" , "r").readlines( )]

will assign the contents of the file "file.txt" to the list "x",
making x[0] the first line in the file and x[-1] is the last line
in the file.

If you want to make other use of the file, you can open a file
object first:

fileObject = open("file.txt" , "r")
x = [line[:-1] for line in fileObject.read lines()]
# use fileObject elsehow here
fileObject.clos e()

The convention of using the "line[:-1]" strips off the newline at
the end of each line. Otherwise, you can just use "line" instead
of "line[:-1]"

-tkc

[Scott David Daniels]

Re: breadth first search

Chris McDonough wrote:[color=blue]
> News wrote:
>... Can Python[color=green]
>> create list dynamically, I want to implement a program which will read
>> data
>> from a file and store each line into a list, is this possible?[/color]
>
> L = []
> [L.append(line) for line in (open('filename .txt')]
>
> - C[/color]
Woops, crossed wires there:
after:
somefile = open('filename. txt')

You can do:
L = somefile.readli nes()
or
L = [line for line in somefile]
or
L = []
for line for line in somefile:
L.append(line)
to put all lines of somefile into L,

but
L = []
K = [L.append(line) for line in somefile]
builds a list K that has a None for each line in
somefile, while filling up L with the lines as a side-effect.
It is a style to avoid. Dropping the "K = " part simply says
"build the list of Nones and then discard it." -- not good style.

Also, it is good style to then call somefile.close( ) after
you are done with the file.

--Scott David Daniels
scott.daniels@a cm.org

[Chris McDonough]

Re: breadth first search

Peter Otten wrote:[color=blue]
> Chris McDonough wrote:
>[color=green][color=darkred]
>>> Can Python
>>> create list dynamically, I want to implement a program which will read
>>> data from a file and store each line into a list, is this possible?[/color]
>> L = []
>> [L.append(line) for line in (open('filename .txt')][/color]
>
> Why would you create two lists, one filled only with None entries just to
> throw it away immediately? Don't use list comprehensions just because you
> can.[/color]

Yes, of course. Thank you. I didn't mean to offend your sensibilities.
I'm not retarded *every* day, just today. ;-)

- C

[Peter Otten]

Re: breadth first search

Chris McDonough wrote:
[color=blue]
> I didn't mean to offend your sensibilities.[/color]

Me neither :-)

Peter

[Tim Chase]

Re: breadth first search

> Thanks for your reply and the structure of the file structure going to be[color=blue]
> read is
>
> <total number of nodes>
> <first node><second node><distance from first node to second node>
> ...
> <end of file represented by -1>
>
> The aims is to find out the shortest path(s) for the leaf node(s)
>
> Example:
> 9
> 0 1 1
> 0 4 2
> 1 2 3
> 1 3 4
> 4 3 2
> 4 5 1
> 4 8 2
> 5 6 2
> 5 7 2
> -1
>
> Output:
> Possible solutions:
> Path=0,1,2 length=4
> Path=0,4,3 length=4[/color]

Well, I notice several items here:

1) the number of records is obvious, as you have newlines
2) the end-of-file is obvious to Python
3) you don't explicitly spell out which nodes are availble
leaf-nodes

To build a tree like your data provides, you might have some code
like

data = open("data.txt" ,"r")
lines = [line[:-1] for line in data.readlines( )[1:-1]]
data.close()
graph = {}
for line in lines:
a,b,weight = line.split(" ",2)
weight = int(weight)
if a in graph:
graph[a][b] =(weight)
else:
graph[a] = {b:weight}

print repr(graph)

You can then navigate this graph/tree. Starting at the root node:

root = graph("0")

root now contains a dictionary. The keys in this dictionary
specify which nodes can be reached from the current location, and
the values of the dictionary represent the weight/cost associated
with traversing to this node.

You can then do a breadth-first search of this data structure
just as you would in any other language. It doesn't look like it
would be a straight-forward breadth-first search, as it looks
like you want to take the weight into account as well as the
number of steps from the root.

-tkc

PS: you should CC the list when you reply, as I certainly don't
have all the answers, and there are others on the mailing list
that can point out better ways to do things, have other ideas, or
be there more predictable than I am (otherwise, you may mail
something and I might not get it for a week)

[Charles Krug]

Re: breadth first search

On 2006-02-08, News <nickyncy@yahoo .com.hk> wrote:[color=blue]
> I am new in using Python
>
> Anyone know how to implement breadth first search using Python? Can Python
> create list dynamically, I want to implement a program which will read data
> from a file and store each line into a list, is this possible?
>
> Please send mail to me at nickyncy@yahoo. com.hk or reply this mail
>
> Thanks a lot!
>[/color]

Yes. List has methods that support a stack, in case you find it useful
in this context.

Yes. List has methods that allow dynamic creation, such as might be
useful when implementing a stack, in case you find it useful in this
context.

And Yes. File has methods that will populate a list from a file.
Examples are in the tutorials.

You're welcome.

You can find numerous examples of the breadth-first algorithm on the
web. You can then take the individual steps and translate them into
Python. You'll likely find one or two sticking points, but the
implementation is straightforward from pseudocode or from a GOOD
statement of the algorithm.