Uniform Matroid
(matroid/uniform_matroid.hpp)

• View this file on GitHub
• Last update: 2026-07-01 14:07:14+09:00
• Include: #include "matroid/uniform_matroid.hpp"

Overview

UniformMatroid represents the uniform matroid $U_{r,n}$. Its ground set is {0, 1, ..., n - 1}, and a subset is independent exactly when it contains at most $r$ elements.

Oracle inputs must contain distinct valid ground-set indices.

Interface

Method	Description	Complexity
UniformMatroid(int ground_size, int rank)	Constructs $U_{r,n}$. Requires 0 <= rank <= ground_size.	$O(1)$
int size() const	Returns the ground-set size.	$O(1)$
int rank() const	Returns $r$.	$O(1)$
bool independent(const std::vector<int>& subset) const	Tests whether subset.size() <= rank().	$O(1)$
bool operator()(const std::vector<int>& subset) const	Independence-oracle shorthand.	$O(1)$

Example

#include "matroid/uniform_matroid.hpp"
#include <vector>

m1une::matroid::UniformMatroid matroid(5, 2);
bool ok = matroid(std::vector<int>{1, 4}); // true

Required by

• Matroid All (matroid/all.hpp)

Verified with

• verify/matroid/matroids.test.cpp

Code

#ifndef M1UNE_MATROID_UNIFORM_MATROID_HPP
#define M1UNE_MATROID_UNIFORM_MATROID_HPP 1

#include <cassert>
#include <vector>

namespace m1une {
namespace matroid {

class UniformMatroid {
   private:
    int _ground_size;
    int _rank;

   public:
    UniformMatroid() : _ground_size(0), _rank(0) {}
    UniformMatroid(int ground_size, int rank) : _ground_size(ground_size), _rank(rank) {
        assert(0 <= rank && rank <= ground_size);
    }

    int size() const {
        return _ground_size;
    }

    int rank() const {
        return _rank;
    }

    bool independent(const std::vector<int>& subset) const {
        return int(subset.size()) <= _rank;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

#endif  // M1UNE_MATROID_UNIFORM_MATROID_HPP

#line 1 "matroid/uniform_matroid.hpp"



#include <cassert>
#include <vector>

namespace m1une {
namespace matroid {

class UniformMatroid {
   private:
    int _ground_size;
    int _rank;

   public:
    UniformMatroid() : _ground_size(0), _rank(0) {}
    UniformMatroid(int ground_size, int rank) : _ground_size(ground_size), _rank(rank) {
        assert(0 <= rank && rank <= ground_size);
    }

    int size() const {
        return _ground_size;
    }

    int rank() const {
        return _rank;
    }

    bool independent(const std::vector<int>& subset) const {
        return int(subset.size()) <= _rank;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

Back to top page