Graphic Matroid
(matroid/graphic_matroid.hpp)

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

Overview

GraphicMatroid uses the edges of an undirected graph as its ground set. A subset is independent exactly when the selected edges form a forest.

Element i corresponds to edges()[i]. Parallel edges are supported; loops are always dependent.

Oracle inputs must contain distinct valid edge indices.

Interface

Method	Description	Complexity
GraphicMatroid(int vertex_count, std::vector<std::pair<int, int>> edges)	Stores the graph.	$O(E)$
int size() const	Returns the number of ground elements (edges).	$O(1)$
int vertex_count() const	Returns the graph’s vertex count.	$O(1)$
const std::vector<std::pair<int, int>>& edges() const	Returns the indexed edge list.	$O(1)$
bool independent(const std::vector<int>& subset) const	Checks whether the selected edges are acyclic.	$O(V+	S	\alpha(V))$
bool operator()(const std::vector<int>& subset) const	Independence-oracle shorthand.	$O(V+	S	\alpha(V))$

Example

#include "matroid/graphic_matroid.hpp"
#include <utility>
#include <vector>

std::vector<std::pair<int, int>> edges = {
    {0, 1}, {1, 2}, {2, 0}, {2, 3}
};
m1une::matroid::GraphicMatroid matroid(4, edges);

bool forest = matroid(std::vector<int>{0, 1, 3}); // true
bool cycle = matroid(std::vector<int>{0, 1, 2});  // false

Required by

• Matroid All (matroid/all.hpp)

Verified with

• verify/matroid/matroid_intersection.test.cpp
• verify/matroid/matroids.test.cpp
• verify/matroid/weighted_matroid_intersection.test.cpp

Code

#ifndef M1UNE_MATROID_GRAPHIC_MATROID_HPP
#define M1UNE_MATROID_GRAPHIC_MATROID_HPP 1

#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

class GraphicMatroid {
   private:
    int _vertex_count;
    std::vector<std::pair<int, int>> _edges;

   public:
    GraphicMatroid() : _vertex_count(0) {}

    GraphicMatroid(int vertex_count, std::vector<std::pair<int, int>> edges)
        : _vertex_count(vertex_count), _edges(std::move(edges)) {
        assert(0 <= vertex_count);
#ifndef NDEBUG
        for (auto [u, v] : _edges) {
            assert(0 <= u && u < _vertex_count);
            assert(0 <= v && v < _vertex_count);
        }
#endif
    }

    int size() const {
        return int(_edges.size());
    }

    int vertex_count() const {
        return _vertex_count;
    }

    const std::vector<std::pair<int, int>>& edges() const {
        return _edges;
    }

    bool independent(const std::vector<int>& subset) const {
        std::vector<int> parent_or_size(_vertex_count, -1);
        auto leader = [&](auto&& self, int v) -> int {
            if (parent_or_size[v] < 0) return v;
            return parent_or_size[v] = self(self, parent_or_size[v]);
        };

        for (int element : subset) {
            assert(0 <= element && element < int(_edges.size()));
            auto [u, v] = _edges[element];
            u = leader(leader, u);
            v = leader(leader, v);
            if (u == v) return false;
            if (-parent_or_size[u] < -parent_or_size[v]) std::swap(u, v);
            parent_or_size[u] += parent_or_size[v];
            parent_or_size[v] = u;
        }
        return true;
    }

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

}  // namespace matroid
}  // namespace m1une

#endif  // M1UNE_MATROID_GRAPHIC_MATROID_HPP

#line 1 "matroid/graphic_matroid.hpp"



#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

class GraphicMatroid {
   private:
    int _vertex_count;
    std::vector<std::pair<int, int>> _edges;

   public:
    GraphicMatroid() : _vertex_count(0) {}

    GraphicMatroid(int vertex_count, std::vector<std::pair<int, int>> edges)
        : _vertex_count(vertex_count), _edges(std::move(edges)) {
        assert(0 <= vertex_count);
#ifndef NDEBUG
        for (auto [u, v] : _edges) {
            assert(0 <= u && u < _vertex_count);
            assert(0 <= v && v < _vertex_count);
        }
#endif
    }

    int size() const {
        return int(_edges.size());
    }

    int vertex_count() const {
        return _vertex_count;
    }

    const std::vector<std::pair<int, int>>& edges() const {
        return _edges;
    }

    bool independent(const std::vector<int>& subset) const {
        std::vector<int> parent_or_size(_vertex_count, -1);
        auto leader = [&](auto&& self, int v) -> int {
            if (parent_or_size[v] < 0) return v;
            return parent_or_size[v] = self(self, parent_or_size[v]);
        };

        for (int element : subset) {
            assert(0 <= element && element < int(_edges.size()));
            auto [u, v] = _edges[element];
            u = leader(leader, u);
            v = leader(leader, v);
            if (u == v) return false;
            if (-parent_or_size[u] < -parent_or_size[v]) std::swap(u, v);
            parent_or_size[u] += parent_or_size[v];
            parent_or_size[v] = u;
        }
        return true;
    }

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

}  // namespace matroid
}  // namespace m1une

Back to top page