crash on input

[schulzchristian]

graph

6 5 1
2 1
1 1 3 1
2 1 4 100
3 100 5 1
4 1 6 1
5 1

links

1 3 100
4 6 100

initial mincut is 1, with the links it should be 2 (cut out node 2 or 5); the program crashed instead.

[tomaThomas]

The algorithms are only about (unweighted) connectivity, so I did not consier link weights in the input graph. I will adjust the parser so any METIS graph will be accepted

[schulzchristian]

thanks!

[tomaThomas]

Vertex and edge weights in the input graph are now parsed, but ignored

[schulzchristian]

just ignoring them is not good, as this leads false results. which parts of the algorithm are not supporting weights? as soon as we work on the cactus it is a weighted graph, isn't it? VieCut is supporting weights.

[tomaThomas]

You're right, VieCut is already using the weights and creates a weighted cactus graph.
HeiConnect does not store them when parsing the original graph, but that graph is not used for the algorithms (mainly to find parallel links, and for constructing the augmented graph). The augmented graph that HeiConnect can output therefore has no weights, but that's the only drawback.

However, the problem definition was increasing the edge connectivity by 1, so the algorithms assume that all links have weight 1 independent from the cost, and e.g. the max flow algorithm only uses integer weights. Supporting non integer weights would require some changes