Routing algorithm - help needed

C

Chris Jones

Guest
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
 
"Chris Jones" <chjones@dacafe.com> wrote in message
news:8090cd3b.0402240322.107d76ce@posting.google.com...
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
Click to expand...
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.
 
Chris Jones wrote:
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
Click to expand...

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.
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top