Ich versuche Boost's vf2_subgraph_iso
zu verwenden, und ich bekomme die falsche Antwort, wenn ich Untergraphen-Isomorphie zwischen einem Paar kleiner Graphen teste. Der Code lautet wie folgt:Warum gibt Boost VF2 Subgraph Isomorphie eine falsche Antwort?
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <sstream>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/property_map/property_map.hpp>
using namespace boost;
typedef property<edge_name_t, char> edge_prop;
typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_prop;
typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_prop, edge_prop> Graph;
typedef property_map<Graph, vertex_name_t>::type vertex_name_map_t;
typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
typedef property_map<Graph, edge_name_t>::type edge_name_map_t;
typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
bool is_subgraph_isomorphic(Graph smallGraph, Graph bigGraph)
{
vertex_comp_t vertex_comp =
make_property_map_equivalent(get(vertex_name, smallGraph), get(vertex_name, bigGraph));
edge_comp_t edge_comp =
make_property_map_equivalent(get(edge_name, smallGraph), get(edge_name, bigGraph));
vf2_print_callback<Graph, Graph> callback(smallGraph, bigGraph);
bool res = vf2_subgraph_iso(smallGraph, bigGraph, callback, vertex_order_by_mult(smallGraph),
edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
return res;
}
int main()
{
Graph gsmall,glarge;
add_vertex(vertex_prop('a'),gsmall);
add_vertex(vertex_prop('b'),gsmall);
add_edge(0, 1, edge_prop('a'), gsmall);
add_vertex(vertex_prop('a'),glarge);
add_vertex(vertex_prop('b'),glarge);
add_vertex(vertex_prop('a'),glarge);
add_edge(0, 1, edge_prop('b'), glarge);
add_edge(1, 2, edge_prop('a'), glarge);
std::cout << "Is first pair subisomorphic ? : " << is_subgraph_isomorphic(gsmall,glarge) << std::endl;
Graph graph1;
add_vertex(vertex_prop('a'), graph1);
add_vertex(vertex_prop('a'), graph1);
add_vertex(vertex_prop('a'), graph1);
add_edge(0, 1, edge_prop('b'), graph1);
add_edge(0, 1, edge_prop('b'), graph1);
add_edge(0, 1, edge_prop('d'), graph1);
add_edge(1, 2, edge_prop('s'), graph1);
add_edge(2, 2, edge_prop('l'), graph1);
add_edge(2, 2, edge_prop('l'), graph1);
// Build graph2
Graph graph2;
add_vertex(vertex_prop('a'), graph2);
add_vertex(vertex_prop('a'), graph2);
add_vertex(vertex_prop('a'), graph2);
add_vertex(vertex_prop('a'), graph2);
add_vertex(vertex_prop('a'), graph2);
add_vertex(vertex_prop('a'), graph2);
add_edge(0, 1, edge_prop('a'), graph2);
add_edge(0, 1, edge_prop('a'), graph2);
add_edge(0, 1, edge_prop('b'), graph2);
add_edge(1, 2, edge_prop('s'), graph2);
add_edge(2, 3, edge_prop('b'), graph2);
add_edge(2, 3, edge_prop('d'), graph2);
add_edge(2, 3, edge_prop('b'), graph2);
add_edge(3, 4, edge_prop('s'), graph2);
add_edge(4, 4, edge_prop('l'), graph2);
add_edge(4, 4, edge_prop('l'), graph2);
add_edge(4, 5, edge_prop('c'), graph2);
add_edge(4, 5, edge_prop('c'), graph2);
add_edge(4, 5, edge_prop('c'), graph2);
add_edge(5, 0, edge_prop('s'), graph2);
std::cout << "Is second pair subisomorphic ? : " << is_subgraph_isomorphic(graph1,graph2) << std::endl;
}
Das erste ist ein Paar von einfachen Graphen und die zweite ist die grafische Darstellung von dem in dem Boost-Dokumentation gegeben example.
Der Code scheint die richtige Antwort für das Boost-Beispiel zu geben, gibt aber die falsche Antwort für die erste. Hier ist die Ausgabe:
Is first pair subisomorphic ? : 0
(0, 2) (1, 3) (2, 4)
Is second pair subisomorphic ? : 1
Das erste Paar ist offensichtlich Untergraphen isomorph.
Ein weiteres ich neugierig, was ich auffiel war, dass, wenn ich
geänderttypedef adjacency_list<vecS, vecS, bidirectionalS, vertex_prop, edge_prop> Graph;
zu
typedef adjacency_list<vecS, vecS, undirectedS, vertex_prop, edge_prop> Graph;
der Ausgang jetzt
(0, 2) (1, 1)
Is first pair subisomorphic ? : 1
Is second pair subisomorphic ? : 0
ist, die für das erste Paar richtig ist aber falsch, der Zweite.
Compilation Befehl:
g++ "-std=c++11" code.cpp -lboost_graph -o exec
Laufen auf Xubuntu 16.04, auf dem neuesten Stand, soweit ich das beurteilen kann. Verwenden der Boost-Bibliothek aus den Repositories.
Könnte mir bitte jemand sagen, was ich falsch mache?
Wissen Sie, was 'bidirektionaleS' bedeutet? Es bedeutet unter anderem, dass "Kante (1,2, g)" nicht äquivalent zu "Kante (2,1, g)" ist. – llonesmiz
Ich bin neu zu steigern, und es scheint, ich habe das missverstanden. Das heißt aber, dass ich beide Paare sub-isomorph gemacht hätte, wenn ich "ungerichtetes" verwendet hätte, richtig? Da das zweite Paar subisomorph ist, wenn ich 'bidirektionalS' verwende, wenn die Kanten eine Richtung haben, sollte das gleiche Mapping im ungerichteten Fall funktionieren. – NILobachevsky
Ich kann nicht verstehen, warum dieses zweite Beispiel bei der Verwendung von 'directedS' ebenfalls fehlschlägt. – llonesmiz