[Haskell-cafe] finding the right mathematical model

[wren ng thornton]

Andrew Korzhuev wrote:
>> What sort of model would be suitable to describe this, some sort of 
>> matrix?
> 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 
constraints.

-- 
Live well,
~wren