How does one search for a small subgraph within a huge database?

[enjoysmath]

Graph algorithms doesn't support this feature directly, but can it be constructed out of the primitives?

[s1ck]

Are you referring to the Subgraph Isomorphism Problem? Here, we are looking for all subgraphs in another graph that are isomorphic to / "match" a given pattern graph. That pattern graph is what the Cypher query language in its core allows you to express.

Is this the problem you want to solve? Are you having a specific algorithm in mind that you would like to see implemented? How complex are the patterns you want to search, are they structure-only or do you have complex predicates?

Generally, I like the idea of adding subgraph isomorphism algos to the library.

[enjoysmath]

@s1ck Yes, that is the precise problem.

Except my query graphs are between 1 - 100 nodes, very sparse. In fact google "commutative diagrams" - that's what I'm in need of.

The database graph itself is a bunch of disconnected diagrams, but there is also a node type for Graph. Every node (type Object) and every edge (type Morphism) has a property that is the id of its Graph node. Then graph nodes can be connected say by user-defined links. Graph nodes also hold diagram-wide labels.

I've thought of some ideas on how to approximate the graph search. What about:

1. Find the longest path in the user's query graph and search for that, maybe checking for equality after expanding to the component.
2. Somehow just enumerating all nodes and relationships and making a really complicated Cypher query, if possible.
3. Do you have any suggestions for my specific problem?

Thanks. You are very helpful.

---

You asked about query complexity. I've thought of doing a regex-based match so that the variable label $c$ would match $a$ say, but that has unforseeable mathematical consequences, and seems like too hard to implement. Especially when there are benefits to doing just an exact match:

1. Very easy to implement.
2. The users will have fun drawing many diagrams anyway.
3. No need for a complex variable-template translation method.
4. No need for any kind of parsing or mathematical syntax recognition.

In other words, my queries will be by exact label match only, no complex predicates. Each Object / Morphism has a labels property which is a list of strings.

[s1ck]

@enjoysmath Sorry, I didn't find time to look into it last week. I'll find some time this week and come back to you.

[enjoysmath]

Thank you! I think it can be accomplished with multiple MATCH lines.

…

On Tue, Apr 2, 2019 at 1:18 AM Martin Junghanns ***@***.***> wrote: @enjoysmath <https://github.com/enjoysmath> Sorry, I didn't find time to look into it last week. I'll find some time this week and come back to you. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#851 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABiC92TN6zz8wV7iWbFApbt4JOvB60r9ks5vcxJXgaJpZM4cFOgV> .

[enjoysmath]

:)

…

On Tue, Apr 2, 2019 at 6:18 PM Luna Tuna ***@***.***> wrote: Thank you! I think it can be accomplished with multiple MATCH lines. On Tue, Apr 2, 2019 at 1:18 AM Martin Junghanns ***@***.***> wrote: > @enjoysmath <https://github.com/enjoysmath> Sorry, I didn't find time to > look into it last week. I'll find some time this week and come back to you. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#851 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/ABiC92TN6zz8wV7iWbFApbt4JOvB60r9ks5vcxJXgaJpZM4cFOgV> > . >