Hey Andy, thanks for the quick responses. For the time being I'm using JGraphT's isomorphism algorithm (VF2) and it works as expected.
See: https://jgrapht.org/guide/UserOverview#graph-comparisons I might retry IsoMatcher/IsoAlg in the future. Regards, Barry -----Original Message----- From: Andy Seaborne <[email protected]> Sent: zondag 1 december 2019 10:58 To: [email protected] Subject: Re: ElementPathBlock comparison Barry, Pull request #642 should fix this. Either do the variable -> blank node replacement and call IsoMatcher.isomorphic(graph,graph) Or call the isomorphism algorithm code as follows: Iso.Mappable mappable = (n1,n2) -> ( n1.isBlank() && n2.isBlank()) || ( n1.isVariable() && n2.isVariable() ); List<Tuple<Node>> x1 = ... List<Tuple<Node>> x2 = ... boolean b = IsoAlg.isIsomorphic(x1, x2, mappable, NodeUtils.sameValue); The "mappable" is the rule for which terms are considered in the isomorphism. The default and used by the main public functions is bnode mapping. IsoMatcher itself as a class is deprecated (its still there) and everything is done with functions. Andy [1] https://github.com/apache/jena/pull/642 On 29/11/2019 12:16, Andy Seaborne wrote: > Barry, > > It does look like something is wrong in iso-matching. Recorded as > JENA-1789. > > Using graph1.isoIsomorphicWith(graph2) > > is a workaround. > > IsoMatcher "fails safe" for its use in the test suite and also its > used there mainly on ResultSets not graphs. > > Andy > > > On 28/11/2019 16:04, Nouwt, B. (Barry) wrote: >> Hi Andy, thanks for the effort. >> >> If you clone this public github repository >> (https://github.com/barrynl/jena-example) and set it us as a Maven >> project and execute the main() in this Java class: >> >> https://github.com/barrynl/jena-example/blob/master/src/main/java/nl/ >> tno/ict/ds/cb/jena/JenaIsomorphTest.java >> >> >> it will show how converting variable nodes to blank nodes and using >> the IsoMatcher yields true, while it should be false. >> >> Maybe you can find what I'm doing wrong. >> >> Thanks in advance! >> >> Barry >> >> -----Original Message----- >> From: Andy Seaborne <[email protected]> >> Sent: donderdag 28 november 2019 11:22 >> To: [email protected] >> Subject: Re: ElementPathBlock comparison >> >> >> >> On 25/11/2019 13:52, Nouwt, B. (Barry) wrote: >>> Hey Andy, >>> >>> I have another question about comparing ElementPathBlock's the way >>> you suggest below using IsoMatcher. >>> >>> The following two graph patterns should (in my opinion and for my >>> use >>> case) not be the same, but the IsoMatcher says they match: >>> >>> graphpattern1: ?a <http://www.tno.nl/test1> ?b . ?b >>> <http://www.tno.nl/test2> ?a . >>> >>> graphpattern2: ?a <http://www.tno.nl/test1> ?b . ?a >>> <http://www.tno.nl/test2> ?b . >> >> They should be different. >> >> If it's _:a and _:b is it different? In which case the variable bit >> is wrong. >> >>> >>> Since RDF triples form a directed graph, this result surprises me, >>> because in graphpattern1 the subject of /test1 has a single outgoing >>> edge, while in graphpattern2 the subject of /test1 has two outgoing >>> edges. How can this be judged the same? >>> >>> I've tested it in two ways: >>> - converting all variables to blank nodes and using: >>> IsoMatcher match = new IsoMatcher(tuplesTriples(gr1.find()), >>> tuplesTriples(gr2.find()), new >>> ResultSetCompare.BNodeIso(NodeUtils.sameValue)); >>> >>> - or not converting them to blank nodes and using: >>> IsoMatcher match = new IsoMatcher(tuplesTriples(gr1.find()), >>> tuplesTriples(gr2.find()), new CustomBNodeIso(NodeUtils.sameValue)); >>> >>> Where CustomBNodeIso adds the IF statement you suggest below. >>> >>> In both cases the above two graph patterns are judged the same while >>> they shouldn't. >>> >>> Any idea what I'm doing wrong? >> >> Do you have a complete, mininal example I can copy-and-paste and run? >> >> If uou put it on a gist/pastebin I might find time to try it. >> >> Andy >> >>> >>> Regards, Barry >>> >>> -----Original Message----- >>> From: Nouwt, B. (Barry) <[email protected]> >>> Sent: donderdag 21 november 2019 13:03 >>> To: [email protected] >>> Subject: RE: ElementPathBlock comparison >>> >>> Hey Andy, thanks. I'm currently testing the IsoMatcher - >>> EqualityTest combination and the first tests look promising. >>> >>> I use the following code (where the gr1 and gr2 graphs have all >>> variables of the graph pattern replaced by blanknodes): >>> >>> IsoMatcher match = new IsoMatcher(tuplesTriples(gr1.find()), >>> tuplesTriples(gr2.find()), new >>> ResultSetCompare.BNodeIso(NodeUtils.sameValue)); >>> >>> but as I said, it requires some more testing. Not having to convert >>> the variable into blanknodes would probably be more elegant, so >>> maybe I'll try your suggestion below as well. >>> >>> Regards, >>> >>> Barry >>> >>> -----Original Message----- >>> From: Andy Seaborne <[email protected]> >>> Sent: woensdag 20 november 2019 10:41 >>> To: [email protected] >>> Subject: Re: ElementPathBlock comparison >>> >>> >>> >>> On 19/11/2019 15:52, Nouwt, B. (Barry) wrote: >>>> Hi Andy, I have an additional question regarding your tip about >>>> turning variables into blanknodes with names; would that also work >>>> in case of predicates? Because variables can be located at the >>>> 'predicate' location of a triple, but I'm unsure whether blanknodes >>>> are allowed at that location. >>> >>> Yes. >>> >>> My recommendation is to write a EqualityTest that does variable >>> isomorphism. It's a small chnage to the >>> >>> Copy BNodeIso and add the "if": >>> >>> if ( n1.isVariable() && n2.isVariable() ) >>> return mapping.makeIsomorphic(n1, n2) ; >>> >>> (not tested) >>> >>> Andy >>> >>>> >>>> Regards, Barry >>>> >>>> -----Original Message----- >>>> From: Nouwt, B. (Barry) <[email protected]> >>>> Sent: dinsdag 19 november 2019 16:49 >>>> To: [email protected] >>>> Subject: RE: ElementPathBlock comparison >>>> >>>> Thanks for the quick replies. >>>> >>>> @Andy Exactly, I do care about the shape, but not about exact >>>> variable names. >>>> >>>> I wanted to use Google Guava Graph library to construct the graphs >>>> and use their equality mechanism, but I think the IsoMatcher is a >>>> better fit, thanks for the pointer! This together with your tip >>>> about transforming the same variable nodes into blank nodes with >>>> the same name, it might just work in combination with BNodeIso. >>>> I'll give that a try and report back the result. >>>> >>>> BTW In the comments of this IsoMatcher class, it says "For graphs, >>>> the Graph isomorphism code in Jena is much better (better tested, >>>> better performance)", is this relevant for me? And do you know >>>> which isomorphism code in Jena is it referring to? >>>> >>>> @Martynas I could, indeed, encode the two BGPs into two RDF graphs >>>> using sp:TriplePattern, but then I still a way to match them. For >>>> my problem this RDF encoding is not necessary and encoding it using >>>> the Google Guava Graph lib seems sufficient. >>>> >>>> Regards, Barry >>>> >>>> -----Original Message----- >>>> From: Andy Seaborne <[email protected]> >>>> Sent: dinsdag 19 november 2019 15:49 >>>> To: [email protected] >>>> Subject: Re: ElementPathBlock comparison >>>> >>>> >>>>> Hi all, >>>>> >>>>> I have two ARQ ElementPathBlocks (or Basic Graph Pattern, see >>>>> SPARQL spec https://www.w3.org/TR/sparql11-query/#GraphPattern) >>>>> and would like to know whether they are equal ignoring variable >>>>> names and ordering of the triples. What is the best/easiest way to >>>>> do that with the Apache Jena? I see there is an >>>>> org.apache.jena.sparql.util.Iso class that provides methods for >>>>> testing isomorphisms...but I'm unsure whether this is what I am >>>>> looking for. I also tested two ElementPathBlocks and using their >>>>> equalTo method (which uses the Iso class), but both variable names >>>>> and order seems to matter judging them equal. >>>> >>>> I'm guessing you mean not caring about the variable names but >>>> respecting the shape they create in the BGP. >>>> >>>> IsoMatcher is a simple algorithm for matching unordered lists >>>> (Iso.isomorphic is ordered lists.) >>>> >>>> If you want to ignore variables names you'll need a "EqualityTest" >>>> that captures that >>>> >>>> >>>> BNodeIso does this for bnodes. Modifying that for a Var->Var map >>>> loosk possible (or converting the input BGPs to have a bnode with >>>> label derived from the Variable name). >>>> >>>> Andy >>>> This message may contain information that is not intended for you. >>>> If you are not the addressee or if this message was sent to you by >>>> mistake, you are requested to inform the sender and delete the >>>> message. TNO accepts no liability for the content of this e-mail, >>>> for the manner in which you use it and for damage of any kind >>>> resulting from the risks inherent to the electronic transmission of >>>> messages. >>>> >>>
