-1
$\begingroup$

We have sequence that we got from topological sort, but because the graph may not be connected in all cases, we should sort this sequence with another factor.

We should output permutation of numbers from $1$ to $n$ such that we also have graph $G$ that is without cycle and might be not connected and array $A$ of integers that is keeping another information for each nod. Now for each pair $(i,j)$ node $j$ should be after node $i$ if they are connected, meaning node $j$ is under node $i$, on other hand if not $j$ is not under $i$, they are not connected, they should be compared with the another array A and sorted with that array.

So, if node $j$ is not reachable from node $i$, node $j$ should be after $i$ if $A_j$ is greater than $A_i$

For example, let our graph have 3 nodes and 1 edge: $(1, 2)$. If $B$ after the topological sort is $\{ 3, 1, 2\}$ and another sequence $A_1 = 5, A_2=8, A_3=1 $. We should sort the sequence $B=\{1, 2, 3\}$. We cannot put $2$ before $1$ because we will break the topological sort rule give above.

I was thinking about using normal sorts, but they are not giving correct results.

$\endgroup$
0
$\begingroup$

Your requirements may not be simultaneously satisfiable. Consider the graph with three nodes $1,2,3$, and a single edge $1 \to 2$. Suppose the array $A$ is $[15,5,10]$. Then node 1 is not reachable from node 3 and $A_1 > A_3$, so your requirement says node 1 should be after node 3. Also node 3 is not reachable from node 2 and $A_3 > A_2$, so your requirement says that node 3 should be after node 2. Finally based on the graph, we require node 1 to be before node 2. These three requirements are not simultaneously satisfiable.

In general, if you have a problem you don't know how to approach, I suggest you start by working through a bunch of small examples by hand, to get a feeling for what's going on. That will help you discover examples like this.

$\endgroup$
  • $\begingroup$ The sort actually should be in the reverse order, node $j$ should be after node $i$ if $A_j > A_i$, so the output permutation is 1 3 2. We want to keep the topological order, but if more answers are possible we want to compare them on $A$, smallest first (but keep the topological order) $\endgroup$ – someone12321 Mar 9 '18 at 17:13
  • $\begingroup$ @someone12321, you changed your question after I wrote my answer. I can only answer the question that was asked. In the future please take more care to get the question right the first time. $\endgroup$ – D.W. Mar 9 '18 at 19:13
  • $\begingroup$ @someone12321, anyway, I revised my answer based on your changed question. The bottom line still holds. After adjusting the example, the conclusion is still that the requirements might not be simultaneously satisfiable. $\endgroup$ – D.W. Mar 9 '18 at 19:14
  • $\begingroup$ The topology is most important, and after we have done this topology sort over the graph, if more than one answer is possible. For our case (1, 2, 3), (1, 3, 2), (3, 1, 2) are all valid topologically sorted sequences over our graph, but we want to reorder now such that the smallest from $A$ is first etc.., so in first position can go 1 and 3, because A[3] is smaller 3 will go first, and now the permutation must be 3 1 2 $\endgroup$ – someone12321 Mar 10 '18 at 8:49
  • $\begingroup$ Also please note that the sequence may not be sorted always correctly by $A$. $\endgroup$ – someone12321 Mar 10 '18 at 8:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.