Map Set/Get Requests into C++ Class/Structure Changes

AutoMapper behaviour changes with a POST

Sorry I was being silly and letting the complexity get the better of me.

I use a transaction attribute, to persist the information in OnActionExecuted.

So what I was doing was > loading the model > modifing it > then loading it again and trying to map it before it had even been persisted.

I know that nHibernate really doesn't like it when you try and do things like that, so I think the in memory object graph was in a state of flux (pending commit), which was affecting the mapping.

I have change my logic to rather do an ActionRedirect after the update, which has resolved the mapping issue.

Much happier all around.

Time complexity/performance of edge and vertex properties in Boost Graph

is it guaranteed that access to the name of a vertex and weight of an edge are efficient and fast under random access like so:

Yes. The properties are actually stored inline with the vertex/edge node. A descriptor is effectively a type erased pointer to that node. name_map[*vi] ends up inlining to something like get<N>(*static_cast<storage_node*>(vi)) if you imagine the property storage as a kind of tuple with a get<> accessor¹.

Part of my confusion comes from general std::map characteristic that it too does not support random access

Property maps are not like std::map; They may be consecutive, they may be node-based, ordered, unordered, or even calculated. In fact Boost Property Map maybe closer to the concept of a Lense in some functional programming languages. It is a set of functions that can be used to model (mutable) projections for a given key type.

See also:

• map set/get requests into C++ class/structure changes
• examples like Is it possible to have several edge weight property maps for one graph?,
  and Boost set default edge weight to one

Curiosity Wins... Code Gen

Let's see what code gets generated:

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <fmt/format.h>

using G =
    boost::adjacency_list<boost::listS, // out edges stored as list
                        boost::listS, // vertices stored as list
                        boost::directedS,
                        boost::property<boost::vertex_name_t, std::string>,
                        boost::property<boost::edge_weight_t, double>>;

using V = G::vertex_descriptor;
using E = G::edge_descriptor;

void test(V v, E e, G const& g) {
    auto name   = get(boost::vertex_name, g);
    auto weight = get(boost::edge_weight, g);

    fmt::print("{} {}\n", name[v], weight[e]);
}

int main()
{
    G g;
    E e = add_edge(add_vertex({"foo"}, g), add_vertex({"bar"}, g), {42}, g).first;

    test(vertex(0, g), e, g);
}

Prints

foo 42

But more interestingly, the codegen:

test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&): # @test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&)
  sub rsp, 40
  mov rax, qword ptr [rsp + 64]
  movups xmm0, xmmword ptr [rdi + 24]
  mov rax, qword ptr [rax]
  movaps xmmword ptr [rsp], xmm0
  mov qword ptr [rsp + 16], rax
  mov rcx, rsp
  mov edi, offset .L.str
  mov esi, 6
  mov edx, 173
  call fmt::v7::vprint(fmt::v7::basic_string_view<char>, fmt::v7::format_args)
  add rsp, 40
  ret

You see, no algorithmic overhead, just dereferences.

---

¹ In reality, the properties are stored in a kind of Lisp-like list type that end up behaving similarly to a tuple. Boost Graph predates tuples by considerable time margin. I suppose if you want one can compare it closely to Boost Fusion's map type (which also has a type key).

undirected DFS: how can I provide color maps as exterior properties?

You need to satisfy the exact parameter requirements documented: http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/undirected_dfs.html

This means you /can/ get away with a vector for the vertex colors, but the edge colors need to be in an associative container, because the edge descriptor isn't integral like the vertex descriptor is for your graph type.

std::vector<default_color_type> vertex_color(num_vertices(g));
std::map<graph_t::edge_descriptor, default_color_type> edge_color;

auto idmap = get(vertex_index, g);
auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
auto ecmap = make_assoc_property_map(edge_color);

graph_t::vertex_descriptor const start = 0;

Now you can invoke either the fixed-argument version of the algorithm:

undirected_dfs(g, vis, vcmap, ecmap, start);

Alternatively, invoke the exact same using the named-argument version:

undirected_dfs(g, 
        root_vertex(graph_t::vertex_descriptor(0))
        .visitor(vis)
        .vertex_color_map(vcmap)
        .edge_color_map(ecmap)
    );

DEMO

Live On Coliru

#include <iostream>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

struct my_vertex { int a1; float a2; };
struct my_edge   { int b1; float b2; };

struct detect_loops : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph& g) {
        std::cout << g[source(e,g)].a1 << " -- " << g[target(e,g)].a1 << "\n";
    }
};

typedef adjacency_list<vecS, vecS, undirectedS, my_vertex, my_edge> graph_t;

int main() {
    detect_loops vis;

    graph_t g;

    std::vector<default_color_type> vertex_color(num_vertices(g));
    std::map<graph_t::edge_descriptor, default_color_type> edge_color;

    auto idmap = get(vertex_index, g);
    auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
    auto ecmap = make_assoc_property_map(edge_color);

    graph_t::vertex_descriptor const start = 0;

    undirected_dfs(g, vis, vcmap, ecmap, start);

    undirected_dfs(g, 
            root_vertex(graph_t::vertex_descriptor(0))
            .visitor(vis)
            .vertex_color_map(vcmap)
            .edge_color_map(ecmap)
        );
}

Boost Dynamic Properties with Custom get property

See some options here: map set/get requests into C++ class/structure changes

You can either transform the result of one property map, or you can use a functional property map altogether.

Transforming values:

An example of using dynamic properties to transform a color property is here: Manually colouring of boost's graphs

Functional map:

• How to use boost::graph dijkstra's algorithm if vertex properties are pointers?
• My preference would be to use a member function and bind it using the transform_value_property_map as shown above, e.g. Using boost graph library with a custom class for vertices
• But here is an example using function_property_map as well boost dijkstra_shortest_paths: can't extract (or find?) the path (path contains a cycle)

Note that you also have make_constant_property_map (e.g. Boost Dynamic Properties with Custom get property)

Boost Graphs. Equivalent technique to Inheritance

The "technique equivalent to inheritance" is called "polymorphism" and BGL favours "static polymorphism" (option 2!).

This is the pay-for-what-you-need approach to generic libraries.

You can adapt any type (hierarchy) for use with BGL's static polymorphism though:

• How to Convert Adapt Existing Graphs to BGL

Also use property maps to link the properties (weight, color) to the vertices/edges.

• map set/get requests into C++ class/structure changes

Is it possible to have several edge weight property maps for one graph?

You can compose a property map in various ways. The simplest approach would seem something like:

Using C++11 lambdas with function_property_map

Live On Coliru

#include <boost/property_map/function_property_map.hpp>
#include <iostream>

struct weights_t {
    float weight1, weight2, weight3, weight4;
};

using namespace boost;

int main() {
    std::vector<weights_t> weight_data { // index is vertex id
        { 1,2,3,4 },
        { 5,6,7,8 },
        { 9,10,11,12 },
        { 13,14,15,16 }, 
    };

    auto wmap1 = make_function_property_map<unsigned, float>([&weight_data](unsigned vertex_id) { return weight_data.at(vertex_id).weight1; });
    auto wmap2 = make_function_property_map<unsigned, float>([&weight_data](unsigned vertex_id) { return weight_data.at(vertex_id).weight2; });
    auto wmap3 = make_function_property_map<unsigned, float>([&weight_data](unsigned vertex_id) { return weight_data.at(vertex_id).weight3; });
    auto wmap4 = make_function_property_map<unsigned, float>([&weight_data](unsigned vertex_id) { return weight_data.at(vertex_id).weight4; });

    for (unsigned vertex = 0; vertex < weight_data.size(); ++vertex)
        std::cout << wmap1[vertex] << "\t" << wmap2[vertex] << "\t" << wmap3[vertex] << "\t"<< wmap4[vertex] << "\n";
}

Using C++03 with transform_value_property_map

This is mainly much more verbose:

Live On Coliru

#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>

struct weights_t {
    float weight1, weight2, weight3, weight4;

    weights_t(float w1, float w2, float w3, float w4)
        : weight1(w1), weight2(w2), weight3(w3), weight4(w4)
    { }

    template <int which> struct access {
        typedef float result_type;

        float operator()(weights_t const& w) const { 
            BOOST_STATIC_ASSERT(which >= 1 && which <= 4);
            switch (which) {
                case 1: return w.weight1;
                case 2: return w.weight2;
                case 3: return w.weight3;
                case 4: return w.weight4;
            }
        }
    };
};

using namespace boost;

int main() {
    std::vector<weights_t> weight_data; // index is vertex id
    weight_data.push_back(weights_t(1,2,3,4));
    weight_data.push_back(weights_t(5,6,7,8));
    weight_data.push_back(weights_t(9,10,11,12));
    weight_data.push_back(weights_t(13,14,15,16));

    boost::transform_value_property_map<weights_t::access<1>, weights_t*, float> wmap1 = make_transform_value_property_map(weights_t::access<1>(), &weight_data[0]);
    boost::transform_value_property_map<weights_t::access<2>, weights_t*, float> wmap2 = make_transform_value_property_map(weights_t::access<2>(), &weight_data[0]);
    boost::transform_value_property_map<weights_t::access<3>, weights_t*, float> wmap3 = make_transform_value_property_map(weights_t::access<3>(), &weight_data[0]);
    boost::transform_value_property_map<weights_t::access<4>, weights_t*, float> wmap4 = make_transform_value_property_map(weights_t::access<4>(), &weight_data[0]);

    for (unsigned vertex = 0; vertex < weight_data.size(); ++vertex)
        std::cout << wmap1[vertex] << "\t" << wmap2[vertex] << "\t" << wmap3[vertex] << "\t"<< wmap4[vertex] << "\n";
}

Output

Both samples output

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

Speed of custom Java classes vs. Maps

I'm assuming that we are comparing Map<String, String> to the equivalent custom type like this:

public class CustomObject {
    private String a, b, c;

    public CustomObject(String a, String b, String c) {
        this.a = a; this.b = b; this.c = c;
    }
    public String getA() { return a; }
    public String getB() { return b; }
    public String getC() { return c; }
}

If the operations we are comparing are obj.getA() versus map.get("A"), then the custom map will be faster, probably by 1 to 2 orders of magnitude. Yes ... a lot faster.

On the other hand, if we put the CustomObject instances into a set of "mixed type" objects, whose fields we don't know anything about, then calling getA becomes much more difficult / expensive, and the Map solution is certainly simpler and possible faster too. (It depends on the assumptions you can make.)

---

Also, does the answer change if the set is large?

No. It doesn't change the performance characteristics significantly.

---

Why would anyone ever use a hashmap, then?

The use-cases where it is better / necessary to use a Map are when the set of possible keys are not known at compile time. This means that you can't write the CustomClass as a regular class with hand-written source code.

In fact, in most cases it is the relative code simplicity and robustness of the two approaches that should decide the approach you take. If the keys are static, the obj.getA() approach isn't just faster. It is also more robust, because you can't accidentally write something like map.get("a") instead of map.get("A") ... which will return an unexpected null and could lead to an NPE. If the keys are dynamic / not known at compile time, the map.get("A") is simpler and probably more robust.

---

Related Topics