[Haskell-cafe] finding the right mathematical model
wren ng thornton
wren at freegeek.org
Tue Jul 6 04:04:25 EDT 2010
Andrew Korzhuev wrote:
>> What sort of model would be suitable to describe this, some sort of
> You still can get loops if your matrix represents graph.
> Sounds like you need a tree.
Well, a DAG would suffice and would be less restrictive. Of course,
you'd want to have the amendation that self-loops are acceptable (i.e.,
a partial order).
Depending on the interpretation of your graph, you may be able to weaken
the restrictions to just having a total preorder. That is, if you're
only interested in the endpoints of complete paths ---namely that the
start is unreachable from (or is identical with) the end--- and not the
specifics of how that path is shaped (i.e., path-medial loops are fine),
then a preorder is sufficient to remove the bad loops.
I'm not aware of specific datastructures for implementing
partial/pre-orders directly, so you'd probably end up representing them
as graphs and then have auxiliary functions to verify the additional
More information about the Haskell-Cafe