Segmentation fault in GraphSymmetryFinder destructor

[andre-tebart]

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]

From an internal test:

or-tools/ortools/algorithms/find_graph_symmetries_test.cc

Line 60 in 9154cf3

using Graph = GraphSymmetryFinder::Graph;

or-tools/ortools/algorithms/find_graph_symmetries_test.cc

Lines 72 to 77 in 9154cf3

	Graph graph;
	for (const std::pair<int, int>& arc : arcs) {
	graph.AddArc(arc.first, arc.second);
	}
	graph.Build();
	GraphSymmetryFinder symmetry_finder(graph, GraphIsSymmetric(graph));

two questions:

1. Does a graph with no arc "is symmetric" ?
2. Why not using GraphIsSymmetric(graph) ?

[Mizux]

1. Does a graph with no arc is symmetric ?

Seems the second arg means "is_undirect"

or-tools/ortools/algorithms/find_graph_symmetries.h

Lines 49 to 60 in 9154cf3

	// If the Graph passed to the GraphSymmetryFinder is undirected, i.e.
	// for every arc a->b, b->a is also present, then you should set
	// "is_undirected" to true.
	// This will, in effect, DCHECK() that the graph is indeed undirected,
	// and bypass the need for reverse adjacency lists.
	//
	// If you don't know this in advance, you may use GraphIsSymmetric() from
	// ortools/graph/util.h.
	//
	// "graph" must not have multi-arcs.
	// TODO(user): support multi-arcs.
	GraphSymmetryFinder(const Graph& graph, bool is_undirected);

[andre-tebart]

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]

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

[Mizux]

see d0eb8dd

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