Hi @angriman,

Thank you for your feedback! I’d like to provide some context and arguments for the choice of graph sizes in the tests and the use of many test cases:

1. Multiple and Larger Graphs
   During the initial implementation, I relied on smaller, single-graph tests, which passed successfully. However, when I extended the tests to include many graphs of the same class (e.g., multiple grid graphs instead of a single 3x3 grid graph), some cases emerged, revealing bugs in the algorithm. Additionally, larger and random graphs helped me uncover issues that smaller graphs missed. These are the main reasons I included these tests.

2. Algorithm extension
   I plan to extend my contribution by modifying the algorithm to provide planar embeddings for planar graphs. This may require minor refactoring of the current implementation. Similarly, potential performance improvements might also lead to refactoring. Having a variety of test cases (including larger and multiple graphs) will make it easier for me and others to ensure correctness during these changes.

3. Negligible Runtime Cost
   On my machine, the runtime difference between testing a single graph versus hundreds of graphs is of the order of a few milliseconds, which is negligible compared to tests that take up to 10 seconds. The same applies to the included large random graphs. While I understand the importance of keeping tests efficient ("Kleinvieh macht auch Mist"), I currently believe the benefits of including larger and multiple graphs, outweigh the costs.

Given these reasons, I’d appreciate it if we could retain the current test cases in the file LeftRightPlanarityCheckGTest.cpp. Of course, I’m happy to hear your thoughts.

What do you think?

Hi @angriman,

Thank you for your feedback! I’d like to provide some context and arguments for the choice of graph sizes in the tests and the use of many test cases:

1. Multiple and Larger Graphs
   During the initial implementation, I relied on smaller, single-graph tests, which passed successfully. However, when I extended the tests to include many graphs of the same class (e.g., multiple grid graphs instead of a single 3x3 grid graph), some cases emerged, revealing bugs in the algorithm. Additionally, larger and random graphs helped me uncover issues that smaller graphs missed. These are the main reasons I included these tests.

2. Algorithm extension
   I plan to extend my contribution by modifying the algorithm to provide planar embeddings for planar graphs. This may require minor refactoring of the current implementation. Similarly, potential performance improvements might also lead to refactoring. Having a variety of test cases (including larger and multiple graphs) will make it easier for me and others to ensure correctness during these changes.

3. Negligible Runtime Cost
   On my machine, the runtime difference between testing a single graph versus hundreds of graphs is of the order of a few milliseconds, which is negligible compared to tests that take up to 10 seconds. The same applies to the included large random graphs. While I understand the importance of keeping tests efficient ("Kleinvieh macht auch Mist"), I currently believe the benefits of including larger and multiple graphs, outweigh the costs.

Given these reasons, I’d appreciate it if we could retain the current test cases in the file LeftRightPlanarityCheckGTest.cpp. Of course, I’m happy to hear your thoughts.

What do you think?

There are positives and negatives about having random generated graphs for testing. In the past it helped us discover some quite subtle bugs. However, sometimes these can come from the generators itself, leading to the case that a test implicitly checks the functionalities of different code units. Also you can not predict when these errors turn up. Overall there are better systems to generate these tests, but these would need a complete pipeline overhaul.

We had more bugs in algorithms / core functionalities which only use a pre-defined set of graphs, since these are often too narrow to cover all corner-cases and are tailored around the original use-cases of the algorithm. Therefore I would not drop the strategy of testing random graphs.

It is true though that this one algorithm does incorporate a lot of generated graphs. While fast for now, running times can explode when new features are encoded or data structures change. I would therefore suggest to drop some redundancy / cases. As a rule of thumb, most algorithms don't test for more than 10 different graphs.

Hi @angriman,
Thank you for your feedback! I’d like to provide some context and arguments for the choice of graph sizes in the tests and the use of many test cases:

1. Multiple and Larger Graphs
   During the initial implementation, I relied on smaller, single-graph tests, which passed successfully. However, when I extended the tests to include many graphs of the same class (e.g., multiple grid graphs instead of a single 3x3 grid graph), some cases emerged, revealing bugs in the algorithm. Additionally, larger and random graphs helped me uncover issues that smaller graphs missed. These are the main reasons I included these tests.

2. Algorithm extension
   I plan to extend my contribution by modifying the algorithm to provide planar embeddings for planar graphs. This may require minor refactoring of the current implementation. Similarly, potential performance improvements might also lead to refactoring. Having a variety of test cases (including larger and multiple graphs) will make it easier for me and others to ensure correctness during these changes.

3. Negligible Runtime Cost
   On my machine, the runtime difference between testing a single graph versus hundreds of graphs is of the order of a few milliseconds, which is negligible compared to tests that take up to 10 seconds. The same applies to the included large random graphs. While I understand the importance of keeping tests efficient ("Kleinvieh macht auch Mist"), I currently believe the benefits of including larger and multiple graphs, outweigh the costs.

Given these reasons, I’d appreciate it if we could retain the current test cases in the file LeftRightPlanarityCheckGTest.cpp. Of course, I’m happy to hear your thoughts.
What do you think?

There are positives and negatives about having random generated graphs for testing. In the past it helped us discover some quite subtle bugs. However, sometimes these can come from the generators itself, leading to the case that a test implicitly checks the functionalities of different code units. Also you can not predict when these errors turn up. Overall there are better systems to generate these tests, but these would need a complete pipeline overhaul.

We had more bugs in algorithms / core functionalities which only use a pre-defined set of graphs, since these are often too narrow to cover all corner-cases and are tailored around the original use-cases of the algorithm. Therefore I would not drop the strategy of testing random graphs.

It is true though that this one algorithm does incorporate a lot of generated graphs. While fast for now, running times can explode when new features are encoded or data structures change. I would therefore suggest to drop some redundancy / cases. As a rule of thumb, most algorithms don't test for more than 10 different graphs.

Hi @farbratu,

Thank you for your detailed feedback! I have to admit that I might not have fully grasped all the concerns raised by @angriman. Thank you for providing additional context and suggestions.

1. I agree with your suggestion to reduce redundancy and limit the number of graphs tested for each type. I’ll adjust the tests to include around 10 graphs per type and in some cases, perhaps up to 20.
2. Regarding the use of random graphs: these are programmatically generated. I will reduce their size from 50–100 nodes to a more manageable 10–20 nodes to ensure the tests remain efficient while still being diverse.

Before I proceed, is the above proposal acceptable for you guys?

Hi @angriman,
Thank you for your feedback! I’d like to provide some context and arguments for the choice of graph sizes in the tests and the use of many test cases:

1. Multiple and Larger Graphs
   During the initial implementation, I relied on smaller, single-graph tests, which passed successfully. However, when I extended the tests to include many graphs of the same class (e.g., multiple grid graphs instead of a single 3x3 grid graph), some cases emerged, revealing bugs in the algorithm. Additionally, larger and random graphs helped me uncover issues that smaller graphs missed. These are the main reasons I included these tests.

2. Algorithm extension
   I plan to extend my contribution by modifying the algorithm to provide planar embeddings for planar graphs. This may require minor refactoring of the current implementation. Similarly, potential performance improvements might also lead to refactoring. Having a variety of test cases (including larger and multiple graphs) will make it easier for me and others to ensure correctness during these changes.

3. Negligible Runtime Cost
   On my machine, the runtime difference between testing a single graph versus hundreds of graphs is of the order of a few milliseconds, which is negligible compared to tests that take up to 10 seconds. The same applies to the included large random graphs. While I understand the importance of keeping tests efficient ("Kleinvieh macht auch Mist"), I currently believe the benefits of including larger and multiple graphs, outweigh the costs.

Given these reasons, I’d appreciate it if we could retain the current test cases in the file LeftRightPlanarityCheckGTest.cpp. Of course, I’m happy to hear your thoughts.
What do you think?

There are positives and negatives about having random generated graphs for testing. In the past it helped us discover some quite subtle bugs. However, sometimes these can come from the generators itself, leading to the case that a test implicitly checks the functionalities of different code units. Also you can not predict when these errors turn up. Overall there are better systems to generate these tests, but these would need a complete pipeline overhaul.
We had more bugs in algorithms / core functionalities which only use a pre-defined set of graphs, since these are often too narrow to cover all corner-cases and are tailored around the original use-cases of the algorithm. Therefore I would not drop the strategy of testing random graphs.
It is true though that this one algorithm does incorporate a lot of generated graphs. While fast for now, running times can explode when new features are encoded or data structures change. I would therefore suggest to drop some redundancy / cases. As a rule of thumb, most algorithms don't test for more than 10 different graphs.

Hi @farbratu,

Thank you for your detailed feedback! I have to admit that I might not have fully grasped all the concerns raised by @angriman. Thank you for providing additional context and suggestions.

1. I agree with your suggestion to reduce redundancy and limit the number of graphs tested for each type. I’ll adjust the tests to include around 10 graphs per type and in some cases, perhaps up to 20.
2. Regarding the use of random graphs: these are programmatically generated. I will reduce their size from 50–100 nodes to a more manageable 10–20 nodes to ensure the tests remain efficient while still being diverse.

Before I proceed, is the above proposal acceptable for you guys?

I agree that testing on random graphs is very helpful for finding bugs in the algorithm you are developing (I've used them a lot in the past). However, I think that, when possible, they should not be part of unit tests because of the following reasons (more about testing best practices can be found in [1]):

• Reproducibility: random tests can be flaky when tested on different architectures. It is important to have reproducible tests when possible.
• If they fail, they don't help you understand what in the algorithm is not behaving as intended.

My recommendation is to test on a fixed and representative set of instances to evaluate that the algorithm behaves as intended. I understand that sometimes this is easier said than done because the algorithm may be complex. If that's the case, we can keep tests on random graphs.

Regarding large graphs: it's ok to have individual tests on larger instances (you can also use those in the input/ directory in NetworKit). What I'm against is writing a unit test with 50+ lines used for graph edges, which makes it impossible for a future reader to understand what's going on. Why do you need do define such a large graph? What kind of behavior are you trying to test that cannot be tested with a smaller instance?

If you just need to test your algorithm on a larger graph, then my recommendation is to replace the custom graphs with 50+ nodes (testRandomGeneratedPlanarGraph50/51/100Nodes) with graphs in the input/ directory.

Let me know if you have further questions!

[1] https://abseil.io/resources/swe-book/html/ch12.html

Hi @angriman,
Thank you for your feedback! I’d like to provide some context and arguments for the choice of graph sizes in the tests and the use of many test cases:

1. Multiple and Larger Graphs
   During the initial implementation, I relied on smaller, single-graph tests, which passed successfully. However, when I extended the tests to include many graphs of the same class (e.g., multiple grid graphs instead of a single 3x3 grid graph), some cases emerged, revealing bugs in the algorithm. Additionally, larger and random graphs helped me uncover issues that smaller graphs missed. These are the main reasons I included these tests.

2. Algorithm extension
   I plan to extend my contribution by modifying the algorithm to provide planar embeddings for planar graphs. This may require minor refactoring of the current implementation. Similarly, potential performance improvements might also lead to refactoring. Having a variety of test cases (including larger and multiple graphs) will make it easier for me and others to ensure correctness during these changes.

3. Negligible Runtime Cost
   On my machine, the runtime difference between testing a single graph versus hundreds of graphs is of the order of a few milliseconds, which is negligible compared to tests that take up to 10 seconds. The same applies to the included large random graphs. While I understand the importance of keeping tests efficient ("Kleinvieh macht auch Mist"), I currently believe the benefits of including larger and multiple graphs, outweigh the costs.

Given these reasons, I’d appreciate it if we could retain the current test cases in the file LeftRightPlanarityCheckGTest.cpp. Of course, I’m happy to hear your thoughts.
What do you think?

There are positives and negatives about having random generated graphs for testing. In the past it helped us discover some quite subtle bugs. However, sometimes these can come from the generators itself, leading to the case that a test implicitly checks the functionalities of different code units. Also you can not predict when these errors turn up. Overall there are better systems to generate these tests, but these would need a complete pipeline overhaul.
We had more bugs in algorithms / core functionalities which only use a pre-defined set of graphs, since these are often too narrow to cover all corner-cases and are tailored around the original use-cases of the algorithm. Therefore I would not drop the strategy of testing random graphs.
It is true though that this one algorithm does incorporate a lot of generated graphs. While fast for now, running times can explode when new features are encoded or data structures change. I would therefore suggest to drop some redundancy / cases. As a rule of thumb, most algorithms don't test for more than 10 different graphs.

Hi @farbratu,
Thank you for your detailed feedback! I have to admit that I might not have fully grasped all the concerns raised by @angriman. Thank you for providing additional context and suggestions.

1. I agree with your suggestion to reduce redundancy and limit the number of graphs tested for each type. I’ll adjust the tests to include around 10 graphs per type and in some cases, perhaps up to 20.
2. Regarding the use of random graphs: these are programmatically generated. I will reduce their size from 50–100 nodes to a more manageable 10–20 nodes to ensure the tests remain efficient while still being diverse.

Before I proceed, is the above proposal acceptable for you guys?

I agree that testing on random graphs is very helpful for finding bugs in the algorithm you are developing (I've used them a lot in the past). However, I think that, when possible, they should not be part of unit tests because of the following reasons (more about testing best practices can be found in [1]):

* Reproducibility: random tests can be flaky when tested on different architectures. It is important to have reproducible tests when possible.

* If they fail, they don't help you understand what in the algorithm is not behaving as intended.

My recommendation is to test on a fixed and representative set of instances to evaluate that the algorithm behaves as intended. I understand that sometimes this is easier said than done because the algorithm may be complex. If that's the case, we can keep tests on random graphs.

Regarding large graphs: it's ok to have individual tests on larger instances (you can also use those in the input/ directory in NetworKit). What I'm against is writing a unit test with 50+ lines used for graph edges, which makes it impossible for a future reader to understand what's going on. Why do you need do define such a large graph? What kind of behavior are you trying to test that cannot be tested with a smaller instance?

If you just need to test your algorithm on a larger graph, then my recommendation is to replace the custom graphs with 50+ nodes (testRandomGeneratedPlanarGraph50/51/100Nodes) with graphs in the input/ directory.

Let me know if you have further questions!

[1] https://abseil.io/resources/swe-book/html/ch12.html

Thank you for the detailed explanation of your concerns. I considered the large graphs of the input folder before but shied away from the effort to independently determine if they are planar or not. I will go ahead and try while removing the "random graphs" from the unit tests. For the "typed graphs" I will reduce the number of generated graphs as proposed above and reorganize the tests to focus on specific behaviors. Thank your for the link to the article. It was a great read and a helpful reminder of best practices.

A side-comment: The error in the pipeline for the aarch64 wheel build is fixed in PR #1283 and can be ignored concerning the finish state of this PR.

There are still unresolved comments (e.g., std::ranges::is_sorted vs std::is_sorted), did you forget to push some commits?

There are still unresolved comments (e.g., std::ranges::is_sorted vs std::is_sorted), did you forget to push some commits?

Sorry. They should all be marked as Outdated. I will go through and resolve them.