igraph_all_minimal_st_separators() sometimes returns empty separators
#2517
Assignees
Labels
fuzz
Issues found using fuzzing, or related to fuzzing
wrong result
A bug where an incorrect result is being returned
Comments
szhorvat
added
the
wrong result
|
I’ll try to fix this on the flight if there’s enough legroom :) |
|
b3e7184 fixes this but I think it's only a band-aid that prevents empty separators from appearing in the result. The underlying algorithm does not have a clear notion about how a separator is defined in a graph that is already disconnected, so if you throw disconnected graphs at it, it will return separators that are not consistent with how you are re-writing the separator function right now. |
krlmlr
added a commit
to igraph/rigraph
that referenced
this issue
Mar 2, 2024
do not generate full scanner tables with flex chore: improve readability of some code refactor: igraph_degree() now uses the cache when checking for self-loops refactor: minor readability cleanup for minimum_size_separators() chore: add note about empty minimal st separator fix tests: minor cleanup in regression tests chore: update changelog fix: correct `is_(minimal_)separator()` for disconnected graphs, fixes igraph/igraph#1480 tests: add more `is_separator()` tests tests: fix premature memory deallocation in is_separator example fix: igraph_all_minimal_st_separators() does not return empty separators any more, fixes igraph/igraph#2517 fix: GraphML reader does not accept duplicate attribute names any more, fixes igraph/igraph#2506 fuzzing: assertion readability in vertex separator fuzzer fuzzing: improve vertex separator fuzzers docs: doc improvements for ECC and Voronoi refactor: minor prettification in trie code fix: assert that keys in a trie are not NULL to make Coverity happy refactor: improved error messages from C attribute handler (igraph/igraph#2513) chore: updated changelog fix: prevent insertion of empty keys in a trie fix: prevent empty ID attributes for <key> tags in GraphML docs: change mentions to pointer vectors to vector lists where appropriate & other improvements fix: -CF causes buffer overflows with Flex, try -Cf instead fix: bug_2506 test case should not be run if igraph is compiled without GraphML support ci: run apt-get update in codeql-analysis pipeline fix: fix attribute value comparison in igraph_read_graph_graphml() fix: fix duplicate attribute detection in igraph_read_graph_graphml(), fixes igraph/igraph#2506 refactor: make use of IGRAPH_CHECK_OOM() in a few places style: fix wording for a few warnings refactor: more detailed error messages in C attribute handler refactor: experimental `-Cf` option for Flex for better performance at the cost of larger code size. Hopefully this avoids fuzzer timeouts. fix: `igraph_disjoint_union()` and `igraph_disjoint_union_many()` now check for overflow chore: Update CONTRIBUTING.md fuzzing: expand file format round-tripping fuzzers fix: disallow writing invalid graph attributes to GML files, fixes igraph/igraph#2505 fuzzing: write_all fuzzer fixes refactor: remove non-exposed igraph_maximum_matching() function whihc was already noted as removed in the 0.10 changelog fuzzing: activate write_all fuzzer fuzzing: add cohesive_blocks() Merge pull request igraph/igraph#2504 from igraph/fix/writing-invalid-lgl-ncol-files
aviator-app bot
pushed a commit
to igraph/rigraph
that referenced
this issue
Mar 2, 2024
do not generate full scanner tables with flex chore: improve readability of some code refactor: igraph_degree() now uses the cache when checking for self-loops refactor: minor readability cleanup for minimum_size_separators() chore: add note about empty minimal st separator fix tests: minor cleanup in regression tests chore: update changelog fix: correct `is_(minimal_)separator()` for disconnected graphs, fixes igraph/igraph#1480 tests: add more `is_separator()` tests tests: fix premature memory deallocation in is_separator example fix: igraph_all_minimal_st_separators() does not return empty separators any more, fixes igraph/igraph#2517 fix: GraphML reader does not accept duplicate attribute names any more, fixes igraph/igraph#2506 fuzzing: assertion readability in vertex separator fuzzer fuzzing: improve vertex separator fuzzers docs: doc improvements for ECC and Voronoi refactor: minor prettification in trie code fix: assert that keys in a trie are not NULL to make Coverity happy refactor: improved error messages from C attribute handler (igraph/igraph#2513) chore: updated changelog fix: prevent insertion of empty keys in a trie fix: prevent empty ID attributes for <key> tags in GraphML docs: change mentions to pointer vectors to vector lists where appropriate & other improvements fix: -CF causes buffer overflows with Flex, try -Cf instead fix: bug_2506 test case should not be run if igraph is compiled without GraphML support ci: run apt-get update in codeql-analysis pipeline fix: fix attribute value comparison in igraph_read_graph_graphml() fix: fix duplicate attribute detection in igraph_read_graph_graphml(), fixes igraph/igraph#2506 refactor: make use of IGRAPH_CHECK_OOM() in a few places style: fix wording for a few warnings refactor: more detailed error messages in C attribute handler refactor: experimental `-Cf` option for Flex for better performance at the cost of larger code size. Hopefully this avoids fuzzer timeouts. fix: `igraph_disjoint_union()` and `igraph_disjoint_union_many()` now check for overflow chore: Update CONTRIBUTING.md fuzzing: expand file format round-tripping fuzzers fix: disallow writing invalid graph attributes to GML files, fixes igraph/igraph#2505 fuzzing: write_all fuzzer fixes refactor: remove non-exposed igraph_maximum_matching() function whihc was already noted as removed in the 0.10 changelog fuzzing: activate write_all fuzzer fuzzing: add cohesive_blocks() Merge pull request igraph/igraph#2504 from igraph/fix/writing-invalid-lgl-ncol-files
krlmlr
added a commit
to igraph/rigraph
that referenced
this issue
Mar 2, 2024
do not generate full scanner tables with flex chore: improve readability of some code refactor: igraph_degree() now uses the cache when checking for self-loops refactor: minor readability cleanup for minimum_size_separators() chore: add note about empty minimal st separator fix tests: minor cleanup in regression tests chore: update changelog fix: correct `is_(minimal_)separator()` for disconnected graphs, fixes igraph/igraph#1480 tests: add more `is_separator()` tests tests: fix premature memory deallocation in is_separator example fix: igraph_all_minimal_st_separators() does not return empty separators any more, fixes igraph/igraph#2517 fix: GraphML reader does not accept duplicate attribute names any more, fixes igraph/igraph#2506 fuzzing: assertion readability in vertex separator fuzzer fuzzing: improve vertex separator fuzzers docs: doc improvements for ECC and Voronoi refactor: minor prettification in trie code fix: assert that keys in a trie are not NULL to make Coverity happy refactor: improved error messages from C attribute handler (igraph/igraph#2513) chore: updated changelog fix: prevent insertion of empty keys in a trie fix: prevent empty ID attributes for <key> tags in GraphML docs: change mentions to pointer vectors to vector lists where appropriate & other improvements fix: -CF causes buffer overflows with Flex, try -Cf instead fix: bug_2506 test case should not be run if igraph is compiled without GraphML support ci: run apt-get update in codeql-analysis pipeline fix: fix attribute value comparison in igraph_read_graph_graphml() fix: fix duplicate attribute detection in igraph_read_graph_graphml(), fixes igraph/igraph#2506 refactor: make use of IGRAPH_CHECK_OOM() in a few places style: fix wording for a few warnings refactor: more detailed error messages in C attribute handler refactor: experimental `-Cf` option for Flex for better performance at the cost of larger code size. Hopefully this avoids fuzzer timeouts. fix: `igraph_disjoint_union()` and `igraph_disjoint_union_many()` now check for overflow chore: Update CONTRIBUTING.md fuzzing: expand file format round-tripping fuzzers fix: disallow writing invalid graph attributes to GML files, fixes igraph/igraph#2505 fuzzing: write_all fuzzer fixes refactor: remove non-exposed igraph_maximum_matching() function whihc was already noted as removed in the 0.10 changelog fuzzing: activate write_all fuzzer fuzzing: add cohesive_blocks() Merge pull request igraph/igraph#2504 from igraph/fix/writing-invalid-lgl-ncol-files
krlmlr
added a commit
to igraph/rigraph
that referenced
this issue
Mar 3, 2024
chore: update changelog feat: igraph_is_complete() checks if a graph is complete (igraph/igraph#2510) Merge pull request igraph/igraph#2525 from igraph/fix/linegraph-keep-loops do not generate full scanner tables with flex chore: improve readability of some code refactor: igraph_degree() now uses the cache when checking for self-loops refactor: minor readability cleanup for minimum_size_separators() chore: add note about empty minimal st separator fix tests: minor cleanup in regression tests chore: update changelog fix: correct `is_(minimal_)separator()` for disconnected graphs, fixes igraph/igraph#1480 tests: add more `is_separator()` tests tests: fix premature memory deallocation in is_separator example fix: igraph_all_minimal_st_separators() does not return empty separators any more, fixes igraph/igraph#2517 fix: GraphML reader does not accept duplicate attribute names any more, fixes igraph/igraph#2506 fuzzing: assertion readability in vertex separator fuzzer fuzzing: improve vertex separator fuzzers docs: doc improvements for ECC and Voronoi refactor: minor prettification in trie code fix: assert that keys in a trie are not NULL to make Coverity happy refactor: improved error messages from C attribute handler (igraph/igraph#2513) chore: updated changelog fix: prevent insertion of empty keys in a trie fix: prevent empty ID attributes for <key> tags in GraphML docs: change mentions to pointer vectors to vector lists where appropriate & other improvements fix: -CF causes buffer overflows with Flex, try -Cf instead fix: bug_2506 test case should not be run if igraph is compiled without GraphML support ci: run apt-get update in codeql-analysis pipeline fix: fix attribute value comparison in igraph_read_graph_graphml() fix: fix duplicate attribute detection in igraph_read_graph_graphml(), fixes igraph/igraph#2506 refactor: make use of IGRAPH_CHECK_OOM() in a few places style: fix wording for a few warnings refactor: more detailed error messages in C attribute handler refactor: experimental `-Cf` option for Flex for better performance at the cost of larger code size. Hopefully this avoids fuzzer timeouts. fix: `igraph_disjoint_union()` and `igraph_disjoint_union_many()` now check for overflow chore: Update CONTRIBUTING.md fuzzing: expand file format round-tripping fuzzers fix: disallow writing invalid graph attributes to GML files, fixes igraph/igraph#2505 fuzzing: write_all fuzzer fixes refactor: remove non-exposed igraph_maximum_matching() function whihc was already noted as removed in the 0.10 changelog fuzzing: activate write_all fuzzer fuzzing: add cohesive_blocks() Merge pull request igraph/igraph#2504 from igraph/fix/writing-invalid-lgl-ncol-files docs: document that `write_graph_graphml()` assumes that strings are UTF-8 encoded, fixes igraph/igraph#2503 docs: mention that the variation of information is in natural units
krlmlr
added a commit
to igraph/rigraph
that referenced
this issue
Mar 3, 2024
chore: update changelog feat: igraph_is_complete() checks if a graph is complete (igraph/igraph#2510) Merge pull request igraph/igraph#2525 from igraph/fix/linegraph-keep-loops do not generate full scanner tables with flex chore: improve readability of some code refactor: igraph_degree() now uses the cache when checking for self-loops refactor: minor readability cleanup for minimum_size_separators() chore: add note about empty minimal st separator fix tests: minor cleanup in regression tests chore: update changelog fix: correct `is_(minimal_)separator()` for disconnected graphs, fixes igraph/igraph#1480 tests: add more `is_separator()` tests tests: fix premature memory deallocation in is_separator example fix: igraph_all_minimal_st_separators() does not return empty separators any more, fixes igraph/igraph#2517 fix: GraphML reader does not accept duplicate attribute names any more, fixes igraph/igraph#2506 fuzzing: assertion readability in vertex separator fuzzer fuzzing: improve vertex separator fuzzers docs: doc improvements for ECC and Voronoi refactor: minor prettification in trie code fix: assert that keys in a trie are not NULL to make Coverity happy refactor: improved error messages from C attribute handler (igraph/igraph#2513) chore: updated changelog fix: prevent insertion of empty keys in a trie fix: prevent empty ID attributes for <key> tags in GraphML docs: change mentions to pointer vectors to vector lists where appropriate & other improvements fix: -CF causes buffer overflows with Flex, try -Cf instead fix: bug_2506 test case should not be run if igraph is compiled without GraphML support ci: run apt-get update in codeql-analysis pipeline fix: fix attribute value comparison in igraph_read_graph_graphml() fix: fix duplicate attribute detection in igraph_read_graph_graphml(), fixes igraph/igraph#2506 refactor: make use of IGRAPH_CHECK_OOM() in a few places style: fix wording for a few warnings refactor: more detailed error messages in C attribute handler refactor: experimental `-Cf` option for Flex for better performance at the cost of larger code size. Hopefully this avoids fuzzer timeouts. fix: `igraph_disjoint_union()` and `igraph_disjoint_union_many()` now check for overflow chore: Update CONTRIBUTING.md fuzzing: expand file format round-tripping fuzzers fix: disallow writing invalid graph attributes to GML files, fixes igraph/igraph#2505 fuzzing: write_all fuzzer fixes refactor: remove non-exposed igraph_maximum_matching() function whihc was already noted as removed in the 0.10 changelog fuzzing: activate write_all fuzzer fuzzing: add cohesive_blocks() Merge pull request igraph/igraph#2504 from igraph/fix/writing-invalid-lgl-ncol-files docs: document that `write_graph_graphml()` assumes that strings are UTF-8 encoded, fixes igraph/igraph#2503 docs: mention that the variation of information is in natural units
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Describe the bug
igraph_all_minimal_st_separators()sometimes returns empty separators.This isn't fixed by #2509.
To reproduce
This is correct:
But if we add an isolated vertex, it returns an (invalid) empty separator.
Version information
Current
masterThe text was updated successfully, but these errors were encountered: