0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ (I find stackexchange.com questions to work better where there is one explicit question in the post body.) $\endgroup$
    – greybeard
    Jul 31 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 31 at 5:49
  • $\begingroup$ What's the context where you encountered this problem? $\endgroup$
    – D.W.
    Jul 31 at 5:52
  • $\begingroup$ 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. $\endgroup$
    – user1da901
    Jul 31 at 18:48
  • $\begingroup$ Where did you encounter this exercise? Can you cite/credit the original source? $\endgroup$
    – D.W.
    Jul 31 at 21:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.