DisjointSet.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2013 Shell Hu
 * Copyright (C) 2013 Shell Hu
 */

#ifndef __DISJOINTSET_H__
#define __DISJOINTSET_H__

#include <shogun/lib/config.h>

#include <shogun/base/SGObject.h>
#include <shogun/lib/SGVector.h>

namespace shogun
{

class CDisjointSet : public CSGObject
{
public:
    CDisjointSet();

    CDisjointSet(int32_t num_elements);

    ~CDisjointSet() { }

    virtual const char* get_name() const { return "DisjointSet"; }

    void make_sets();

    int32_t find_set(int32_t x);

    int32_t link_set(int32_t xroot, int32_t yroot);

    bool union_set(int32_t x, int32_t y);

    bool is_same_set(int32_t x, int32_t y);

    int32_t get_unique_labeling(SGVector<int32_t> out_labels);

    int32_t get_num_sets();

    bool get_connected();

    void set_connected(bool is_connected);

private:
    void init();

private:
    int32_t m_num_elements;

    SGVector<int32_t> m_parent;

    SGVector<int32_t> m_rank;

    bool m_is_connected;
};

}

#endif