Routing algorithm - help needed

- C
- Chris Jones
  
  Contact options for registered users
posted
20 years ago

Tue, Feb 24, 2004 11:22 AM

Consider the grid shown below.

There are 4 electrical "switch pairs" which need to be connected to make the overall connection work.

--------------------------------------------------------- | | | | | | | | | | | | | | |

--------------------------------------------------------- | | | | | | | | | | | | | | c`|

--------------------------------------------------------- | | | | | | | | | | | | | | |

--------------------------------------------------------- | | | | b | | | | | | | | | | |

--------------------------------------------------------- | | | | | | | | | | | | | d'| |

--------------------------------------------------------- | | | | | | | | | | | | | | |

--------------------------------------------------------- | | | | | | a | | | | | a`| | | |

--------------------------------------------------------- | | | | | | | | | | | | | | |

--------------------------------------------------------- | | | | | | | | | | | b`| | | |

--------------------------------------------------------- | | | | | | | d | | | | | | | |

--------------------------------------------------------- | | | | | | | | | | | | | | |

--------------------------------------------------------- | | c | | | | | | | | | | | | |

---------------------------------------------------------

The paths are

a --- a' (path A) b --- b' (path B) c --- c' (path C) d --- d' (path D)

There would be two possible routes to connect these paths. The connection can follow either 1) horizontal then vertical direction, or 2) vertical then horizontal direction. There ie no other way that the path between the electrical switches could be made. Thus every possible path here would make a bounded rectangle encompassing the pair of switches.

The following rule is to be followed for making up these paths:

If a switch p belonging to one path lies in the bounded rectangle formed by the switches belonging to another path, then path p must be connected first.

SO - What would be the order of connectivity of this set of paths?

AND - Develop a generalized procedure to implement this strategy!

Thanks, Chris

- D
- David Brown
  
  Contact options for registered users
Vote on answer
posted
20 years ago

Tue, Feb 24, 2004 12:00 PM

The strategy will not work in general. Consider the network:

a b -

- a' b'

It's easy to see a connection solution, but b is in the boundary of a-a', and a' is in the boundary of b-b', so your strategy will not work here.

Also, you need to consider how to deal with unsolvable networks.

- D
- Dave
  
  Contact options for registered users
Vote on answer
posted
20 years ago

Tue, Feb 24, 2004 6:01 PM

First, determine how you would do this in your head. Then try to do it on paper. Then pretend to be a dumb computer and do it on paper again. Then you should have a good idea how the program will work.

Seems, unless I've misread it, that this network is soluble in alphabetical order: a-a': trivial. b-b': across/down fails because of a-a'; down/across works. c-c': could go either way d-d': up/right crosses a-a' but right/up is ok.

So in my head I'm marking cells that have been visited by existing connections, then for subsequent connections considering if those cells are already occupied. It's not hard to see that in other arrangements, abcd might not be possible but some other order is, so you'll need to run through the possible variations from abcd to dcba, listing the orders that work.

Dave.