#include <stdlib.h>
#include <assert.h>
#include "defs.hh"
#include "orbit.hh"
/*
Copyright (c) 2003-2015 Tommi Junttila
Released under the GNU Lesser General Public License version 3.
This file is part of bliss.
bliss is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, version 3 of the License.
bliss is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with bliss. If not, see <http://www.gnu.org/licenses/>.
*/
namespace bliss_digraphs {
Orbit::Orbit()
{
nof_elements = 0;
}
Orbit::~Orbit()
{
}
void Orbit::init(
const unsigned int n)
{
assert(n > 0);
orbits_vec.resize(n);
orbits = orbits_vec.begin();
in_orbit_vec.resize(n);
in_orbit = in_orbit_vec.begin();
nof_elements = n;
reset();
}
void Orbit::reset()
{
assert(!orbits_vec.empty());
assert(!in_orbit_vec.empty());
for(
unsigned int i = 0; i < nof_elements; i++)
{
orbits[i].element = i;
orbits[i].next = 0;
orbits[i].size = 1;
in_orbit[i] = &orbits[i];
}
_nof_orbits = nof_elements;
}
void Orbit::merge_orbits(OrbitEntry *orbit1, OrbitEntry *orbit2)
{
if(orbit1 != orbit2)
{
_nof_orbits--;
/* Only update the elements in the smaller orbit */
if(orbit1->size > orbit2->size)
{
OrbitEntry *
const temp = orbit2;
orbit2 = orbit1;
orbit1 = temp;
}
/* Link the elements of orbit1 to the almost beginning of orbit2 */
OrbitEntry *e = orbit1;
while(e->next)
{
in_orbit[e->element] = orbit2;
e = e->next;
}
in_orbit[e->element] = orbit2;
e->next = orbit2->next;
orbit2->next = orbit1;
/* Keep the minimal orbit representative in the beginning */
if(orbit1->element < orbit2->element)
{
const unsigned int temp = orbit1->element;
orbit1->element = orbit2->element;
orbit2->element = temp;
}
orbit2->size += orbit1->size;
}
}
void Orbit::merge_orbits(
unsigned int e1,
unsigned int e2)
{
merge_orbits(in_orbit[e1], in_orbit[e2]);
}
bool Orbit::is_minimal_representative(
unsigned int element)
const
{
return(get_minimal_representative(element) == element);
}
unsigned int Orbit::get_minimal_representative(
unsigned int element)
const
{
OrbitEntry *
const orbit = in_orbit[element];
return(orbit->element);
}
unsigned int Orbit::orbit_size(
unsigned int element)
const
{
return(in_orbit[element]->size);
}
}
// namespace bliss_digraphs
