Suggestions on how to connect components of a grid-based graph

[theguitarist]

Hello,

I have a graph that is represented in the form of a grid. For example:

V--V
--VV
V---V
VVVVV

Each V is a node. If there is another V above/below/to the side of a V then there is an edge between them.

I'm to form one single connected component in this by doing either:
1. adding a node where it doesn't exist
2. Removing a node from where it exists
3. Moving a node either above/below/to the side if no node exists there.

Each of the above have different costs.

I'm to find a decent way to this using some combination of 1, 2 and 3.

I don't know if the optimal solution is easy to find (complexity-wise). Perhaps there is a greedy approach to this that will do fairly well?

[gusano79]

Is the grid important to the graph, or is it just a convenience for display purposes?

[theguitarist]

Well it is important. Not just for display. On a normal graph you could connect 2 vertices with an edge no matter which the 2 vertices are. Here it is only vertices right next to each other can be connected. Each cell in the grid constrains the location of the vertex in it.

The problem wants a solution with the grid structure in mind.
Hope I didn't confuse you further :P

[gusano79]

The problem wants a solution with the grid structure in mind.

Fair enough.

If "one single connected component" means you're supposed to modify it to be a connected graph, then what does it actually mean to be adding, removing, and moving nodes? There will generally be multiple ways to connect disconnected subgraphs, so if the grid is meaningful, how do you decide which is the "right" connection to make?

A smartass solution is to add a node everywhere one doesn't exist--boom, it's all connected. I'm pretty sure that's not the solution they're looking for, though... it feels like we're missing some important information.

[theguitarist]

If "one single connected component" means you're supposed to modify it to be a connected graph, then what does it actually mean to be adding, removing, and moving nodes? There will generally be multiple ways to connect disconnected subgraphs, so if the grid is meaningful, how do you decide which is the "right" connection to make?

Imagine there is a real grid of rooms in each of which may lie of computer. Each computer may communicate with a computer next to it(not diagonally though). In one arrangement it so happens that not all computers are able to communicate with eachother (for obvious reasons of lack of connectivity). Our task is to either:
1. add new computers to empty rooms
2. delete computers from some rooms
3. move a computer from one room to another room next to it
or any combination of the above 3.

Each of those 1,2 and 3 have costs.
We want the minimal cost or atleast a good cost. "The" right connection is the one with least cost.

However if that is hard we could settle with a "good" cost.

Are we missing any information?

[gusano79]

Are we missing any information?

Not any more :)

So... it's an optimization problem. Is there a particular strategy you've been working on, or are your options wide open?

You could model the problem as something resembling a single-player game tree, with each "move" being one of the add/delete/move operations. This will probably not be super efficient, but if the grid is relatively small, it won't be unmanageable. Also, there are improvements to the basic tree building process, like stopping if you reach a connected configuration you've already got cheaper elsewhere in the tree, or not delving into subtrees if they're already guaranteed to be more expensive than a solution you already have.

[theguitarist]

Nope I haven't been able to think of a particular strategy. The only thing I was able to do was separate it into components and join the components. This of course uses just turning a non-verex into a vertex (one of those 3 moves).

About the game tree approach, it is just brute force isn't it :)
I don't think it is feasible at all. It would produce the best solution though

Is there a greedy approach? One that would give a decent result?

[gusano79]

About the game tree approach, it is just brute force isn't it :)

It can be. The improvements I mentioned help some.

I don't think it is feasible at all

Why not?

One way or another, you're looking at some kind of decision tree-type analysis.

It would produce the best solution though

If you run it all the way through, yes. But you can also bail out as soon as you find a solution that is "good enough" in your judgment.

Is there a greedy approach?

You could just try the cheapest actions and see if they get you a valid configuration. If that doesn't get you one, though, you have to backtrack and try something else. Stop at the first one you find that works.

This is essentially a depth-first look at the tree, generating it as you go; the method I described earlier is a breadth-first search.

separate it into components and join the components.

Actually this sounds like a good way to limit your choices: Only consider actions that bring you closer (for some definition of "closer") to connecting the parts, ignoring moves that don't really help.

[theguitarist]

Why not?

The amount of processing to be done is really large. All my implementaions ran far too long.

If you run it all the way through, yes. But you can also bail out as soon as you find a solution that is "good enough" in your judgment.

I don't have any heuristics that will tell me if a solution is "good enough". By good enough I meant one produced by an intuitively convincing greedy algorithm :)

Actually this sounds like a good way to limit your choices: Only consider actions that bring you closer (for some definition of "closer") to connecting the parts, ignoring moves that don't really help.

I've been finding it really hard to write what you say in code. A definition of "closer" is quite complex to me.

If I advance/find out anything more, I'll post here.

Thanks

[gusano79]

The amount of processing to be done is really large. All my implementaions ran far too long.

A naive (brute force) implementation of the tree would certainly take a long time, but you have the cost information available, which should allow you to stop looking at series of more expensive changes.

I can't think of another method right now that would actually be less complex.

I don't have any heuristics that will tell me if a solution is "good enough".

An easy one is "fits within the budget for moving/buying computers."

By good enough I meant one produced by an intuitively convincing greedy algorithm :)

The concepts "intuitively convincing" and "runs in a reasonable amount of time" may be mutually exclusive here, depending on how intuitive trees and recursion are for you.

I've been finding it really hard to write what you say in code. A definition of "closer" is quite complex to me.

If you can identify separate groups of connected rooms and how far apart they are, how about this:

1. Identify all of the groups of rooms.
2. Identify all possible moves you can make.
3. Eliminate the ones that don't actually reduce the distance between any of the groups.
4. Of the remaining moves, choose the one that is cheapest and make that move.
5. Repeat steps 1-4 until you've connected all of the groups.

I believe this will always get you a solution, mostly because you always have the option of adding a new computer to an empty room.

Hm. It'll also never choose to delete computers. If the sequence (delete, add) is cheaper than moving a single machine, you might adjust step 3 to only eliminate moves that increase the distance between groups.

Note that we're actually searching the move tree, just without generating all possible subtrees--one way to avoid running until the sun explodes. A greedy algorithm like this won't always get you the best solution, but it's relatively straightforward and simple, compared to some of the more accurate and/or efficient tree searching techniques.