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