具有两种节点的图形 [英] Graph with two types of nodes

问题描述

我正在用C ++和Boost Graph Library（BGL）编写一个程序。
我有两个名为Buildings和Contracts的类。我需要制作一个表示它们之间的连接关系的图。所以该图应该有两种类型的顶点（B和C），面向并包括边B-> B，C-> C和B-> C。

1. 有可能吗？
   
   $ b
如果是，如何实施？实际上，我试图避免不同类型节点之间的连接，所以我有两个单独的图。但是由于B和C之间实际存在的关系的实现，使得我的模型变得更加复杂。边B1-> B2表明有必要已经建立B1来构建B2。 C1-> C2实际上是一样的，但就合同而言。 B-> C显示，合约C可以在B楼完成。

解决方案

我已经留下了评论，要求提供目标：






如果您能够描述您遇到的问题，我很乐意展示（几种）方法试图解决。因为在这一点上，我们不太清楚你需要集成的数据结构（我无法想到可以同时具有B-B，C-C，B-C边缘的算法）。在我脑海的顶部，有两张单独的图表，一个将它们连接在一起的隐式图表，或者一张带有可选过滤视图的单一图表。过滤可以通过某种（动态）类型的开关完成，或者可以使用某种外部/侵入索引来完成。





来源。点看起来像这样：

  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/




I'm writing a program using C++ and Boost Graph Library (BGL). I have two classes named Buildings and Contracts. I need to make a graph which represents connection relations between them all. So the graph should have two types of vertices (B and C), be oriented and include edges B->B, C->C and B->C.

1. Is it possible?
2. If yes, how to implement this?

EDIT

Actually, I tried to avoid connections between different type nodes, so I had two separate graphs. But it made my model far more complicated because of implementation of in fact existing relation between B and C. Edge B1->B2 shows that it's necessary to have already built B1 to build B2. C1->C2 is actually the same, but in terms of contracts. B->C shows, that a contract C can be completed in building B.

解决方案

I already left a comment asking for the goal:

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. – sehe 31 mins ago

Regardless of that, you can use boost::variant to do exactly what the question asks (that is, probably an X/Y problem question):

Demo

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);
}

Prints

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

As well as generating graph.dot for the following graph:

The source .dot looks like this:

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 ;
}

And I rendered it online using https://dreampuf.github.io/GraphvizOnline/

这篇关于具有两种节点的图形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！