google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
10.79k stars 2.09k forks source link

Segmentation fault in GraphSymmetryFinder destructor #3954

Open andre-tebart opened 9 months ago

andre-tebart commented 9 months ago

What version of OR-Tools and what language are you using? Version: v9.7 Language: C++

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) GraphSymmetryFinder

What operating system (Linux, Windows, ...) and version? Ubuntu 22.04

What did you do? Steps to reproduce the behavior:

#include <doctest/doctest.h>
#include <ortools/algorithms/sparse_permutation.h>
#include <ortools/algorithms/find_graph_symmetries.h>
#include <ortools/graph/graph.h>

TEST_SUITE("or-tools symmetry finder") {
    TEST_CASE("finds symmetries") {
        auto graph = operations_research::GraphSymmetryFinder::Graph{};
        graph.Build();

        auto symmetryFinder = operations_research::GraphSymmetryFinder(graph, true);
    }
}

I run this code snippet via doctest.

What did you expect to see I expect this to just run through.

What did you see instead? The program crashes with a segmentation violation signal. This is the stack trace I get:

std::_Rb_tree_increment(std::_Rb_tree_node_base*) 0x00007fffefa6a1d4
operations_research::StatsGroup::~StatsGroup() 0x00007ffff0ad87e9
operations_research::GraphSymmetryFinder::Stats::~Stats find_graph_symmetries.h:249
operations_research::GraphSymmetryFinder::~GraphSymmetryFinder find_graph_symmetries.h:45
DOCTEST_ANON_SUITE_14::DOCTEST_ANON_FUNC_15 graph_symmetry.test.cpp:12
doctest::Context::run doctest.h:7007
main test_main.cpp:8
<unknown> 0x00007fffef79bd90
__libc_start_main 0x00007fffef79be40
_start 0x0000555555555145

Anything else we should know about your project / environment We also use CP-SAT in our project and don't have any issues there.

Mizux commented 9 months ago

From an internal test:

https://github.com/google/or-tools/blob/9154cf343decf2489fec38bdf0958e687921d636/ortools/algorithms/find_graph_symmetries_test.cc#L60 https://github.com/google/or-tools/blob/9154cf343decf2489fec38bdf0958e687921d636/ortools/algorithms/find_graph_symmetries_test.cc#L72-L77

two questions:

  1. Does a graph with no arc "is symmetric" ?
  2. Why not using GraphIsSymmetric(graph) ?
Mizux commented 9 months ago
  1. Does a graph with no arc is symmetric ?

Seems the second arg means "is_undirect"

https://github.com/google/or-tools/blob/9154cf343decf2489fec38bdf0958e687921d636/ortools/algorithms/find_graph_symmetries.h#L49-L60

andre-tebart commented 8 months ago

The error also occurs with a non empty undirected graph. You get correct results from the symmetry finder but it still crashes in the destructor.

lperron commented 8 months ago

We have added unit test on our code, and it does not crash.

Mizux commented 8 months ago

see https://github.com/google/or-tools/commit/d0eb8dd3d80ecbb5a91f94337af4ed80240d8284

note: currently not supported nor run when using cmake based build...