cp-algo/graph/edge_types.hpp

• View this file on GitHub
• Last update: 2025-12-05 14:59:58+01:00
• Include: #include "cp-algo/graph/edge_types.hpp"

Required by

• cp-algo/graph/base.hpp
• cp-algo/graph/concepts.hpp
• cp-algo/graph/cycle.hpp
• cp-algo/graph/dfs.hpp
• cp-algo/graph/dfs_time.hpp
• cp-algo/graph/euler.hpp
• cp-algo/graph/mst.hpp
• cp-algo/graph/shortest_path.hpp
• cp-algo/graph/tarjan.hpp
• cp-algo/tree/ascending_dfs.hpp
• cp-algo/tree/diameter.hpp
• cp-algo/tree/hld.hpp

Verified with

• Two-Edge-Connected Components (verify/graph/2cc.test.cpp)
• Biconnected Components (verify/graph/bcc.test.cpp)
• Cycle Detection (Directed) (verify/graph/cycle_directed.test.cpp)
• Cycle Detection (Undirected) (verify/graph/cycle_undirected.test.cpp)
• Eulerian Trail (Directed) (verify/graph/euler_directed.test.cpp)
• Eulerian Trail (Undirected) (verify/graph/euler_undirected.test.cpp)
• Minimum Diameter Spanning Tree (verify/graph/minimum_diameter_spanning_tree.test.cpp)
• Minimum Spanning Tree (verify/graph/mst.test.cpp)
• Strongly Connected Components (verify/graph/scc.test.cpp)
• Shortest Path (verify/graph/shortest_path.test.cpp)
• Tree Diameter (SPFA) (verify/graph/tree_diameter_spfa.test.cpp)
• Tree Diameter (verify/tree/diameter.test.cpp)
• Jump on Tree (verify/tree/jump.test.cpp)
• Lowest Common Ancestor (verify/tree/lca.test.cpp)

Code

#ifndef CP_ALGO_GRAPH_EDGE_TYPES_HPP
#define CP_ALGO_GRAPH_EDGE_TYPES_HPP
#include <iostream>
#include <cstdint>
namespace cp_algo::graph {
    using node_index = int;
    struct edge_base {
        int xor_nodes;

        edge_base() {}
        edge_base(node_index from, node_index to): xor_nodes(from ^ to) {}

        // Given one endpoint, return the other
        node_index traverse(node_index from) const {
            return xor_nodes ^ from;
        }

        static auto read(node_index v0 = 0) {
            node_index u, v;
            std::cin >> u >> v;
            u -= v0;
            v -= v0;
            return std::pair{u, edge_base(u, v)};
        }
    };

    struct weighted_edge: edge_base {
        int64_t w;

        weighted_edge() {}
        weighted_edge(node_index from, node_index to, int64_t w): edge_base(from, to), w(w) {}

        static auto read(node_index v0 = 0) {
            auto [u, e] = edge_base::read(v0);
            int64_t w;
            std::cin >> w;
            return std::pair{u, weighted_edge(u, e.traverse(u), w)};
        }
    };

    template<typename edge>
    concept edge_type = std::is_base_of_v<edge_base, edge>;
    template<typename edge>
    concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}
#endif // CP_ALGO_GRAPH_EDGE_TYPES_HPP

#line 1 "cp-algo/graph/edge_types.hpp"


#include <iostream>
#include <cstdint>
namespace cp_algo::graph {
    using node_index = int;
    struct edge_base {
        int xor_nodes;

        edge_base() {}
        edge_base(node_index from, node_index to): xor_nodes(from ^ to) {}

        // Given one endpoint, return the other
        node_index traverse(node_index from) const {
            return xor_nodes ^ from;
        }

        static auto read(node_index v0 = 0) {
            node_index u, v;
            std::cin >> u >> v;
            u -= v0;
            v -= v0;
            return std::pair{u, edge_base(u, v)};
        }
    };

    struct weighted_edge: edge_base {
        int64_t w;

        weighted_edge() {}
        weighted_edge(node_index from, node_index to, int64_t w): edge_base(from, to), w(w) {}

        static auto read(node_index v0 = 0) {
            auto [u, e] = edge_base::read(v0);
            int64_t w;
            std::cin >> w;
            return std::pair{u, weighted_edge(u, e.traverse(u), w)};
        }
    };

    template<typename edge>
    concept edge_type = std::is_base_of_v<edge_base, edge>;
    template<typename edge>
    concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}

#ifndef CP_ALGO_GRAPH_EDGE_TYPES_HPP
#define CP_ALGO_GRAPH_EDGE_TYPES_HPP
#include <iostream>
#include <cstdint>
namespace cp_algo::graph{ using node_index=int; struct edge_base{ int xor_nodes; edge_base(){} edge_base(node_index from,node_index to):xor_nodes(from^to){} node_index traverse(node_index from)const{ return xor_nodes^from; } static auto read(node_index v0=0){ node_index u,v; std::cin>>u>>v; u-=v0; v-=v0; return std::pair{u,edge_base(u,v)}; } }; struct weighted_edge:edge_base{ int64_t w; weighted_edge(){} weighted_edge(node_index from,node_index to,int64_t w):edge_base(from,to),w(w){} static auto read(node_index v0=0){ auto[u,e] =edge_base::read(v0); int64_t w; std::cin>>w; return std::pair{u,weighted_edge(u,e.traverse(u),w)}; } }; template<typename edge> concept edge_type=std::is_base_of_v<edge_base,edge>; template<typename edge> concept weighted_edge_type=std::is_base_of_v<weighted_edge,edge>; }
#endif

#line 1 "cp-algo/graph/edge_types.hpp"
#include <iostream>
#include <cstdint>
namespace cp_algo::graph{ using node_index=int; struct edge_base{ int xor_nodes; edge_base(){} edge_base(node_index from,node_index to):xor_nodes(from^to){} node_index traverse(node_index from)const{ return xor_nodes^from; } static auto read(node_index v0=0){ node_index u,v; std::cin>>u>>v; u-=v0; v-=v0; return std::pair{u,edge_base(u,v)}; } }; struct weighted_edge:edge_base{ int64_t w; weighted_edge(){} weighted_edge(node_index from,node_index to,int64_t w):edge_base(from,to),w(w){} static auto read(node_index v0=0){ auto[u,e] =edge_base::read(v0); int64_t w; std::cin>>w; return std::pair{u,weighted_edge(u,e.traverse(u),w)}; } }; template<typename edge> concept edge_type=std::is_base_of_v<edge_base,edge>; template<typename edge> concept weighted_edge_type=std::is_base_of_v<weighted_edge,edge>; }

Back to top page