Problem 107

[robheus]

The algorithm I used for removing redundant edges was [snip description of correct algorithm].
The solution I found was checked for the example, and gave the right answer (max saving 150).
But it seems not to work for the network described in network.txt.

I can not find an error in my algorithm though. Maybe the algorithm does not work in any network topology?

Any hints as to what could be wrong with it?

[stijn263]

That should work. Are you sure your final network is connected? Did you make any mistakes copying your network? I get 261832 as the original weight. The final answer should not exceed the original weight obviously

[daniel.is.fischer]

The algorithm is provably correct.
But there remain a few possibilities:

• You might have an error in your implementation of the algorithm, check it once more
• You might have an error in your code for reading the network from the file, perhaps check that first
• Actually, I can't think of anything else offhand, would need to see the code or something

[robheus]

That should work. Are you sure your final network is connected? Did you make any mistakes copying your network? I get 261832 as the original weight. The final answer should not exceed the original weight obviously

I did only replace the '-' sign with the number '-1' and added a comma after each line, then included that as:

Code: Select all

int matrix[SIZE*SIZE] = {
#include "network.inc"
};

and use a macro to access those values:

Code: Select all

#define network(x,y)   (matrix[SIZE*(x)+(y)])

My final network is connected because an edge (p,q) is only candidate for removal unless (p,q) still connected in the remaining network via other nodes.
The check for connectedness is done after performing a removal, which is undone directly afterwards, [snip].

[daniel.is.fischer]

I'll have a look.

[robheus]

That should work. Are you sure your final network is connected? Did you make any mistakes copying your network? I get 261832 as the original weight. The final answer should not exceed the original weight obviously

Initial weight confirmed.

[robheus]

I see the error.

I check now if after my removals the complete network still connected.

That shows I removed too many edges.

Because I only check when removing an edge between p and q if p and q still connected via other nodes, but I did not check if any node other then p or q has become disconnected,.....

That is why this worked for the example (because it has some typical network topology) but not the general case.

I should check every node against every other node if they are still connected when attempting to remove an edge....

[daniel.is.fischer]

No, that's not it. Say you have a path between two nodes x, y which uses the edge (p,q). That path then consists of three pieces, the part connecting x to p (without loss of generality), the edge (p,q) and the part connecting q to y. Now if after removing the edge (p,q) there's still a path from p to q, you can insert that path between the first and third pieces of the path from x to y and you see that x and y are still connected.

[daniel.is.fischer]

Bug found, it is in the check for connectedness.

[daniel.is.fischer]

An example exhibiting the problem, small enough to do by hand in order to identify the problem:

Code: Select all

  -1,   3,  -1,  -1,  -1,  -1, 100,  -1,  -1,  -1,  -1,
   3,  -1,  -1,   6,   7,  -1,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,   9,  -1,  -1,  -1,  -1,  -1,
  -1,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  14,  -1,
  -1,   7,  -1,  -1,  -1,  -1,  -1,  -1,  14,  -1,  -1,
  -1,  -1,   9,  -1,  -1,  -1,  13,  14,  -1,  -1,  -1,
 100,  -1,  -1,  -1,  -1,  13,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  19,
  -1,  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  -1,  20,
  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,  -1,  -1,  19,  20,  -1,  -1

[robheus]

No, that's not it. Say you have a path between two nodes x, y which uses the edge (p,q). That path then consists of three pieces, the part connecting x to p (without loss of generality), the edge (p,q) and the part connecting q to y. Now if after removing the edge (p,q) there's still a path from p to q, you can insert that path between the first and third pieces of the path from x to y and you see that x and y are still connected.

Yes, that must be the case. However my implementation of the check for connectedness is in error as even when there is a path between p and q after removing the edge p,q there were some x,y that were unconnected, so I got different / erroneous results.

Will check that function(s).

[robheus]

An example exhibiting the problem, small enough to do by hand in order to identify the problem:

Code: Select all

  -1,   3,  -1,  -1,  -1,  -1, 100,  -1,  -1,  -1,  -1,
   3,  -1,  -1,   6,   7,  -1,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,   9,  -1,  -1,  -1,  -1,  -1,
  -1,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  14,  -1,
  -1,   7,  -1,  -1,  -1,  -1,  -1,  -1,  14,  -1,  -1,
  -1,  -1,   9,  -1,  -1,  -1,  13,  14,  -1,  -1,  -1,
 100,  -1,  -1,  -1,  -1,  13,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  19,
  -1,  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  -1,  20,
  -1,  -1,  -1,  14,  -1,  -1,  -1,  -1,  -1,  -1,  -1,
  -1,  -1,  -1,  -1,  -1,  -1,  -1,  19,  20,  -1,  -1

Added a function 'still_connected()' which checks for every i,j in 0..SIZE-1 that there is a connection.
It returns false when called, even before I have tried removing any edge.

[daniel.is.fischer]

Take a sheet of paper and follow your code-path by hand. That way you'll see the problem. Besides, there's a small other mistake in your bookkeeping.

[robheus]

Take a sheet of paper and follow your code-path by hand. That way you'll see the problem. Besides, there's a small other mistake in your bookkeeping.

Finally found the little error in the check for connectedness, and now it runs in a blimse and gives the right answer!
Thanks!

[ukimiku]

The problem states that points connected in the old network must stay connected in the new one. But can I introduce new connections as well? Provided I keep the old points connected, my new network would preserve its connectedness, fulfilling the problem conditions. Would that be a valid solution as well?

Thanks.

[Susanne]

Hi ukimiku,

the nodes must be connected by edges which are already known. You cannot introduce new connections.

[ukimiku]

Hi Susanne,

thanks for the reply.
From the wording of the problem, it is not forbidden to introduce new connections, it it?

to optimise the network by removing some edges and still ensure that all points on the network remain connected

Introducing new connections would not change the fact that all points on the network remain connected, in my opinion.
Do you think I should talk to the problem inventor?

Again, thank you (and congratulations on your 246 solved problems - wow!)

Regards,

[jaap]

It says to remove edges to "optimise" the graph. To optimise here means to make the graph as simple as possible while still fulfilling the conditions. Why would you add them? And what weight would you give them?
Should every problem list all of the things you shouldn't do? If a problem says to add numbers together, would you ask whether it is allowed to multiply them instead?

[ukimiku]

Oh well, the problem wants you to a) remove edges to "optimize" (reduce total network weight) and b) to ensure that the nodes remain connected. If I add connections, I am ensuring just that, fulfilling task b). Hence I could connect every node with every other node, decide on the weight of the connection freely and then take out only the minimum weights whilst ensuring connectedness. Of course, ideally, one would then assign massively negative weights to new connections as to make the resulting total weight loss exorbitant. Now, this problem just has to have been designed by Weight Watchers...

Seriously, your reply triggered a key idea to understanding why it was not really sensible to introduce new connections shouldn't you be allowed to decide on the weights for them yourself, and thus to the solution. Thanks.

Regards,

[Fogmeister]

Hi,

Just getting started on this and want to see if I can do it from scratch just using knowledge from previous problems etc...

Anyway, I've just got a quick question.

Can connections cross over each other?

i.e. could you have a network with 4 nodes and 6 connections (i.e. each node connected to every other node). In this there are two connections that cross over (hmm... only if you draw straight lines only...).

OK, needs more investigation...

Hmm... are cross overs relevant...

Hmm... ::goes away to think about it some more::