fzi_icl_core: ts_UnionFind.cpp Source File

Go to the documentation of this file.
00001 // this is for emacs file handling -*- mode: c++; indent-tabs-mode: nil -*-
00002 
00003 // -- BEGIN LICENSE BLOCK ----------------------------------------------
00004 // This file is part of FZIs ic_workspace.
00005 //
00006 // This program is free software licensed under the LGPL
00007 // (GNU LESSER GENERAL PUBLIC LICENSE Version 3).
00008 // You can find a copy of this license in LICENSE folder in the top
00009 // directory of the source code.
00010 //
00011 // © Copyright 2016 FZI Forschungszentrum Informatik, Karlsruhe, Germany
00012 //
00013 // -- END LICENSE BLOCK ------------------------------------------------
00014 
00015 //----------------------------------------------------------------------
00022 //----------------------------------------------------------------------
00023 #include <icl_core/UnionFind.h>
00024 
00025 #include <boost/test/unit_test.hpp>
00026 
00027 using icl_core::UnionFind;
00028 
00029 BOOST_AUTO_TEST_SUITE(ts_UnionFind)
00030 
00031 BOOST_AUTO_TEST_CASE(UnionFindTest)
00032 {
00033   UnionFind uf(5);
00034   BOOST_CHECK_EQUAL(uf.size(), 5);
00035   BOOST_CHECK_EQUAL(uf.find(0), 0);
00036   BOOST_CHECK_EQUAL(uf.find(1), 1);
00037   BOOST_CHECK_EQUAL(uf.find(2), 2);
00038   BOOST_CHECK_EQUAL(uf.find(3), 3);
00039   BOOST_CHECK_EQUAL(uf.find(4), 4);
00040 
00041   uf.merge(0, 1);
00042   uf.merge(2, 3);
00043   BOOST_CHECK_EQUAL(uf.find(0), 0);
00044   BOOST_CHECK_EQUAL(uf.find(1), 0);
00045   BOOST_CHECK_EQUAL(uf.find(2), 2);
00046   BOOST_CHECK_EQUAL(uf.find(3), 2);
00047   BOOST_CHECK_EQUAL(uf.find(4), 4);
00048 
00049   uf.merge(2, 4);
00050   BOOST_CHECK_EQUAL(uf.find(0), 0);
00051   BOOST_CHECK_EQUAL(uf.find(1), 0);
00052   BOOST_CHECK_EQUAL(uf.find(2), 2);
00053   BOOST_CHECK_EQUAL(uf.find(3), 2);
00054   BOOST_CHECK_EQUAL(uf.find(4), 2);
00055 
00056   // Copying the structure and merging in different directions
00057   {
00058     UnionFind uf_forward = uf;
00059     UnionFind uf_backward = uf;
00060     uf_forward.merge(0, 3);
00061     BOOST_CHECK_EQUAL(uf_forward.find(0), 0);
00062     BOOST_CHECK_EQUAL(uf_forward.find(1), 0);
00063     BOOST_CHECK_EQUAL(uf_forward.find(2), 0);
00064     BOOST_CHECK_EQUAL(uf_forward.find(3), 0);
00065     BOOST_CHECK_EQUAL(uf_forward.find(4), 0);
00066 
00067     uf_backward.merge(3, 0);
00068     BOOST_CHECK_EQUAL(uf_backward.find(0), 2);
00069     BOOST_CHECK_EQUAL(uf_backward.find(1), 2);
00070     BOOST_CHECK_EQUAL(uf_backward.find(2), 2);
00071     BOOST_CHECK_EQUAL(uf_backward.find(3), 2);
00072     BOOST_CHECK_EQUAL(uf_backward.find(4), 2);
00073   }
00074 
00075   // Enlarging the structure
00076   uf.grow(2);
00077   BOOST_CHECK_EQUAL(uf.size(), 7);
00078   BOOST_CHECK_EQUAL(uf.find(0), 0);
00079   BOOST_CHECK_EQUAL(uf.find(1), 0);
00080   BOOST_CHECK_EQUAL(uf.find(2), 2);
00081   BOOST_CHECK_EQUAL(uf.find(3), 2);
00082   BOOST_CHECK_EQUAL(uf.find(4), 2);
00083   BOOST_CHECK_EQUAL(uf.find(5), 5);
00084   BOOST_CHECK_EQUAL(uf.find(6), 6);
00085 
00086   // Merging on the enlarged structure
00087   uf.merge(5, 6);
00088   uf.merge(4, 5);
00089   BOOST_CHECK_EQUAL(uf.find(0), 0);
00090   BOOST_CHECK_EQUAL(uf.find(1), 0);
00091   BOOST_CHECK_EQUAL(uf.find(2), 2);
00092   BOOST_CHECK_EQUAL(uf.find(3), 2);
00093   BOOST_CHECK_EQUAL(uf.find(4), 2);
00094   BOOST_CHECK_EQUAL(uf.find(5), 2);
00095   BOOST_CHECK_EQUAL(uf.find(6), 2);
00096 
00097   uf.merge(1, 6);
00098   BOOST_CHECK_EQUAL(uf.find(0), 2);
00099   BOOST_CHECK_EQUAL(uf.find(1), 2);
00100   BOOST_CHECK_EQUAL(uf.find(2), 2);
00101   BOOST_CHECK_EQUAL(uf.find(3), 2);
00102   BOOST_CHECK_EQUAL(uf.find(4), 2);
00103   BOOST_CHECK_EQUAL(uf.find(5), 2);
00104   BOOST_CHECK_EQUAL(uf.find(6), 2);
00105 }
00106 
00107 BOOST_AUTO_TEST_SUITE_END()