Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

update to graph isomorphism #128

Open
pfps opened this issue Jan 16, 2025 · 4 comments
Open

update to graph isomorphism #128

pfps opened this issue Jan 16, 2025 · 4 comments
Assignees
Labels
ms:CR Milestone: Candidate Recommendation

Comments

@pfps
Copy link
Contributor

pfps commented Jan 16, 2025

As far as I can tell, graph isomorphism needs the following extra clause

  • M(tt) is the triple term ( M(s), M(p), M(o) ) for tt a triple term of the form (s, p, o)

This is slightly clunky but doesn't use any concrete syntax.

@gkellogg gkellogg added the ms:CR Milestone: Candidate Recommendation label Jan 16, 2025
@hartig hartig self-assigned this Jan 17, 2025
@hartig
Copy link
Contributor

hartig commented Jan 17, 2025

I will take care of this one.

@hartig
Copy link
Contributor

hartig commented Jan 17, 2025

I was just about to implement the change as proposed in the issue description above. Yet, it turns out that it may not be exactly that simple, for the following reasons: By the current definition, the domain of the bijection_M_ is the set of all nodes of the graph G. Yet, it is not guaranteed that any of the three elements of the triple term tt = (s, p, o) is such a node. Therefore, M(s) may be undefined, and so may M(p) and M(o).

The fix to this problem may be to change the domain and the co-domain of the bijection M to both be the set of all RDF terms. With this change, the extra clause mention in the issue description above can then be added without problems. So, to be explicit, in addition to adding this extra clause we need to change the sentence before the bullet points in the section. I propose to change that sentence as follows:

Two RDF graphs G and G' are isomorphic (that is, they have an identical form) if there is a bijection M from the set of all RDF terms into that same set, such that all of the following properties hold:

I will implement this change once PR #137 is merged.

@pfps
Copy link
Contributor Author

pfps commented Jan 17, 2025

Good catch

@pchampin
Copy link
Contributor

Also, note that M(p) is not necessary in the recursion (p is always an IRI, so M(p) is always equal to p).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
ms:CR Milestone: Candidate Recommendation
Projects
None yet
Development

No branches or pull requests

4 participants