{"action":"opened","issue":{"url":"https://api.github.com/repos/RDFLib/rdflib/issues/494","labels_url":"https://api.github.com/repos/RDFLib/rdflib/issues/494/labels{/name}","comments_url":"https://api.github.com/repos/RDFLib/rdflib/issues/494/comments","events_url":"https://api.github.com/repos/RDFLib/rdflib/issues/494/events","html_url":"https://github.com/RDFLib/rdflib/issues/494","id":93785218,"number":494,"title":"RDGA1 graph canonicalization sometimes collapses distinct BNodes","user":{"login":"joernhees","id":464192,"avatar_url":"https://avatars.githubusercontent.com/u/464192?v=3","gravatar_id":"","url":"https://api.github.com/users/joernhees","html_url":"https://github.com/joernhees","followers_url":"https://api.github.com/users/joernhees/followers","following_url":"https://api.github.com/users/joernhees/following{/other_user}","gists_url":"https://api.github.com/users/joernhees/gists{/gist_id}","starred_url":"https://api.github.com/users/joernhees/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joernhees/subscriptions","organizations_url":"https://api.github.com/users/joernhees/orgs","repos_url":"https://api.github.com/users/joernhees/repos","events_url":"https://api.github.com/users/joernhees/events{/privacy}","received_events_url":"https://api.github.com/users/joernhees/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/RDFLib/rdflib/labels/bug","name":"bug","color":"e10c02"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/RDFLib/rdflib/milestones/5","html_url":"https://github.com/RDFLib/rdflib/milestones/rdflib%204.2.1","labels_url":"https://api.github.com/repos/RDFLib/rdflib/milestones/5/labels","id":986799,"number":5,"title":"rdflib 4.2.1","description":"","creator":{"login":"joernhees","id":464192,"avatar_url":"https://avatars.githubusercontent.com/u/464192?v=3","gravatar_id":"","url":"https://api.github.com/users/joernhees","html_url":"https://github.com/joernhees","followers_url":"https://api.github.com/users/joernhees/followers","following_url":"https://api.github.com/users/joernhees/following{/other_user}","gists_url":"https://api.github.com/users/joernhees/gists{/gist_id}","starred_url":"https://api.github.com/users/joernhees/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joernhees/subscriptions","organizations_url":"https://api.github.com/users/joernhees/orgs","repos_url":"https://api.github.com/users/joernhees/repos","events_url":"https://api.github.com/users/joernhees/events{/privacy}","received_events_url":"https://api.github.com/users/joernhees/received_events","type":"User","site_admin":false},"open_issues":8,"closed_issues":23,"state":"open","created_at":"2015-02-19T14:38:16Z","updated_at":"2015-07-08T13:07:19Z","due_on":null,"closed_at":null},"comments":0,"created_at":"2015-07-08T13:07:19Z","updated_at":"2015-07-08T13:07:19Z","closed_at":null,"body":"There seems to be a bug in RDGA1 wrt. graph canonicalization.\r\nGiven an input graph `g`, `cg = rdflib.compare.to_canonical_graph(g)` will in some cases construct a canonical version of the graph that can't be isomorphic to `g` as `cg`'s node degrees are different.\r\n\r\nBelow is an example graph `g` showing this behavior. I'm a bit sorry for the length, it's basically the RDF representation of a SPARQL BGP (see #483 for more info) by using reification for each triple in the SPARQL pattern:\r\n\r\n```python\r\nimport rdflib\r\ng = rdflib.Graph()\r\ng += [\r\n (rdflib.term.BNode('Na1a8fbcf755f41c1b5728f326be50994'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#object'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Na1a8fbcf755f41c1b5728f326be50994'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#predicate'),\r\n  rdflib.term.BNode('vcb3')),\r\n (rdflib.term.BNode('Na1a8fbcf755f41c1b5728f326be50994'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#subject'),\r\n  rdflib.term.BNode('vcb2')),\r\n (rdflib.term.BNode('Na1a8fbcf755f41c1b5728f326be50994'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement')),\r\n (rdflib.term.BNode('Na713b02f320d409c806ff0190db324f4'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#object'),\r\n  rdflib.term.URIRef(u'target')),\r\n (rdflib.term.BNode('Na713b02f320d409c806ff0190db324f4'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#predicate'),\r\n  rdflib.term.BNode('vcb0')),\r\n (rdflib.term.BNode('Na713b02f320d409c806ff0190db324f4'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#subject'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Na713b02f320d409c806ff0190db324f4'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement')),\r\n (rdflib.term.BNode('Ndb804ba690a64b3dbb9063c68d5e3550'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#object'),\r\n  rdflib.term.BNode('vr0KcS4')),\r\n (rdflib.term.BNode('Ndb804ba690a64b3dbb9063c68d5e3550'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#predicate'),\r\n  rdflib.term.BNode('vrby3JV')),\r\n (rdflib.term.BNode('Ndb804ba690a64b3dbb9063c68d5e3550'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#subject'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Ndb804ba690a64b3dbb9063c68d5e3550'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement')),\r\n (rdflib.term.BNode('Ndfc47fb1cd2d4382bcb8d5eb7835a636'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#object'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Ndfc47fb1cd2d4382bcb8d5eb7835a636'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#predicate'),\r\n  rdflib.term.BNode('vcb5')),\r\n (rdflib.term.BNode('Ndfc47fb1cd2d4382bcb8d5eb7835a636'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#subject'),\r\n  rdflib.term.URIRef(u'target')),\r\n (rdflib.term.BNode('Ndfc47fb1cd2d4382bcb8d5eb7835a636'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement')),\r\n (rdflib.term.BNode('Nec6864ef180843838aa9805bac835c98'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#object'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Nec6864ef180843838aa9805bac835c98'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#predicate'),\r\n  rdflib.term.BNode('vcb4')),\r\n (rdflib.term.BNode('Nec6864ef180843838aa9805bac835c98'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#subject'),\r\n  rdflib.term.URIRef(u'source')),\r\n (rdflib.term.BNode('Nec6864ef180843838aa9805bac835c98'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'),\r\n  rdflib.term.URIRef(u'http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement'))]\r\n\r\nprint 'graph length: %d, nodes: %d' % (len(g), len(g.all_nodes()))\r\nprint 'triple_bnode degrees:'\r\nfor triple_bnode in g.subjects(rdflib.RDF['type'], rdflib.RDF['Statement']):\r\n    print len(list(g.triples([triple_bnode, None, None])))\r\nprint 'all node degrees:'\r\nprint sorted([len(list(g.triples([node, None, None]))) for node in g.all_nodes()], reverse=True)\r\n```\r\nThe above prints:\r\n```\r\ngraph length: 20, nodes: 15\r\ntriple_bnode degrees:\r\n4\r\n4\r\n4\r\n4\r\n4\r\nall node degrees:\r\n[4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\r\n```\r\nif you're interested, the graph looks like this:\r\n![screen shot 2015-07-08 at 14 38 35](https://cloud.githubusercontent.com/assets/464192/8570484/d73d8772-2580-11e5-9ff8-b297a76899b4.png)\r\n\r\nNow let's do the same for the canonicalized graph:\r\n```python\r\ncg = rdflib.compare.to_canonical_graph(test_graph)\r\nprint 'graph length: %d, nodes: %d' % (len(cg), len(cg.all_nodes()))\r\nprint 'triple_bnode degrees:'\r\nfor triple_bnode in cg.subjects(rdflib.RDF['type'], rdflib.RDF['Statement']):\r\n    print len(list(cg.triples([triple_bnode, None, None])))\r\nprint 'all node degrees:'\r\nprint sorted([len(list(cg.triples([node, None, None]))) for node in cg.all_nodes()], reverse=True)\r\n```\r\nThis produces the following output, which shows that something went wrong, as canonicalization shouldn't delete nodes nor change degrees:\r\n```\r\ngraph length: 19, nodes: 14\r\ntriple_bnode degrees:\r\n7\r\n4\r\n4\r\n4\r\nall node degrees:\r\n[7, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\r\n```\r\n\r\nthe canonical graph looks like this:\r\n![screen shot 2015-07-08 at 14 39 15](https://cloud.githubusercontent.com/assets/464192/8570723/a96d4038-2582-11e5-8b2b-119d7d65a81c.png)\r\nIn the picture you can see that the indicated `triple_bnode` suddenly has 2 subjects, predicates and objects, which is problematic for reification as afterwards you can't know which triple this statement is about anymore :(\r\n\r\n\r\n@jimmccusker could you maybe have a look?"}}