graph subgraph isomorphism with weighted vertexes
Firstly i am a complete newbie in boost lib. There is boost graph library isomorphism program without weights.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/algorithm/cxx11/all_of.hpp>
#include <iostream>
#include <random>
using namespace std;
using namespace boost;
using boost::make_iterator_range;
using boost::adaptors::transformed;
using boost::algorithm::all_of;
int main()
{
typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
int temp, networkSIZE, clusterSIZE;
// Build graph1
cout << "input cluster size" << endl;
cin >> clusterSIZE;
graph_type graph1(clusterSIZE);
add_edge(0, 6, graph1); add_edge(0, 7, graph1);
add_edge(1, 5, graph1); add_edge(1, 7, graph1);
add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
add_edge(3, 4, graph1);
// Build graph2
cout << "input network size" << endl;
cin >> networkSIZE;
graph_type graph2(networkSIZE);
add_edge(0, 6, graph2); add_edge(0, 8, graph2);
add_edge(1, 5, graph2); add_edge(1, 7, graph2);
add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
// Create callback to print mappings
vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
// Print out all subgraph isomorphism mappings between graph1 and graph2.
// Vertices and edges are assumed to be always equivalent.
bool found = vf2_subgraph_iso(graph1, graph2, callback);
std::cout << "Found subgraph:" << std::boolalpha << found << std::endl;
}
How can i find subgraph ismomorphism with weighted vertexes(i mean maximum weighted subgraph) using boost library and can i do it at all using this library. If no is there any library of any language where i can do it. If no and there are no libraries. Can you please give me atleast complete implementation of Ullman or VF2 or Cordella or Bonicci algorithms because I cannot find an adequate and more or less compact and simple implementation of these algorithms. maybe i will modernise it with weights
I solved isomorphism task with weighted verteces and wrote a working program using simple c++, but I need a serious efficient algorithm
Solution
Here's my take on things.
To the best of my knowledge it is not possible to cause vf2_subgraph_iso to consider vertices from the large graph in any preferential order. There is the VertexOrderSmall argument though in case you can leverage it to arrive at the best mapping(s) sooner.
So, what you can do is to generate multiple mappings. Just to show off some of the flexibilities, I decided to not only generate all mappings, but also render them as DOT renderings of a tree of (sub)graphs where the "root" graph contains all of the large graph, and the "child" graph contains just the mapped isomorphism with weigths, descriptors.
I assumed, for the sake of exposition that by "maximum weighted subgraph" you were referring to edge weights.
Without further ado:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>
using boost::make_iterator_range;
// I cannot make up random weights well
#include <random>
// The things we do for pretty renderings...
#include <boost/graph/copy.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/subgraph.hpp>
namespace Dot { // lot of noise just to render pretty graphs
using namespace boost;
using Dict = std::map<std::string, std::string>;
template <typename Base>
using Wrap = adjacency_list<
setS, vecS, bidirectionalS,
property<vertex_attribute_t, Dict, typename vertex_property_type<Base>::type>, // vertex
property<edge_index_t, int,
property<edge_attribute_t, Dict,
typename edge_property_type<Base>::type>>, // edge
property<graph_name_t, std::string, // graph
property<graph_graph_attribute_t, Dict,
property<graph_vertex_attribute_t, Dict,
property<graph_edge_attribute_t, Dict,
typename graph_property_type<Base>::type>>>>>;
} // namespace Dot
static int s_dotfile_counter = 0;
template <typename Graph, typename Map>
static auto createRendering(Graph const& small, Graph const& large, Map correspondence) {
using RenderTree = boost::subgraph<Dot::Wrap<Graph>>;
using RV = typename RenderTree::vertex_descriptor;
// Render (sub)graph isomorphism map
RenderTree root;
auto& sub = root.create_subgraph();
get_property(sub, boost::graph_name) = "clusterSmall";
get_property(root, boost::graph_name) = "large";
// copy all of large graph into root
auto ignore = [&](auto...) {};
auto copy_prop = [](auto tag, auto& src_graph, auto& tgt_graph) {
return [&, tag](auto src_descr, auto tgt_descr) {
put(tag, tgt_graph, tgt_descr, get(tag, src_graph, src_descr));
};
};
std::vector<RV> copy_map(num_vertices(large));
copy_graph(
large, root,
boost::vertex_copy(ignore)
.edge_copy(copy_prop(boost::edge_weight, large, root))
.orig_to_copy(make_iterator_property_map(copy_map.begin(), get(boost::vertex_index, small))));
// mark sub-graph vertices
for (auto largev : make_iterator_range(vertices(large))) {
auto small_v = get(correspondence, largev);
auto root_v = copy_map[largev];
if (small_v != small.null_vertex()) {
auto sub_v = add_vertex(root_v, sub);
// auto sub_v = sub.global_to_local(root_v);
std::ostringstream label;
label << "{small:" << small_v << " | large:" << largev << "}";
put(boost::vertex_attribute, sub, sub_v,
Dot::Dict{
{"label", label.str()},
{"color", "green"},
});
} else {
std::ostringstream label;
label << "{large:" << largev << "}";
put(boost::vertex_attribute, root, root_v,
Dot::Dict{
{"label", label.str()},
{"color", "gray"},
});
}
}
double total_weight = 0;
{ // write .dot and render png, calculating total_weight
std::string const fname = "dot" + std::to_string(++s_dotfile_counter);
get_property(root, boost::graph_vertex_attribute)["shape"] = "Mrecord";
for (auto e : make_iterator_range(edges(root))) {
double w = get(boost::edge_weight, root, e);
std::ostringstream label;
label << "weight:" << std::fixed << std::setprecision(2) << w;
put(boost::edge_attribute, root, e, Dot::Dict{{"label", label.str()}});
if (sub.find_edge(e).second)
total_weight += w;
}
get_property(sub, boost::graph_graph_attribute) //
["label"] = "total weight: " + std::to_string(total_weight);
{
std::ofstream ofs(fname + ".dot");
write_graphviz(ofs, root);
}
if (::system(("dot -Tpng '" + fname + ".dot' -o '" + fname + ".png'").c_str())) {
std::cerr << "(couldn't not invokge graphviz dot tool)" << std::endl;
}
}
return total_weight;
}
int main() {
using Graph = boost::adjacency_list< //
boost::setS, boost::vecS, boost::bidirectionalS, //
boost::no_property, // vertex
boost::property<boost::edge_weight_t, double>>; // edge
// Build smaller graph (graph1)
Graph small, large;
add_edge(0, 6, small);
add_edge(0, 7, small);
add_edge(1, 5, small);
add_edge(1, 7, small);
add_edge(2, 4, small);
add_edge(2, 5, small);
add_edge(2, 6, small);
add_edge(3, 4, small);
// Build larger graph (graph2)
auto gen_weight = bind(std::uniform_real_distribution(0.1, 2.9), std::mt19937(42));
add_edge(0, 6, gen_weight(), large);
add_edge(0, 8, gen_weight(), large);
add_edge(1, 5, gen_weight(), large);
add_edge(1, 7, gen_weight(), large);
add_edge(2, 4, gen_weight(), large);
add_edge(2, 7, gen_weight(), large);
add_edge(2, 8, gen_weight(), large);
add_edge(3, 4, gen_weight(), large);
add_edge(3, 5, gen_weight(), large);
add_edge(3, 6, gen_weight(), large);
// Create callback to print mappings
using V = Graph::vertex_descriptor;
std::map<V, V> mapping;
double best_weight = -INFINITY;
auto callback = [&](auto f, auto f_inv) {
auto w = createRendering(small, large, f_inv);
std::cout << "found isomorphism mapping with total weight of " << w << "\n";
if (w > best_weight) {
best_weight = w;
for (mapping.clear(); auto v : make_iterator_range(vertices(small)))
mapping.emplace(v, f[v]);
}
return true; // give us more isomorphisms if any
};
if (vf2_subgraph_iso(small, large, callback)) {
std::cout << " best weight: " << best_weight << " mapping:";
for (auto [s,l] : mapping)
std::cout << " [" << s << ", " << l <<"]";
std::cout << "\n";
} else {
std::cout << "no isomorphisms\n";
}
}
Prints, e.g.:
found isomorphism mapping with total weight of 11.5698
found isomorphism mapping with total weight of 11.5698
found isomorphism mapping with total weight of 9.3165
found isomorphism mapping with total weight of 9.3165
found isomorphism mapping with total weight of 11.4182
found isomorphism mapping with total weight of 11.4182
found isomorphism mapping with total weight of 10.7861
found isomorphism mapping with total weight of 10.7861
best weight: 11.5698 mapping: [0, 1] [1, 2] [2, 3] [3, 0] [4, 6] [5, 4] [6, 5] [7, 7]
Note the pairs of equal weights are caused by the same vertex being omitted from the selection:
Those images were generated by DOT from graphviz files written like e.g. dot5.dot:
digraph large {
node [
shape=Mrecord];
subgraph clusterSmall {
graph [
label="total weight: 11.418200"];
0[color=green, label="{small:0 | large:0}"];
1[color=green, label="{small:3 | large:1}"];
2[color=green, label="{small:1 | large:2}"];
3[color=green, label="{small:2 | large:3}"];
4[color=green, label="{small:5 | large:4}"];
5[color=green, label="{small:4 | large:5}"];
6[color=green, label="{small:6 | large:6}"];
8[color=green, label="{small:7 | large:8}"];
2 -> 4[label="weight:1.35"];
3 -> 4[label="weight:1.03"];
1 -> 5[label="weight:2.28"];
3 -> 5[label="weight:0.50"];
0 -> 6[label="weight:2.33"];
3 -> 6[label="weight:1.92"];
0 -> 8[label="weight:0.61"];
2 -> 8[label="weight:1.39"];
}
7[color=gray, label="{large:7}"];
1 -> 7[label="weight:1.77"];
2 -> 7[label="weight:0.38"];
}
UPDATE: Node Weights
To the comments, if you preferred node weights instead of edge weights, that's just simpler, because we don't have to figure out which edges belong in the isomorphism anymore:
Live On Coliru (that's the version posted in the comment)
Live On Coliru Version further simplified (157 lines) and generalized:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>
#include <cstdint>
using boost::make_iterator_range;
// I cannot make up random values well
#include <random>
// The things we do for pretty renderings...
#include <boost/graph/copy.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/subgraph.hpp>
namespace Dot { // lot of noise just to render pretty graphs
using namespace boost;
using Dict = std::map<std::string, std::string>;
template <typename Base>
using Wrap = adjacency_list<
setS, vecS, bidirectionalS, property<vertex_attribute_t, Dict>, // vertex
property<edge_index_t, int, property<edge_attribute_t, Dict>>, // edge
property<graph_name_t, std::string, // graph
property<graph_graph_attribute_t, Dict,
property<graph_vertex_attribute_t, Dict, property<graph_edge_attribute_t, Dict>>>>>;
} // namespace Dot
static int s_dotfile_counter = 0;
template <typename Graph, typename Map, typename NodeWeight>
static auto createRendering(Graph const& small, Graph const& large, Map correspondence, NodeWeight nweight) {
using RenderTree = boost::subgraph<Dot::Wrap<Graph>>;
using RV = typename RenderTree::vertex_descriptor;
// Render (sub)graph isomorphism map
RenderTree root;
auto& sub = root.create_subgraph();
get_property(sub, boost::graph_name) = "clusterSmall";
get_property(root, boost::graph_name) = "large";
// copy all of large graph into root
std::vector<RV> copy_map(num_vertices(large));
static constexpr auto ignore = [](auto...) {};
copy_graph(large, root,
boost::vertex_copy(ignore).edge_copy(ignore).orig_to_copy(
make_iterator_property_map(copy_map.begin(), get(boost::vertex_index, small))));
// mark sub-graph vertices
int total_weight = 0;
for (auto largev : make_iterator_range(vertices(large))) {
int w = get(nweight, largev);
auto small_v = get(correspondence, largev);
auto root_v = copy_map[largev];
std::ostringstream label;
std::string color;
if (small_v != small.null_vertex()) {
total_weight += w;
/*auto sub_v =*/ add_vertex(root_v, sub);
label << "{small:" << small_v << " | large:" << largev << "}";
color = "green";
} else {
label << "{large:" << largev << "}";
color = "gray";
}
label << "|weight:" << w;
put(boost::vertex_attribute, root, root_v,
Dot::Dict{
{"label", label.str()},
{"color", color},
});
}
{ // write .dot and render png
std::string const fname = "dot" + std::to_string(++s_dotfile_counter);
get_property(root, boost::graph_vertex_attribute)["shape"] = "Mrecord";
get_property(sub, boost::graph_graph_attribute) //
["label"] = "total weight: " + std::to_string(total_weight);
{
std::ofstream ofs(fname + ".dot");
write_graphviz(ofs, root);
}
if (::system(("dot -Tpng '" + fname + ".dot' -o '" + fname + ".png'").c_str()))
std::cerr << "Couldn't not invokge graphviz dot tool" << std::endl;
}
return total_weight;
}
int main() {
struct NodeProps { int processing_power; };
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, NodeProps>;
// Build smaller graph (graph1)
Graph small, large;
add_edge(0, 6, small);
add_edge(0, 7, small);
add_edge(1, 5, small);
add_edge(1, 7, small);
add_edge(2, 4, small);
add_edge(2, 5, small);
add_edge(2, 6, small);
add_edge(3, 4, small);
// Build larger graph (graph2)
auto gen_power = bind(std::uniform_int_distribution(30, 120), std::mt19937(std::random_device{}()));
add_edge(0, 6, large);
add_edge(0, 8, large);
add_edge(1, 5, large);
add_edge(1, 7, large);
add_edge(2, 4, large);
add_edge(2, 7, large);
add_edge(2, 8, large);
add_edge(3, 4, large);
add_edge(3, 5, large);
add_edge(3, 6, large);
for (auto v : make_iterator_range(vertices(large)))
large[v].processing_power = gen_power();
// Create callback to print mappings
using V = Graph::vertex_descriptor;
std::map<V, V> mapping;
int best_power = INT_MIN;
auto callback = [&](auto f, auto f_inv) {
auto w = createRendering(small, large, f_inv, get(&NodeProps::processing_power, large));
std::cout << "found isomorphism mapping with total weight of " << w << "\n";
if (w > best_power) {
best_power = w;
for (mapping.clear(); auto v : make_iterator_range(vertices(small)))
mapping.emplace(v, f[v]);
}
return true; // give us more isomorphisms if any
};
if (vf2_subgraph_iso(small, large, callback)) {
std::cout << " best weight: " << best_power << " mapping:";
for (auto [s,l] : mapping)
std::cout << " [" << s << ", " << l <<"]";
std::cout << "\n";
} else {
std::cout << "no isomorphisms\n";
}
}
With a sample run output:
- Segmentation fault when converting char * to char **
- What's the difference between "C system calls" and "C library routines"?
- C standard - const qualification of struct members
- Conventions/good ways to initialize variables with default/NULL values
- why there are int56_t in clang c header file, and how to use them
- How to watch char values of strings pointed by a pointer to pointers in debugger mode of VSCode
- How to repeat a char using printf?
- Is left shifting a long long considered Undefined Behavior in C?
- String buffer gets skipped on the last loop iteration
- Unsigned int weird behavior with Loops in C
- How are Linked Lists implemented in the Ready Queue before moving onto the scheduler during the PCB implementation?
- How do C/C++/Objective-C compare with C# when it comes to using libraries?
- Why no switch on pointers?
- Similar syntax causes strange, repeated compile errors when building PHP from source on Windows
- Segmentation fault in C shellcode x64
- Where is the documentation for the XRandr header?
- i*=j ==x and i=i*j ==x behaving differently in C
- How can I make objcopy -Obinary append every text section?
- timespec equivalent for windows
- Register keyword: stack or heap
- Detect a parenthesized macro argument in C
- Modifying (stealing) Linux syscalls using kprobe
- Python's bz2 module not compiled by default
- ASCII file encoding with 16-bit bytes
- GtkContainer/GtkWidget maximum width
- AF-XDP: Implement Shared Umem sockets
- Are there known implementations of the CIEDE2000 or CIE94 Delta-E color difference calculation algorithm?
- ssh_channel_request_exec is not working without ssh_channel_read
- Are DHCP options ordered?
- Can't install apk using adb