Algorithm to identify network differences

[kevin.hall]

I've got a problem where I have to identify differences in network. The
network may have different types of nodes and may only have a string of
ring-like topology:


Code:
A--B--C--D--E

or

A--B--C--D--E
| |
+-----------+

What I must do is identify the simplest way to change Network 1 into
Network 2


For example:

Code:
Network 1:

A--D--C--B

Network 2:

A--B--C--D

Solution: Swap nodes B and D


Another example:

Network 1:

A--B--C--D--E

Network 2:

A--B--C--D--E
| |
+-----------+

Solution: Connect node E to node A


NOTE: This is not a homework problem. This is a work-related problem.
My current solution is to run through a set of possible problems and
analyze each one. Something like this:

* Compare network topologies: (string-like or ring-like)
* Count the number of nodes on each network.
* Identify which nodes are identical and which are different.
* Does the topology type (string vs. ring) need to change? If so, what
is the simplest fix?
* Are 2 nodes swapped? If yes, identify which ones.
* Are 3 nodes different? Then...
* etc...

This does not seem like the most efficient way of doing things, and it
seems like this is something that someone would have worked out in
acadamia somewhere.

My question: Is there a well known algorthm for this sort of problem?

Many thanks!

- Kevin

 

[phil_gg04]

Kevin asked

I've got a problem where I have to identify differences in network. The
network may have different types of nodes and may only have a string of
ring-like topology:

For example:
A--D--C--B
A--B--C--D
Solution: Swap nodes B and D

You are looking for an "edit script" to convert one to the other.
Typically an edit script list the inserts and deletes needed to go from
one to the other, but you mention swaps; presumably a script listing
inserts and deletes could be converted to one that also used swaps in
some fairly simple way. Apart from that, this is a standard problem;
it's what the "diff" program solves. I can point you to some GPL C++
code to solve it if you are interested. Otherwise, try to find "An
O(ND) Difference Algorithm and Its Variations" by Eugene W Myers; the
PDF is out there somewhere and is quite readable.

Your variation on this is that you also have rings. A naive solution
is to consider each point where the ring could be broken to form a
string and find the edit script in each case, then select the one with
the simplest script. Alternatively, I wonder if Myers' algorithm could
be transformed to "wrap around" at the edges?

--Phil.

 

[kevin.hall]

Thanks for the reply. That helps a bunch. I appreciate the idea about
considering the parts connecting the nodes as nodes themselves --
either "good connection" or "bad connection".

I will take a look at Myer's paper. In the mean time, would you mind
posting the links to the GPL C++ code you mentioned?

Thanks again!

- Kevin

 

[phil_gg04]

would you mind posting the links to the GPL C++ code you mentioned?

Download http://chezphil.org/anyterm/anyterm-0.14.tbz2 and look at
apachemod/diff.*

--Phil.

 

[kevin.hall]

Thanks again!