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
Here's my take on things.
To the best of my knowledge it is not possible to cause
vf2_subgraph_isoto consider vertices from the large graph in any preferential order. There is theVertexOrderSmallargument 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:
Live On Coliru
Prints, e.g.:
Those images were generated by
DOTfrom graphviz files written like e.g. dot5.dot: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:
With a sample run output: