3

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.

Andrii Tytarenko
  • 121
  • 1
  • 10
  • What did you try so far? What two types of edges (B->B, C->C, and B->C)? – gue Aug 03 '17 at 13:02
  • see the **EDIT**, @gue – Andrii Tytarenko Aug 03 '17 at 13:10
  • and sorry, i made a mistake in title. Of course, I meant two types of nodes, not edges @gue – Andrii Tytarenko Aug 03 '17 at 13:20
  • 2
    How about `class Node; class B : public Node; class C: public Node;` and have Graph store Node pointers? Or maybe `class Node { VertexType* data; /* insert adjancecy here*/}; class VertexType; class B: public VertextType ...` – Aziuth Aug 03 '17 at 13:27
  • I think that probably should work, but in this case I have Node graph where I should write something to detect what the node actually is. In fact it's not a great problem, but I believe that there's a better solution maybe using BGL solutions or just more simple. @Aziuth – Andrii Tytarenko Aug 03 '17 at 13:35
  • 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 Aug 04 '17 at 10:11

1 Answers1

2

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:

enter image description here

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/

sehe
  • 374,641
  • 47
  • 450
  • 633