通过移除叶子来制作增强图的子图

Question

我有一个类型为 vecS 的 BGL 图。我想通过移除叶子来制作它的新图表。我需要它主要是为了可视化，因为有很多叶子我不需要可视化。据此 post c++ remove vertex from a graph BGL page 从 vecS 邻接表中删除顶点是不安全的。那么在我有一个 vecS 图的情况下，解决方案是什么？我如何制作没有叶子的新图表。

    /// vertex properties
struct VertexData
{
    std::string label;
    int num;
    bool is_leaf=false;
};

/// edges properties
struct EdgeData
{
    std::string edge_name;
    double edge_confidence;
};

/// define the boost-graph
typedef boost::adjacency_list<boost::vecS, boost::vecS,
        boost::bidirectionalS,
        boost::property<boost::vertex_index_t , size_t , VertexData>,
        boost::property<boost::edge_weight_t, double, EdgeData> > Graph;

感谢您的回答。

PS。是否可以使用 predicate 和 filtered_graph？

Answer 1

你有一个布尔标志来指示什么是叶子，这有点令人惊讶。在图的本质上，假设叶子是任何出度为 0 的顶点似乎是合乎逻辑的。

无论：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>

/// vertex properties
struct VertexData {
    std::string label;
    int num;
    bool is_leaf=false;
};

/// edges properties
struct EdgeData {
    std::string edge_name;
    double edge_confidence;
};

/// define the boost-graph
typedef boost::adjacency_list<boost::vecS, boost::vecS,
        boost::bidirectionalS,
        boost::property<boost::vertex_index_t, size_t, VertexData>,
        boost::property<boost::edge_weight_t, double, EdgeData> > Graph;

using Predicate = std::function<bool(Graph::vertex_descriptor)>;
using Filtered  = boost::filtered_graph<Graph, boost::keep_all, Predicate>;

Graph make_graph();

int main() {
    Graph g = make_graph();
    auto const labels = get(&VertexData::label, g);

    std::cout << "\n---Main graph:\n";
    print_graph(g, labels);

    // manual markings
    {
        auto manual_is_leaf = [&g](Graph::vertex_descriptor vd) { return !g[vd].is_leaf; };
        Filtered manual(g, boost::keep_all{}, manual_is_leaf);

        {

            std::cout << "\n---Filtered, no leafs:\n";
            print_graph(manual, labels);
        }

        {
            std::cout << "\n---Filtered, manual leafs:\n";
            g[2].is_leaf = true; // only "three"

            print_graph(manual, labels);
        }
    }

    // automatic, dynamic markings
    {
        // note that for bidirectional/undirected out_degree might not make
        // sense, but neither does the notion of a leaf! 
        auto by_degree = [&g](Graph::vertex_descriptor vd) { return boost::out_degree(vd, g); };
        Filtered automatic(g, boost::keep_all{}, by_degree);

        {
            std::cout << "\n---Filtered by actual out_degree:\n";
            print_graph(automatic, labels);
        }

        {
            // make `five` and `six` appear:
            add_edge(5, 4, 100, g); // six -> five

            std::cout << "\n---After adding an edge:\n";
            print_graph(automatic, labels);
        }
    }
}

Graph make_graph() {
    Graph g;

    auto v1 = add_vertex({ 1, {"one",   100, false} }, g);
    auto v2 = add_vertex({ 2, {"two",   200, false} }, g);
    auto v3 = add_vertex({ 3, {"three", 300, false} }, g);
    auto v4 = add_vertex({ 4, {"four",  400, false} }, g);
    auto v5 = add_vertex({ 5, {"five",  500, false} }, g);
    auto v6 = add_vertex({ 6, {"six",   600, false} }, g);

    add_edge(v1, v2, 0.5, g);
    add_edge(v2, v3, 0.5, g);
    add_edge(v3, v4, 0.5, g);
    add_edge(v3, v5, 0.5, g);
    add_edge(v3, v6, 0.5, g);
    add_edge(v2, v4, 0.5, g);
    add_edge(v3, v5, 0.5, g);
    add_edge(v4, v6, 0.5, g);

    return g;
}

版画

---Main graph:
one --> two 
two --> three four 
three --> four five six five 
four --> six 
five --> 
six --> 

---Filtered, no leafs:
one --> two 
two --> three four 
three --> four five six five 
four --> six 
five --> 
six --> 

---Filtered, manual leafs:
one --> two 
two --> four 
four --> six 
five --> 
six --> 

---Filtered by actual out_degree:
one --> two 
two --> three four 
three --> four 
four --> 

---After adding an edge:
one --> two 
two --> three four 
three --> four six 
four --> six 
six -->

NOTE

Replace boost::out_degree with boost::degree if you want to be more "true" to the nature of bidirectional/undirected graphs (see the comment). In that case you will see all vertices in the automatic section, because all vertices are connected with some edge.

通过移除叶子来制作增强图的子图

Make a subgraph of a boost graph by removing leaves

boost

boost-graph

c++11

NOTE