4
$\begingroup$

The problem: This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (which is the start and the end of the edge). The nodes can be in an arbitrary order, and the whole list can contain duplicates. The wanted output is a list of each node (identified by name) and it's coordinates.

It can be assumed that the input uniquely identifies each point correctly, otherwise the algorithm can cancel with an error.

here is an example:

The input could be (AA,BB,CC are names of nodes)

AA,BB = (1,1),(2,2)
BB,AA = (2,2),(1,1)
BB,AA = (1,1),(2,2)
AA,CC = (1,1),(3,3)

The output would be :

AA = (1,1)
BB = (2,2)
CC = (3,3)

So essentially form a list of undirected edges, I want to fetch the list of named nodes.

My current solution: is a naive implementation, where I'm simple iterating (or recursing) through the input, I note 2 possible coordinates for each named node. If a coordinate verifies with another line of input I mark it as 'confirmed' and add it to the final result (and remove it from the set of 'possible' coordinates).

What I want: is a better solution, because this feels like a standard problem of graph theory. Can this be reduced to an existing problem, with an existing algorithm? I guess I'm overthinking this, and I all I need to do is putting the input in some kind of mathematical struct and the the solution is trivial or automatically there. Any ideas? Can this be reduced to a standard-problem? Is it possibly NP hard (so my naive implementation is the best I will find)? I'm also struggling to find a unique identifier, for a better solution. Is a name of a point uniquely identifying the 2D coordinate, or is the 2D coordinate uniquely identifying the named node? I have a bit of a blockage in my thinking and can't find a better way than my current one. I'm implementing it in Python, but if anyone has an idea (or hints) in plain words or pseudocode I'm happy to read them.

Thanks

$\endgroup$
2
$\begingroup$

I will assume the graph is connected (otherwise, break it down into connected components and recurse on each connected component).

Pick a single vertex. Find an edge that uses that vertex. That gives you two possibilities for the coordinates of that vertex. Try one of them, propagate its implications, and see if it leads to a contradiction or a consistent assignment of coordinates to vertices. If it leads to a contradiction, try the other possibility. If either leads to a consistent assignment, output that assignment. If both lead to a contradiction, abort with an error.

So all that remains is to describe how to propagate the implications. Suppose we have picked node AA and we assign it to location (2,2). Then we find all edges between node AA and some other unassigned node. This will let us assign a location to other other nodes, or abort with a cancellation. For instance, once we assign AA to location (2,2), the edge AA,BB = (1,1),(2,2) causes us to assign BB to location (1,1) (which might trigger more implications) and the edge AA,CC = (1,1),(3,3) causes a contradiction (since AA can't be in location (2,2)). Once this process completes, we check whether the resulting assignment is consistent with all of the edges; if not, we've found a contradiction. Propagation can be done with any standard graph traversal algorithm, like DFS or BFS.

The running time to propagate the implications is linear in the size of the graph. We only have to do that twice (once for each assumption about the location of the starting vertex), so the total running time is linear, i.e., $O(|V|+|E|)$.

$\endgroup$

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.