Re: [jgrapht-users] Isomorphic Graphs - VF2

[J K. <j.k...@gm...>]

Please address your replies to the entire list, not to me in person: this
increases the likelihood that the original author of the algorithm chimes
in.

I'm unfortunately not familiar with the VF2 algorithm, or its
implementation in jgrapht. I'd recommend to repeat your experiment. Keep
your experiment as simple as possible to eliminate potential (common)
causes of bugs. E.g.:
1. use Graph<Integer, DefaultEdge> g1=new SimpleGraph<>(DefaultEdge.class);
for both graphs (instead of directed graphs which are cast to undirected
graphs).
2. use Integer as vertex data type, not String.

Finally:
1. Since checking whether 2 graphs are isomorphic is generally hard, please
verify whether VF2 is a complete (exact) algorithm.
2. Provide a mapping from the vertices of g1 to the vertices of g2 to prove
that the graphs are indeed isomorphic.

If the graphs are indeed isomorphic, the algorithm is exact, and the
algorithm returns false, please feel free to file a bug report using our
issue tracker:
https://github.com/jgrapht/jgrapht/issues
Alternatively, if you are convinced that this is a bug, feel free to have a
look at the source code (https://github.com/jgrapht/jgrapht) . The
algorithm seems pretty short, so it may not be very hard to track down
what's going wrong.

thanks,

Joris Kinable


On Thu, Aug 17, 2017 at 2:37 PM, murad tukan <mur...@gm...> wrote:

> Dear Joris,
>
> I have attached bellow the code for checking the isomorphism:
>
>
> public class testing3 {
>
>     private static DefaultDirectedGraph<String, DefaultEdge> graph1,
> graph2;
>     private static IsomorphismInspector<String, DefaultEdge> inspector;
>
>
>     public static void main(String[] args)
>     {
>
>
>         graph1 = new DefaultDirectedGraph<String,
> DefaultEdge>(DefaultEdge.class);
>         graph2 = new DefaultDirectedGraph<String,
> DefaultEdge>(DefaultEdge.class);
>
>         // graph1
>         for(int i = 1; i <= 6; ++i)
>         {
>             graph1.addVertex(Integer.toString(i));
>             graph2.addVertex(Integer.toString(i));
>         }
>
>         graph1.addEdge("1", "2");
>         graph1.addEdge("2", "1");
>         graph1.addEdge("1", "3");
>         graph1.addEdge("3", "1");
>         graph1.addEdge("1", "6");
>         graph1.addEdge("6", "1");
>         graph1.addEdge("2", "4");
>         graph1.addEdge("4", "2");
>         graph1.addEdge("2", "5");
>         graph1.addEdge("5", "2");
>         graph1.addEdge("3", "4");
>         graph1.addEdge("4", "3");
>         graph1.addEdge("3", "5");
>         graph1.addEdge("5", "3");
>         graph1.addEdge("4", "6");
>         graph1.addEdge("6", "4");
>         graph1.addEdge("5", "6");
>         graph1.addEdge("6", "5");
>
>
>         // graph2
>         graph2.addEdge("1", "2");
>         graph2.addEdge("2", "1");
>         graph2.addEdge("1", "3");
>         graph2.addEdge("3", "1");
>         graph2.addEdge("1", "6");
>         graph2.addEdge("6", "1");
>         graph2.addEdge("2", "3");
>         graph2.addEdge("3", "2");
>         graph2.addEdge("2", "4");
>         graph2.addEdge("4", "2");
>         graph2.addEdge("3", "5");
>         graph2.addEdge("5", "3");
>         graph2.addEdge("4", "5");
>         graph2.addEdge("5", "4");
>         graph2.addEdge("4", "6");
>         graph2.addEdge("6", "4");
>         graph2.addEdge("5", "6");
>         graph2.addEdge("6", "5");
>
>         UndirectedGraph<String, DefaultEdge> g1 = new
> AsUndirectedGraph<String, DefaultEdge>(graph1);
>         UndirectedGraph<String, DefaultEdge> g2 = new
> AsUndirectedGraph<String, DefaultEdge>(graph2);
>
>         inspector = new VF2GraphIsomorphismInspector<String,
> DefaultEdge>(g1,g2);
>         System.err.println(inspector.isomorphismExists());
>     }
>
> }
>
> For such graph, the result should be true rather than false (Also i
> checked using MATLAB graph isomorphism solver and it returned true).
>
> To get more intuition why the two graphs are isomorphic, see the actual
> graphs:
>
> [image: Inline image 2]
>
>
> Please advise.
>
> Thanks in advance,
> M.T.
>
> P.s. Also tried using SimpleGraph and still got false in term of
> isomorphic or not.
>
> On Thu, Aug 17, 2017 at 7:48 AM, J Kinable <j.k...@gm...> wrote:
>
>> Hi,
>>
>> Can you be a bit more specific? What is the graph you are testing on? Can
>> you show a code snippet. Preferably provide a small working example, and
>> describe the expected output.
>>
>> br,
>>
>> Joris Kinable
>>
>> On Wed, Aug 16, 2017 at 9:59 PM, murad tukan <mur...@gm...> wrote:
>>
>>> Dear sir/madam,
>>>
>>> I have tried your vf2 algorithm a.k.a. VF2GraphIsomorphismInspector on
>>> the following graphs by replacing each edge by two directional edges such
>>> that each is in opposite direction in order to obtain a directed graph.
>>> The algorithm returned false when it should have returned true.
>>>
>>> Is there a bug in the implementation of VF2 or I misrepresented the
>>> graphs?
>>>
>>> Please advise as soon as possible.
>>>
>>> Thanks in advance,
>>> M.T.
>>>
>>> ------------------------------------------------------------
>>> ------------------
>>> Check out the vibrant tech community on one of the world's most
>>> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>
>