This PR implements a modified version of Kobayashi and Tamaki's algorithm for computing crossing numbers for orientable pairs only. Tested against the tiny medium testsets. Example usage:
banana::crossing::CrossingMatrix c(graph);
auto p = c.getOrientablePairs();
std::cout << p.size() << " orientable pairs:" << std::endl;
for (auto[i, j] : p)
std::cout << i+1 << ',' << j+1 << std::endl;
for (int i : graph.getB())
{
for (int j : graph.getB())
std::cout << std::setw(2) << c(i, j) << ' ';
std::cout << std::endl;
}
Summary of changes:
Implemented the CrossingMatrix class
Slightly modified BipartiteGraph: added getA() and getB() to be able to get partitions more easily. Not sure if this is the approach we are going for. There was some discussion about relabelling vertices to be 0-indexed on each partition, but I think this is better in some ways. cc @MvKaio
Fixes #9.
This PR implements a modified version of Kobayashi and Tamaki's algorithm for computing crossing numbers for orientable pairs only. Tested against the tiny medium testsets. Example usage:
Summary of changes:
CrossingMatrix
classBipartiteGraph
: addedgetA()
andgetB()
to be able to get partitions more easily. Not sure if this is the approach we are going for. There was some discussion about relabelling vertices to be 0-indexed on each partition, but I think this is better in some ways. cc @MvKaio