compare isomophic checks with SDMLib

[hoechp]

It's not exactly clear how to reliably compare performance of both systems. The check that's implemented here is mainly for testing if a graph is an isomorphic subgraph of another graph, but it can also be used to check if two graphs are isomorph to one another. I'll probably compare some different types of big graphs, mainly including those who should perform best and worst on this system.

The main problem should be to bring the same graph i use in this system to SDMLib.

[hoechp]

I found the class org.sdmlib.models.pattern.IsomorphismComputation with method isIsomorphic(Object, Object, IdMap) : boolean in SDMLib, that seems to be the one to use for this test - so I can compare the performance to the one from the GraphEngine of this project.

I've only seen SDMLib's IsomorphismComputation be used with SimpleStates, though, which are simplified graphs without attribute names or even multiple attributes and without edge names and so on - nothing that could be compared to a proper graph, especially regarding performance.

I have to find out, if I can use proper graphs with IsomorphismComputation, or if there is another isomorphism check I could use in SDMLib. And I probably have to connect the two projects for a while, so I can transform graphs generated in one project to the counterparts in the other project - OR I have to deserialize JSON from one project in the other one, which could be even harder. Or I just generate the same graph programmatically in both systems to compare performance...

[hoechp]

Okay, there's a ferryman's problem example at org.sdmlib.test.examples.reachabilitygraphs.ReachabilityGraphFerrymansProblemExample that seems to be, like about any other graph, compatible with IsomorphismComputation. I never used SDMLib before. So for simplicity, I could use some pre-existing generated classes like those and create some huge graphs, that don't make any sense, with it - as long as I manage to create the same graph in my project. Probably not today though. Whatever helps... :)

[hoechp]

The first comparison was done with a graph with three types of nodes:

• NodeTypeA in SDMLib has an attribute 'attra' with the value always being 'a' (in my project that Node has an attribute 'type' with value 'NodeTypeA' and also 'attra' = 'a')
• NodeTypeB in SDMLib has an attribute 'attrb' with the value always being 'b' (in my project that Node has an attribute 'type' with value 'NodeTypeB' and also 'attrb' = 'b')
• NodeTypeC in SDMLib has an attribute 'attrc' with the value always being 'c' (in my project that Node has an attribute 'type' with value 'NodeTypeC' and also 'attrc' = 'c')

I generated 50 nodes of each type.

• each NodeTypeA has an edge 'atob' to each NodeTypeB
• each NodeTypeB has an edge 'btoc' to each NodeTypeC
• each NodeTypeC has an edge 'ctoa' to each NodeTypeA

SDMLib took for the pure isomorphic check about half a second (and like a minute to build the graphs) test ismorphic check performance: 589.034698ms

my project took for the pure isomorphic check about 1/30 second (and like no time to build the graphs) test ismorphic check performance: 31.349503ms

I'm sure other graphs perform differently - maybe there are cases, where my project is slower.

Here's the test in SDMLib:

   @Test
   public void PhilippKolodziejIsomorphismTestGraph() {
          Storyboard storyboard = new Storyboard();
          ClassModel model = new ClassModel("org.sdmlib.test.examples.reachabilitygraphs.philippkolodziejisomorphismgraphtest");
          Clazz a = model.createClazz("NodeTypeA")
                  .withAttribute("attra", DataType.STRING);
          Clazz b = model.createClazz("NodeTypeB")
                  .withAttribute("attrb", DataType.STRING);
          Clazz c = model.createClazz("NodeTypeC")
                  .withAttribute("attrc", DataType.STRING);
          a.withUniDirectional(b, "atob", Cardinality.MANY);
          b.withUniDirectional(c, "btoc", Cardinality.MANY);
          c.withUniDirectional(a, "ctoa", Cardinality.MANY);
          storyboard.addClassDiagram(model);
          model.generate("src/test/java");
          storyboard.dumpHTML();
   }

    @Test
    public void PhilippKolodziejIsomorphismTest() {
        Storyboard storyboard1 = new Storyboard();
        Storyboard storyboard2 = new Storyboard();
        // ================================================
        storyboard1.add("initial situation:");
        storyboard2.add("initial situation:");
        int size = 50;
        ArrayList<NodeTypeA> as1 = new ArrayList<NodeTypeA>();
        ArrayList<NodeTypeB> bs1 = new ArrayList<NodeTypeB>();
        ArrayList<NodeTypeC> cs1 = new ArrayList<NodeTypeC>();
        ArrayList<NodeTypeA> as2 = new ArrayList<NodeTypeA>();
        ArrayList<NodeTypeB> bs2 = new ArrayList<NodeTypeB>();
        ArrayList<NodeTypeC> cs2 = new ArrayList<NodeTypeC>();
        for (int i = 0; i < size; ++i) {
            as1.add(new NodeTypeA());
            bs1.add(new NodeTypeB());
            cs1.add(new NodeTypeC());
            as2.add(new NodeTypeA());
            bs2.add(new NodeTypeB());
            cs2.add(new NodeTypeC());
        }
        for (int i = 0; i < size; ++i) {
            as1.get(i).setAttra("a");
            bs1.get(i).setAttrb("b");
            cs1.get(i).setAttrc("c");
            as2.get(i).setAttra("a");
            bs2.get(i).setAttrb("b");
            cs2.get(i).setAttrc("c");
            for (int j = 0; j < size; ++j) {
                as1.get(i).withAtob(bs1.get(j));
                bs1.get(i).withBtoc(cs1.get(j));
                cs1.get(i).withCtoa(as1.get(j));
                as2.get(i).withAtob(bs2.get(j));
                bs2.get(i).withBtoc(cs2.get(j));
                cs2.get(i).withCtoa(as2.get(j));
            }           
        }
        NodeTypeA root1 = as1.get(0);
        NodeTypeA root2 = as2.get(0);
        storyboard1.addObjectDiagram(root1);
        storyboard2.addObjectDiagram(root1);
        storyboard1.add("compute certificates");
        storyboard1.add("compute certificates");
        ReachableState rs1 = new ReachableState().withGraphRoot(root1);
        ReachableState rs2 = new ReachableState().withGraphRoot(root2);
        NodeTypeACreator cc1 = new NodeTypeACreator();
        NodeTypeACreator cc2 = new NodeTypeACreator();
        IdMap map1 = cc1.createIdMap("s");
        IdMap map2 = cc2.createIdMap("s");
        map1.with(ReachabilityGraphCreator.createIdMap("rg"));
        map2.with(ReachabilityGraphCreator.createIdMap("rg"));
        String s1cert = rs1.computeCertificate(map1);
        String s2cert = rs2.computeCertificate(map2);
        storyboard1.add(s1cert);
        storyboard2.add(s2cert);
        ReachabilityGraph reachabilityGraph1 = new ReachabilityGraph()
           .withMasterMap(map1).withStates(rs1).withTodo(rs1).withStateMap(s1cert, rs1);
        ReachabilityGraph reachabilityGraph2 = new ReachabilityGraph()
           .withMasterMap(map2).withStates(rs2).withTodo(rs2).withStateMap(s2cert, rs2);
        long start = System.nanoTime();
        Assert.assertNotNull(IsomorphismComputation.calculateMatch(rs1, rs2, map1));
        long duration = System.nanoTime() - start;
        System.out.println("test ismorphic check performance: " + duration / 1e6 + "ms");
    } 

Here's the test in my project:

    @Test
    public void testIsomorphismTestGraph() {

        Graph one = new Graph();

        ArrayList<Node> as = new ArrayList<Node>();
        ArrayList<Node> bs = new ArrayList<Node>();
        ArrayList<Node> cs = new ArrayList<Node>();

        int size = 50;

        for (int i = 0; i < size; ++i) {
            as.add(new Node().setAttribute("type", "NodeTypeA").setAttribute("attra", "a"));
            bs.add(new Node().setAttribute("type", "NodeTypeB").setAttribute("attrb", "b"));
            cs.add(new Node().setAttribute("type", "NodeTypeC").setAttribute("attrc", "c"));
        }
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                as.get(i).addEdge("atob", bs.get(j));
                bs.get(i).addEdge("btoc", cs.get(j));
                cs.get(i).addEdge("ctoa", as.get(j));
            }
            one.addNode(as.get(i)).addNode(bs.get(i)).addNode(cs.get(i));
        }

        Graph two = one.clone();

        long start = System.nanoTime();
        Assert.assertTrue(GraphEngine.isIsomorphTo(two, one));
        long duration = System.nanoTime() - start;
        System.out.println("test ismorphic check performance: " + duration / 1e6 + "ms");

    }

[hoechp]

I should wait for other features to be implemented and then write a couple more tests for different types of graphs.

[hoechp]

see #21