Cut set of a graph, Boost Graph Library
Here's a quick PoC based on Boost BiMap
typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
smart_map colorMap;
boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);
I've taken a small sample from http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm and you can see it Live On Coliru, output:
c The total flow:
s 15
c flow values:
f 0 1 5
f 0 2 10
f 1 3 5
f 1 4 0
f 2 3 5
f 2 4 5
f 3 5 10
f 4 5 5
ltr: 0 -> 5
ltr: 4 -> 0
ltr: 0 -> 1
ltr: 4 -> 2
ltr: 0 -> 3
ltr: 0 -> 4
rtl: 0 -> 4
rtl: 1 -> 0
rtl: 2 -> 4
rtl: 3 -> 0
rtl: 4 -> 0
rtl: 5 -> 0
Full Listing:
#include <boost/foreach.hpp>
#include <boost/bimap.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>
int main() {
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
listS, vecS, directedS, property<vertex_name_t, std::string>,
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, Traits::edge_descriptor> > > > Graph;
Graph g;
property_map<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g);
property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);
property_map<Graph, edge_residual_capacity_t>::type residual_capacity = get(edge_residual_capacity, g);
typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
smart_map colorMap;
boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);
Traits::vertex_descriptor s, t;
read_dimacs_max_flow(g, capacity, rev, s, t);
std::vector<Traits::edge_descriptor> pred(num_vertices(g));
long flow = edmonds_karp_max_flow(
g, s, t, capacity, residual_capacity, rev,
color_map, &pred[0]);
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::cout << "c flow values:" << std::endl;
graph_traits<Graph>::vertex_iterator u_iter, u_end;
graph_traits<Graph>::out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (capacity[*ei] > 0)
std::cout << "f " << *u_iter << " " << target(*ei, g) << " " << (capacity[*ei] - residual_capacity[*ei])
<< std::endl;
for (auto const& e : colorMap.left) std::cout << "ltr: " << e.first << " -> " << e.second << "\n";
for (auto const& e : colorMap.right) std::cout << "rtl: " << e.first << " -> " << e.second << "\n";
return EXIT_SUCCESS;
}
UPDATE
Using Boost MultiIndex to create a bidirectional mapping:
struct VertexColor {
Traits::vertex_descriptor vertex;
boost::default_color_type color;
};
typedef boost::multi_index_container<
VertexColor,
bmi::indexed_by<
bmi::hashed_non_unique<bmi::tag<struct by_color>, bmi::member<VertexColor, boost::default_color_type, &VertexColor::color> >,
bmi::ordered_unique <bmi::tag<struct by_vertex>, bmi::member<VertexColor, Traits::vertex_descriptor, &VertexColor::vertex> >
>
> smart_map;
Now, using Boost Property Map to model a ReadWritePropertyMap:
struct bidi_color_map {
typedef smart_map::index<by_vertex>::type impl_t;
bidi_color_map(impl_t& ref) : ref_(&ref) {}
impl_t &get() { return *ref_; }
impl_t const &get() const { return *ref_; }
private:
impl_t* ref_;
};
namespace boost {
template <> struct property_traits<bidi_color_map> {
typedef default_color_type value_type;
typedef default_color_type reference;
typedef Traits::vertex_descriptor key_type;
typedef read_write_property_map_tag category;
};
}
boost::property_traits<bidi_color_map>::reference get(bidi_color_map const& idx, boost::property_traits<bidi_color_map>::key_type const& key) {
auto it = idx.get().find(key);
if (it != idx.get().end())
return it->color;
else
throw std::range_error("key not found in index");
}
void put(bidi_color_map& idx, boost::property_traits<bidi_color_map>::key_type const& key, boost::property_traits<bidi_color_map>::value_type val) {
auto it = idx.get().find(key);
if (it != idx.get().end())
idx.get().modify(it, [val](VertexColor& p) { p.color = val; });
else
idx.get().insert({key,val});
}
Now you can just pass that as the colormap:
smart_map colorMap;
bidi_color_map color_map(colorMap.get<by_vertex>());
See it Live On Coliru as well
boost grid_graph and graph cut on image
The problem you have with the other answer is probably caused by an older version of Visual Studio (its code works fine with Visual Studio 2012 Express/g++ 4.8.0 and boost 1.53.0). If that problem is the only one with your compiler it can easily be sidestepped by creating another custom property map similar to the one that uses capacity. The changes required are marked with //ADDED and //CHANGED.
#include <iostream>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/iteration_macros.hpp>
int main()
{
const unsigned int D = 2;
typedef boost::grid_graph<D> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;//ADDED
typedef boost::graph_traits<Graph>::vertices_size_type VertexIndex;
typedef boost::graph_traits<Graph>::edges_size_type EdgeIndex;
boost::array<std::size_t, D> lengths = { { 3, 3 } };
Graph graph(lengths, false);
float pixel_intensity[]={10.0f,15.0f,25.0f,
5.0f,220.0f,240.0f,
12.0f,15.0,230.0f};
std::vector<int> groups(num_vertices(graph));
std::vector<float> residual_capacity(num_edges(graph)); //this needs to be initialized to 0
std::vector<float> capacity(num_edges(graph)); //this is initialized below, I believe the capacities of an edge and its reverse should be equal, but I'm not sure
std::vector<EdgeDescriptor> reverse_edges(num_edges(graph));//ADDED
BGL_FORALL_EDGES(e,graph,Graph)
{
VertexDescriptor src = source(e,graph);
VertexDescriptor tgt = target(e,graph);
VertexIndex source_idx = get(boost::vertex_index,graph,src);
VertexIndex target_idx = get(boost::vertex_index,graph,tgt);
EdgeIndex edge_idx = get(boost::edge_index,graph,e);
capacity[edge_idx] = 255.0f - fabs(pixel_intensity[source_idx]-pixel_intensity[target_idx]); //you should change this to your "gradiant or intensity or something"
reverse_edges[edge_idx]=edge(tgt,src,graph).first;//ADDED
}
VertexDescriptor s=vertex(0,graph), t=vertex(8,graph);
//in the boykov_kolmogorov_max_flow header it says that you should use this overload with an explicit color property map parameter if you are interested in finding the minimum cut
boykov_kolmogorov_max_flow(graph,
make_iterator_property_map(&capacity[0], get(boost::edge_index, graph)),
make_iterator_property_map(&residual_capacity[0], get(boost::edge_index, graph)),
make_iterator_property_map(&reverse_edges[0], get(boost::edge_index, graph)), //CHANGED
make_iterator_property_map(&groups[0], get(boost::vertex_index, graph)),
get(boost::vertex_index, graph),
s,
t
);
for(size_t index=0; index < groups.size(); ++index)
{
if((index%lengths[0]==0)&&index)
std::cout << std::endl;
std::cout << groups[index] << " ";
}
return 0;
}
Working on Coliru.
PS: One thing that the Boost.Graph documentation fails to clarify is that the concept requirements described there apply to the case when you explicitly pass every one of the arguments. Some of the default arguments may introduce further requirements.
How to efficiently use boost graph
1 - how can i use setS instead of vecS to avoid checking is a
Q.: vertex/edge exists. when i do so, the write_graphiz function complains
that it fails with lots of errors beginning with
Sure. In fact the edge selector is no problem to begin with: https://godbolt.org/z/b1xbYMM4s. Making the vertex containter setS won't do what you mean, because every added vertex is unique by definition.
But in the interest of showing the technical issue at hand: there is no implicit vertex index (ordinal numbering [0..numvertices()) for that storage strategy. Some algorithms require one. Also, you assume one with VertexLabelArray_ which no longer makes sense, so let's change into VertexLabelMap_ just like for edge labels:
Live On Compiler Explorer
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex {
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelMap_.emplace(vertex, name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> src, std::shared_ptr<Vertex> dst,
std::shared_ptr<Edge> weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
std::map<VertexDesc, int> idmap;
for (auto v : boost::make_iterator_range(vertices(graph_))) {
idmap.emplace(v, idmap.size());
}
write_graphviz(out, graph_,
boost::make_label_writer(
boost::make_assoc_property_map(vertexLabelMap_)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{},
boost::make_assoc_property_map(idmap));
}
private:
std::map<VertexDesc, std::string> vertexLabelMap_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
Alternatively, if such an index can be made part of Vertex:
Live On Compiler Explorer
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex {
int id;
std::string name;
};
struct Edge {
std::string name;
};
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;
void addNode(std::shared_ptr<Vertex> const& node)
{
const auto name = node->name;
if (vertexMap_.find(name) == vertexMap_.end()) {
const auto vertex = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = vertex;
}
}
void addEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& weight = nullptr)
{
const auto srcName = src->name;
const auto dstName = dst->name;
const auto vertexPair = std::make_pair(srcName, dstName);
if (edgeSet_.find(vertexPair) == edgeSet_.end()) {
addNode(src);
addNode(dst);
const auto edge = add_edge(vertexMap_[srcName], vertexMap_[dstName],
weight, graph_)
.first;
edgeSet_.insert(vertexPair);
edgeLabelMap_[edge] = weight ? weight->name : "";
}
}
void print(std::ostream& out)
{
auto idmap = boost::make_transform_value_property_map(
[](auto const& sp) { return sp->id; },
get(boost::vertex_bundle, graph_));
write_graphviz(
out, graph_,
boost::make_label_writer(boost::make_iterator_property_map(
vertexLabelArray_.begin(), idmap)),
boost::make_label_writer(
boost::make_assoc_property_map(edgeLabelMap_)),
boost::default_writer{}, idmap);
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
std::set<std::pair<std::string, std::string>> edgeSet_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{0, "n1"}});
const auto n2 = std::make_shared<Node>(Node{{1, "n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.addEdge(n1, n2, e1);
g.print(std::cout);
}
Q.: 2 - i am using a shared_ptr for allowing for custom object to be
attached to vertices and edges.
I noticed this. I think it's a little bit questionable. If you're looking for efficiency, I wouldn't be using shared_ptr all over the place.
Q.: is there an easy way for looking up a
vertex index based on its attached object?
Not built in. There is the (undocumented?) labeled_graph adaptor that has... some convenience. YMMV. Also, you can use a bimap or similar.
Q.: 3 - Is it possible to remove most of the external data structures and
use boost property instead somehow?
I would strongly consider this. Of course you can. Basically, you already do this.
Review
Your code has many opportunities for improvement (including effective optimizations).
pass the shared pointers by
const&:do not pass shared pointers in the first place, since you're not intending to share ownership/observe refcounts/lifetimes. I'll show this when I show a version that embodies the node/edge data in the graph model directly.
void addNodecould return the vertex descriptor, avoiding a lot of redundant lookups. This also makes it more explicit about an item already existing not being an error. (Right now it simply ignores theaddNode/addEdge?)void ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
if (edgeSet_.emplace(src->name, dst->name).second) {
auto [descriptor, isnew] = add_edge( //
ensureNode(src), ensureNode(dst), edge, graph_);
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
}
}Doing less work means being more efficient.
Like you almost mentioned you can already test whether an edge exists using the result of
add_edge, obviating the extraedgeSet_:EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), edge, graph_);
if (isnew)
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
return descriptor;
}Note that now, because the behaviour is more consistent, we can also return the edge descriptor. This will remove the need to query for the edge we just added.
Current version Live On Compiler Explorer:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
MyGraph() = default;
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::bidirectionalS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(std::shared_ptr<Vertex> const& node)
{
auto const& name = node->name;
auto it = vertexMap_.find(name);
if (it == vertexMap_.end()) {
auto descriptor = add_vertex(node, graph_);
vertexLabelArray_.push_back(name);
vertexMap_[name] = descriptor;
it = vertexMap_.emplace(name, descriptor).first;
}
return it->second;
}
EdgeDesc ensureEdge(std::shared_ptr<Vertex> const& src,
std::shared_ptr<Vertex> const& dst,
std::shared_ptr<Edge> const& edge = {})
{
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), edge, graph_);
if (isnew)
edgeLabelMap_.emplace(descriptor, edge ? edge->name : "");
return descriptor;
}
void print(std::ostream& out) const
{
write_graphviz(
out, graph_, //
boost::make_label_writer(vertexLabelArray_.data()),
boost::make_label_writer(make_assoc_property_map(edgeLabelMap_)));
}
private:
std::vector<std::string> vertexLabelArray_;
std::map<EdgeDesc, std::string> edgeLabelMap_;
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex {};
struct Arc : Edge {};
#include <iostream>
int main() {
MyGraph g;
const auto n1 = std::make_shared<Node>(Node{{"n1"}});
const auto n2 = std::make_shared<Node>(Node{{"n2"}});
const auto e1 = std::make_shared<Arc>(Arc{{"e1"}});
g.ensureEdge(n1, n2, e1);
g.print(std::cout);
}
Still prints
digraph G {
0[label=n2];
1[label=n1];
1->0 [label=e1];
}
Other Steps
You specified
BidirectionalGraphsupport, but don't currently use the in-edge interface. Consider dropping that so you don't incur the overhead for maintaining the redundant edge informationusing Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::directedS,
std::shared_ptr<Vertex>, std::shared_ptr<Edge>>;Consider using value semantics for the property bundles. This will reduce allocations, increase locality of reference and may enable a host of storage optimization opportunities.
Consider this version, which no longer uses
vertexLabelArray_noredgeLabelMap_(both properties simply reside inside the graph model after all):void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)));
}
Live On Compiler Explorer
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto descriptor = add_vertex(node, graph_);
vertexMap_[node.name] = descriptor;
vertexMap_.emplace(node.name, descriptor);
return descriptor;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [descriptor, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return descriptor; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)));
}
private:
std::map<std::string, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
Prints
digraph G {
0[label=n2];
1[label=n1];
2[label=n4];
3[label=n3];
1->0 [label=e1];
3->2 [label=e2];
}
Much More Efficient Vertex Lookup?
If you really care about storage and lookup efficiency, make vertexMap_ key a string_view. This requires careful thought about the lifetime of the referred-to strings.
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
For starters, you NEED a container selector with reference stabiility for the vertex container (e.g. listS).
Also, consider making the container a flat_map so storage and lookup will be much optimized. They will effectively become vector<tuple<char const*, size_t, size_t> >:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
See It Live On Compiler Explorer
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct Vertex { std::string name; };
struct Edge { std::string name; };
class MyGraph {
public:
using Graph = boost::adjacency_list< //
boost::setS, boost::listS, boost::directedS, Vertex, Edge>;
using VertexDesc = Graph::vertex_descriptor;
using EdgeDesc = Graph::edge_descriptor;
VertexDesc ensureNode(Vertex const& node) {
if (auto it = vertexMap_.find(node.name); it != vertexMap_.end())
return it->second;
auto vd = add_vertex(node, graph_);
// use stored property, not parameter as vertexMap_ key!
vertexMap_.emplace(graph_[vd].name, vd);
return vd;
}
EdgeDesc ensureEdge(Vertex const& src, Vertex const& dst, Edge edge) {
auto [ed, isnew] =
add_edge(ensureNode(src), ensureNode(dst), std::move(edge), graph_);
return ed; // TODO maybe raise an error if !isnew?
}
void print(std::ostream& out) const {
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{},
get(&Vertex::name, graph_));
}
private:
boost::container::flat_map<std::string_view, VertexDesc> vertexMap_;
Graph graph_;
};
struct Node : Vertex { };
struct Arc : Edge { };
#include <iostream>
int main() {
MyGraph g;
Node n1{{"n1"}}, n2{{"n2"}};
Arc e1{{"e1"}};
g.ensureEdge(n1, n2, e1);
g.ensureEdge({"n3"}, {"n4"}, {"e2"});
g.print(std::cout);
}
Note this cheated a little by using the Vertex name as the graphviz node ID. That makes a lot of sense anyways:
digraph G {
n2[label=n2];
n1[label=n1];
n4[label=n4];
n3[label=n3];
n1->n2 [label=e1];
n3->n4 [label=e2];
}
If you insist on integral IDs - you can hack them back using the fact that vertexMap_ is now contiguous:
void print(std::ostream& out) const {
auto node_id = boost::make_function_property_map<VertexDesc>(
[this](VertexDesc vd) {
return vertexMap_.find(graph_[vd].name) - vertexMap_.begin();
});
write_graphviz(out, graph_,
make_label_writer(get(&Vertex::name, graph_)),
make_label_writer(get(&Edge::name, graph_)),
boost::default_writer{}, node_id);
}
This prints (Live Link):
digraph G {
1[label=n2];
0[label=n1];
3[label=n4];
2[label=n3];
0->1 [label=e1];
2->3 [label=e2];
}
Note that doing the
listSvertex container selection makes a BIG difference in resource trade-offs in the graph implementation itself, so if the vertex lookup viavertexMap_is not your bottleneck, don't do this optimization!
More BGL facilities
As I mentioned there's some supported for labeled graphs in BGL. I'm not recommending that as I've run into my share of implementation bugs/quirks. But I would be remiss not to mention it here.
Also see How to create a named_graph with Boost Graph Library? which is a very good answer
Using boost graph library with a custom class for vertices
without changing your declarations, this is a bit painful, but possible:
{
boost::dynamic_properties dp;
boost::property_map<graph_t, boost::vertex_my_custom_class_t>::type custom = get(boost::vertex_my_custom_class, graph);
dp.property("node_id", boost::make_transform_value_property_map(std::mem_fn(&my_custom_class::get_int), custom));
dp.property("label", boost::make_transform_value_property_map(std::mem_fn(&my_custom_class::get_my_string), custom));
boost::write_graphviz_dp(std::cout, graph, dp);
}Printing: Live On Coliru
digraph G {
123 [label=Lorem];
456 [label=ipsum];
123 [label=Lorem];
123->456 ;
123->123 ;
}You will want to take care of this externally. Why not have an intrusive set of nodes and verify the contraints that way. Changing the Vertex Container Selector as you say has no effect (it just ends up storing the vertex descriptors in ascending order, while they stay unique as they were before).
A side effect is changing from contiguously allocated vertex storage to node-based (pro: iterator/reference stability, con: allocation overhead, reduced locality of reference, non-implicit vertex_index).
Related Topics
C++ Function for Picking from a List Where Each Element Has a Distinct Probability
Ramifications of C++20 Requiring Two's Complement
Remote Debugging C++ Applications with Eclipse Cdt/Rse/Rdt
What Is the Purpose of the _Chkstk() Function
Inconsistent Strcmp() Return Value When Passing Strings as Pointers or as Literals
Does One Double Promote Every Int in the Equation to Double
Why Does a Virtual Function Get Hidden
Using Boost Adaptors with C++11 Lambdas
Auto' as a Template Argument Placeholder for a Function Parameter
How Exactly Is Std::String_View Faster Than Const Std::String&