Velocity Reviews > Prioritization function needed (recursive help!)

# Prioritization function needed (recursive help!)

rh0dium
Guest
Posts: n/a

 01-21-2008
Hi all,

I need some help on writing a recursive priority function

Given a list = [ A, B, C, D]

Where the following constraints are in place:

A depends on [B, C]
C depends on [B]

Figure out real order that prioritizes these.

Output [ B, C, A, D ] is valid. (Actually D could be anywhere in it
as it doesn't matter..)

I am really struggling on simply how to organize the data and write
the corresponding function - I tried classes but I don't know if
that's the best approach. See my other post on this.

Thanks

Paul Rubin
Guest
Posts: n/a

 01-21-2008
rh0dium <(E-Mail Removed)> writes:
> I am really struggling on simply how to organize the data and write
> the corresponding function - I tried classes but I don't know if
> that's the best approach. See my other post on this.

Anyway, look up "topological sorting" in a CS textbook or on Wikipedia.

Arnaud Delobelle
Guest
Posts: n/a

 01-21-2008
On Jan 21, 10:30*pm, rh0dium <(E-Mail Removed)> wrote:
> Hi all,
>
> I need some help on writing a recursive priority function
>
> Given a list = [ A, B, C, D]
>
> Where the following constraints are in place:
>
> A depends on [B, C]
> C depends on [B]
>
> Figure out real order that prioritizes these.
>
> Output [ B, C, A, D ] is valid. *(Actually D could be anywhere in it
> as it doesn't matter..)
>
> I am really struggling on simply how to organize the data and write
> the corresponding function - I tried classes but I don't know if
> that's the best approach. *See my other post on this.
>
> Thanks

There's a very recent thread on this subject (topological sort)

--
Arnaud

Kent Johnson
Guest
Posts: n/a

 01-21-2008
rh0dium wrote:
> Hi all,
>
> I need some help on writing a recursive priority function
>
> Given a list = [ A, B, C, D]
>
> Where the following constraints are in place:
>
> A depends on [B, C]
> C depends on [B]
>
> Figure out real order that prioritizes these.

You need a topological sort.
http://en.wikipedia.org/wiki/Topological_sort

Two Python implementations:
http://pypi.python.org/pypi/topsort/0.9
http://www.bitformation.com/art/python_toposort.html

Kent