具有两种类型节点的图

Question

我正在使用 C++ 和 Boost 图形库 (BGL) 编写程序。我有两个类命名为 Buildings 和 Contracts。我需要制作一个图表来表示它们之间的连接关系。因此该图应该有两种类型的顶点（B 和 C），是有方向的并且包括边 B->B、C->C 和 B->C。

可能吗？
如果是，如何实现？

编辑

实际上，我试图避免不同类型节点之间的连接，所以我有两个单独的图。但它使我的模型变得更加复杂，因为 B 和 C 之间实际上存在关系的实现。边 B1->B2 表明必须已经构建 B1 才能构建 B2。 C1->C2 其实也是一样的，不过是在契约方面。 B->C 表明，合同 C 可以在建筑 B 中完成。

Answer 1

我已经留言询问目标：

I'd be happy to show (several) approaches iff you would be able to describe the problem you're trying to solve. Because at this point it's not at all clear what you'd require the integrated datastructure for (I'm unable to think of algorithms that would benefit from having both the B-B, C-C, B-C edges.). Off the top of my mind 2 separate graphs, an implicit graph that conjoins them, or a single graph with optionally filtered views would do. Filtering could be done by some kind of (dynamic) type switch OR it could be done using some kind of external/intrusive index.

无论如何，您可以使用 boost::variant 来完全问题所问的内容（也就是说，可能是 X/Y problem 问题）：

演示

Live On Wandbox

#include <boost/graph/adj_list_serialize.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/variant.hpp>
#include <fstream>
using namespace boost;

namespace Nodes {
    struct Building { std::string id; };
    struct Contract { std::string id; };

    static inline std::ostream& operator<<(std::ostream& os, Building const& b) { return os << "Building " << b.id; }
    static inline std::ostream& operator<<(std::ostream& os, Contract const& b) { return os << "Contract " << b.id; }

    std::string id_of(Building const& b) { return b.id; }
    std::string id_of(Contract const& c) { return c.id; }
    std::string shape_of(Building const& b) { return "circle"; }
    std::string shape_of(Contract const& c) { return "diamond"; }
}

using Nodes::Building;
using Nodes::Contract;
using Vertex = boost::variant<Building, Contract>;

std::string id_of(Vertex const& v) {
    return boost::apply_visitor([](auto const& node) { return id_of(node); }, v);
}
std::string shape_of(Vertex const& v) {
    return boost::apply_visitor([](auto const& node) { return shape_of(node); }, v);
}

typedef adjacency_list<vecS, vecS, directedS, Vertex> Graph;

int main() {
    Graph g;
    auto office1    = add_vertex(Building{ "office1" }, g);
    auto office2    = add_vertex(Building{ "office2" }, g);
    auto warehouse1 = add_vertex(Building{ "warehouse1" }, g);
    auto contract1  = add_vertex(Contract{ "contract1" }, g);
    auto contract2  = add_vertex(Contract{ "contract2" }, g);

    add_edge(office1, office2, g);
    add_edge(warehouse1, contract1, g);
    add_edge(contract2, contract1, g);

    {
        std::ofstream dot_file("graph.dot");
        dynamic_properties dp;

        dp.property("node_id", boost::make_transform_value_property_map(&::id_of, boost::get(boost::vertex_bundle, g)));
        dp.property("shape", boost::make_transform_value_property_map(&::shape_of, boost::get(boost::vertex_bundle, g)));
        dp.property("label", boost::make_transform_value_property_map(
            [](Vertex const& v) { return boost::lexical_cast<std::string>(v); },
            boost::get(boost::vertex_bundle, g)));

        write_graphviz_dp(dot_file, g, dp);
    }

    print_graph(g);
}

版画

0 --> 1
1 -->
2 --> 3
3 -->
4 --> 3

以及为下图生成 graph.dot：

源 .dot 如下所示：

digraph G {
office1 [label="Building office1", shape=circle];
office2 [label="Building office2", shape=circle];
warehouse1 [label="Building warehouse1", shape=circle];
contract1 [label="Contract contract1", shape=diamond];
contract2 [label="Contract contract2", shape=diamond];
office1->office2 ;
warehouse1->contract1 ;
contract2->contract1 ;
}

我使用 https://dreampuf.github.io/GraphvizOnline/

在线渲染了它

具有两种类型节点的图

Graph with two types of nodes

c++

boost

graph

boost-graph

演示