2
$\begingroup$

I have a weighted graph where each edge is a 1d vector eg if weight going from A to B is 1 then from B to A it is -1. In the graph each cycle should add to zero though sometimes the weights have errors and in that case a cycle will not add to zero.

So for example if the weight from A to B is 1 and B to C is 1 then for the cycle to sum to zero C to A must be -2 and there is an error if it is anything else. Please note that in general the cycles can involve an arbitrary amount of nodes.

What is the best algorithm for detecting these errors? IE what is the best algorithm for finding all weights that have errors and so are causing the cycles to add to a non zero value?

$\endgroup$
  • $\begingroup$ Do you really mean that the weights are a vector, or just a number? Your example is 1 and -1, which are numbers, not vectors. $\endgroup$ – D.W. Jul 6 '17 at 18:26
  • $\begingroup$ @D.W. I think the asker is thinking of vectors in the sense that a weight of $-x$ corresponds to "a weight of $x$ in the opposite direction." But I agree it's not the best description. $\endgroup$ – David Richerby Jul 6 '17 at 19:14
2
$\begingroup$

One approach is to compute the distance $d(u,v)$ between each pair $u,v$ of vertices using an all-pairs shortest paths algorithm, such as Floyd-Warshall. Then, if $d(v,v) < 0$, you know that there exists a cycle through $v$ that doesn't add to zero. You can explicitly find one such cycle by augmenting the shortest-paths algorithm with predecessor links to keep track of an example shortest path from $v$ to $v$. Then you know that at least one of the edges along that cycle has an error.

Unfortunately there doesn't appear to be any way to uniquely determine which edges are in error. For instance, consider a graph with edge $a \to b$ of weight $1.01$ and edge $b \to c$ of weight $-1.48$ and edge $c \to a$ of weight $0.50$; you know that at least one of those edges has an error, but there's no way to know which one; it could even be all of them that have an error.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ U are describing a loop. For that there is no error if the weight for A to B is x then the weight from B to A will always be -x. What I mean is that if A to B the weight is 1 B to C it is 1 then for the weights to sum to zero C to A must be -2 and there is an error if it is not as the cycle will then not add to zero $\endgroup$ – Jack Jul 6 '17 at 19:02
  • $\begingroup$ @Jack, actually, no, I am talking about a cycle. I've updated the second paragraph of my answer to give a hopefully-better example of a cycle (not a loop). Take another look at my edited answer and see if that's any clearer. $\endgroup$ – D.W. Jul 6 '17 at 20:24

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.