Can anyone help me with this problem?
Find all possible non-circular paths between cities starting from a
given city. The possible end of the path is one of the cities from
which we can go anywhere (here Madrid and Ankara).
For example: All possible paths for London:
London - Paris - Madrid
London - Paris - Vienna - Ankara
London - Rome - Vienna - Ankara
(setf (get 'New_York 'nextcity) '(London Rome)
(get 'London 'nextcity) '(Paris Rome)
(get 'Paris 'nextcity) '(Madrid Vienna)
(get 'Madrid 'nextcity) '()
(get 'Rome 'nextcity) '(Vienna)
(get 'Vienna 'nextcity) '(Ankara)
(get 'Ankara 'nextcity) '())
Thanks,
Nick
On Mar 1, 9:34 pm, ·········@gmail.com wrote:
> Find all possible non-circular paths between cities starting from a
> given city.
(defun paths (city)
(labels
((pathlist (city old-path)
(if (find city old-path)
(list old-path)
(let ((new-path (cons city old-path))
(next-cities (get city 'next-cities)))
(if (not next-cities)
(list new-path)
(apply #'nconc
(mapcar (lambda (c)
(pathlist c new-path))
next-cities)))))))
(and city
(mapcar #'reverse (pathlist city '())))))
-------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
William James <·········@yahoo.com> writes:
> On Mar 2, 1:08 am, danb <·········@gmail.com> wrote:
>> On Mar 1, 9:34 pm, ·········@gmail.com wrote:
>>
>> > Find all possible non-circular paths between cities starting from a
>> > given city.
>>
>> (defun paths (city)
>> (labels
>> ((pathlist (city old-path)
>> (if (find city old-path)
>> (list old-path)
>> (let ((new-path (cons city old-path))
>> (next-cities (get city 'next-cities)))
>> (if (not next-cities)
>> (list new-path)
>> (apply #'nconc
>> (mapcar (lambda (c)
>> (pathlist c new-path))
>> next-cities)))))))
>> (and city
>> (mapcar #'reverse (pathlist city '())))))
>
> Perhaps an Arc aficionado can produce a shorter program.
I'm sure they will.
A worse problem that the program is buggy.
Given a graph
A---B---C
and starting at A, it will find the path ABC but not the path AB (or
the path A).
Also, its use of "find" to search the current path and apply-nconc to
combine sets of paths guarantees that it wil be slow for larger
graphs.
Sven-Olof
On Mar 2, 6:33 am, ········@localhost.localdomain (Sven-Olof Nystrom)
wrote:
> William James <·········@yahoo.com> writes:
> > On Mar 2, 1:08 am, danb <·········@gmail.com> wrote:
> >> On Mar 1, 9:34 pm, ·········@gmail.com wrote:
>
> >> > Find all possible non-circular paths between cities starting from a
> >> > given city.
>
> >> (defun paths (city)
> >> (labels
> >> ((pathlist (city old-path)
> >> (if (find city old-path)
> >> (list old-path)
> >> (let ((new-path (cons city old-path))
> >> (next-cities (get city 'next-cities)))
> >> (if (not next-cities)
> >> (list new-path)
> >> (apply #'nconc
> >> (mapcar (lambda (c)
> >> (pathlist c new-path))
> >> next-cities)))))))
> >> (and city
> >> (mapcar #'reverse (pathlist city '())))))
>
> > Perhaps an Arc aficionado can produce a shorter program.
>
> I'm sure they will.
>
> A worse problem that the program is buggy.
>
> Given a graph
>
> A---B---C
>
> and starting at A, it will find the path ABC but not the path AB (or
> the path A).
The example the original poster gave makes the problem seem
a lot more trivial than the one you are thinking about.
He seems to want only the paths that terminate at Madrid or
Ankara. And the cities seem to be connected by one-way
roads.
# Ruby
$links = {} # A hash-table (associative array).
"
(get 'New_York 'nextcity) '(London Rome)
(get 'London 'nextcity) '(Paris Rome)
(get 'Paris 'nextcity) '(Madrid Vienna)
(get 'Madrid 'nextcity) '()
(get 'Rome 'nextcity) '(Vienna)
(get 'Vienna 'nextcity) '(Ankara)
(get 'Ankara 'nextcity) '()
".scan( /\(get +'(\S+) .*'\((.*)\)/ ){|from,to|
$links[from] = to.split}
def extend_path path
destinations = $links[ path.last ]
if destinations.empty?
puts path.join( " - " )
else
destinations.each{|city| extend_path path + [city] }
end
end
def paths city; extend_path [city] end
paths 'London'
On Mar 2, 6:33 am, ········@localhost.localdomain (Sven-Olof Nystrom)
wrote:
> A worse problem that the program is buggy.
> it will find the path ABC but not the path AB (or the path A).
There is a bug, but that's not it. The OP didn't ask for subpaths.
There's also a specification issue of why he insisted that all paths
end in a city with no next-cities.
The real problem is that I didn't eliminate ineligible cities.
If any city had multiple circular continuations, the noncircular
path(s) ending in that city would be duplicated.
As for FIND and APPLY #'NCONC, MEMBER or a hashtable might be faster,
but this isn't production code, and I don't know of a better way to
flatten a list in CL.
Anyway, since you mentioned subpaths, here's a hopefully better
version
that works either way:
(labels
((pathlist (city old-path including-subpaths)
(let ((new-path (cons city old-path))
(next-cities (remove-if (lambda (c) (member c old-path))
(get city 'next-cities))))
(if (null next-cities)
(list new-path)
(let ((pathlist
(apply #'nconc
(mapcar (lambda (c)
(pathlist c new-path
including-subpaths))
next-cities))))
(if including-subpaths
(cons new-path pathlist)
pathlist))))))
(defun paths (city &optional including-subpaths)
(and city
(symbolp city)
(mapcar #'reverse (pathlist city '() including-subpaths)))))
-------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
> On Mar 2, 6:33 am, ········@localhost.localdomain (Sven-Olof Nystrom)
> wrote:
>
>> A worse problem that the program is buggy.
>> it will find the path ABC but not the path AB (or the path A).
>
> There is a bug, but that's not it. The OP didn't ask for subpaths.
> There's also a specification issue of why he insisted that all paths
> end in a city with no next-cities.
>
> The real problem is that I didn't eliminate ineligible cities.
> If any city had multiple circular continuations, the noncircular
> path(s) ending in that city would be duplicated.
>
> As for FIND and APPLY #'NCONC, MEMBER or a hashtable might be faster,
> but this isn't production code, and I don't know of a better way to
> flatten a list in CL.
>
> Anyway, since you mentioned subpaths, here's a hopefully better
> version
> that works either way:
>
> (labels
> ((pathlist (city old-path including-subpaths)
> (let ((new-path (cons city old-path))
> (next-cities (remove-if (lambda (c) (member c old-path))
> (get city 'next-cities))))
> (if (null next-cities)
> (list new-path)
> (let ((pathlist
> (apply #'nconc
> (mapcar (lambda (c)
> (pathlist c new-path
> including-subpaths))
> next-cities))))
> (if including-subpaths
> (cons new-path pathlist)
> pathlist))))))
> (defun paths (city &optional including-subpaths)
> (and city
> (symbolp city)
> (mapcar #'reverse (pathlist city '() including-subpaths)))))
I assumed that the program was intended to compute all paths starting
with a city, as it did (almost) that. The destination city was not
even mentioned in the previous program.
As for efficiency, the problem is that both this program and the
previous program have unnecessarily high complexity. When you go
beyond a few dozen cities the inefficency will be noticable. What is
the largest graph you have tested this program on?
Of course, enumerating all paths between two nodes in a graph is
always a very expensive operation. Not something to be undertaken
unless you *really* need to compute all paths. If you are interested
in a single path (the shortest, for example) there are better
solutions. What is your application?
Sven-Olof
·········@gmail.com writes:
> Can anyone help me with this problem?
>
> Find all possible non-circular paths between cities starting from a
> given city. The possible end of the path is one of the cities from
> which we can go anywhere (here Madrid and Ankara).
A quick-and-dirty solution would be to modify Norvig's PAIP trip
function to do breadth-first search rather than beam search, to
collect those paths that don't contain duplicate cities, and to stop
when the length of the paths exceeds the total number of cities.
Maybe five or ten minutes of programming. Hope this helps.