c++algorithmgraphboostisomorphism
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:
- C typedef name conflict
- How to use 32-bit pointers in 64-bit application?
- problems with scanf input stream
- Is it guaranteed to be safe to perform memcpy(0,0,0)?
- Need help understanding pointer to a type of n elements in C (int (*p)[10])?
- Local variables performance vs global in example
- How to Print SOAP Message Request Body generated using GSOAP when calling service
- Big Number Subtraction in C
- Docker custom program stop
- GTK4 Windows Multiple File Choosing
- Cannot get lldb to read file input through redirect
- Modeling nested lists in C
- Linker and Memory map for shared memory in autosar embedded environment
- Why is only the numerator cast to float to obtain a float quotient while dividing two integers?
- $gcc problemMatcher doesn't show all errors or warnings
- What registers to save in the ARM C calling convention?
- What does ** do in C language?
- How to install pywin32 module in windows 7
- How to differentiate a Cypher clause from an SQL clause in C?
- How do I check if my executable is running for a service or for a normal program?
- How to fix a simple error in Atmel studio
- Given day, month, year calculate day in year
- Definition of int64_t
- Can we have multiple c files to define functions for one header file?
- Check if array is ASCII
- What does C or GCC do when implicit function declaration exists
- How can I programmatically find the CPU frequency with C
- Can I use a binary literal in C or C++?
- Want to Convert Integer to String without itoa function
- How to permanently configure VSCode to use cl.exe without launching it from the Developer Command Prompt?