# Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario.

Let $$x_1,...,x_n$$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $$x_1$$ starts driving strictly before $$x_2$$ and so on. i.e. Each $$x_i$$ starts driving strictly before $$x_j$$ for any $$j > i$$.

We also have a set of facts $$Y$$. We have that $$(x_i,x_j) \in Y$$ where $$i < j$$ if $$x_i$$ finishes driving before $$x_j$$ begins.

We also have a set of facts $$Z$$. We have that $$(x_i,x_j) \in Z$$ where $$i < j$$ if $$x_i$$ and $$x_j$$ were ever driving at the same time on the road.

The following is an example of an inconsistent pair of sets of facts $$Y$$ and $$Z$$.

If $$Y = \{(x_1,x_2)\}$$ and $$Z = \{(x_1,x_3)\}$$, then this pair of sets of facts are inconsistent. Why? We have that $$x_1$$ finishes driving before $$x_2$$ begins driving and we have that $$x_1$$ and $$x_3$$ were also at one point both driving at the same time.

But we know that $$x_2$$ begins driving strictly before $$x_3$$. So if $$x_1$$ finishes driving before $$x_2$$, then we also must have that $$x_1$$ finishes driving before $$x_3$$. Hence, we cannot have that $$x_1$$ and $$x_3$$ were also at one point both driving at the same time.

Hence, this pair of $$Y, Z$$ are inconsistent.

In general, consistency is defined so that for every $$(x_i,x_j) \in Y$$ where $$i < j$$, there is no $$k \geq j$$ such that $$(x_i,x_k) \in Z$$.

Problem Statement: Given $$x_1,...,x_n$$, where each $$x_i$$ starts driving strictly before $$x_j$$ for any $$j > i$$, and given $$Y$$ and $$Z$$, is all our facts consistent with each other?

I am looking for a general algorithm that can determine whether or not a given pair of $$X,Y$$ are consistent or inconsistent.

I am trying to formulate this as a directed graph problem where each node is some $$x_i$$, and each edge is some relationship given by elements of $$Y,Z$$. And then use topological sort to check if cycles exist.

My main issue is somehow translating $$Y$$ and $$Z$$ into edges of a directed graph.

The following problem is similar to my problem.

https://stackoverflow.com/questions/66702780/efficient-algorithm-to-check-queue-consistency-by-pairwise-relationship

• (I find stackexchange.com questions to work better where there is one explicit question in the post body.) Jul 31 at 5:30
• What's your question? I don't see a question here. We are a question-and-answer site, and we require you to articulate a specific question. Please edit your post accordingly.
– D.W.
Jul 31 at 5:49
• What's the context where you encountered this problem?
– D.W.
Jul 31 at 5:52
• I have edited the question to add some clarity. I hope it is clear. And the problem is an exercise on directed acyclic graphs (DAG) and topological sorting. Jul 31 at 18:48
• Where did you encounter this exercise? Can you cite/credit the original source?
– D.W.
Jul 31 at 21:29