GraphGists

Recently there was a nice blog on versioning networks by Ian Robinson (read it here) on using identity nodes and separating structure from state. In this gist I’d like to put in my 2 cents by introducing another approach using relationnodes. This is more about structure of a network than about states of nodes, but it treats versioning differently. As Ian states in his blog, there’s always a trade-off to be made, since versioning causes an extra load on storage and processing.

Relationnodes?

What are relationnodes?

Relation nodes are intermediary nodes between two network nodes that represents the relation between the nodes.

So, if A and B are two network nodes, instead of connecting them with a relationship of [:RELTYPE], a relationnode is inserted in between, and is connected with a [:RS] and [RE] which stand for relation start and relation end respectively.

Gist01

Why use relationnodes?

Neo4j (my preferred graph db) current 2.0.3. version does not allow to create relationships between a relationship and a node. And this is what I need if I want to indicate that a specific relationship between to network nodes belongs to a specific network, which is itself represented by a node.

In addition, my usecase requires me to share network nodes between networks, but in a different constellation.

Another reason is that a network is determined by the relationships between the nodes. Not by the nodes in themselves. If I have two nodes A and B, this doesn’t tell me something about their relationship. Not its direction, not its type, or if there are multiple relationships connecting them. On the other hand, if I know a relationship, I know its starting/ending node and its type. A node can exist without relationships, while a relationship can only exist with a start and end node.

A fourth reason for using this approach is that it allows me to compare networks. For instance to answer questions like "Can version 3 of Network 1 co-exist with version 1 of Network 2?". This will not be subject of this gist however, since it requires some additional braintime.

Creating a network

Setup

The process of creating a network has the following steps:

  • Create a node representing a network

  • Create network nodes

  • Create relationnodes that are linked through [:RS] and [:RE] relations to network nodes and with an [:UPDATE {type:'ADD', version:1] to the network node.

A first version of Network 1 of chaining A to B to C is created by the setup query. Note that the version property of the [:UPDATE] relationship can simply be replaced or accompanied by a timestamp property, making the graph time-aware.

CREATE (_0:`nw` {`name`:"Network1"})
CREATE (_5:`nwnode` {`name`:"A"})
CREATE (_6:`nwnode` {`name`:"B"})
CREATE (_7:`nwnode` {`name`:"C"})
CREATE (_13:`relationnode` {`id`:1})
CREATE (_14:`relationnode` {`id`:2})
CREATE _5-[:`RS`]->_13
CREATE _6-[:`RS`]->_14
CREATE _13-[:`RE`]->_6
CREATE _14-[:`RE`]->_7
CREATE _0-[:`UPDATE` {`type`:"ADD", `version`:1}]->_14
CREATE _0-[:`UPDATE` {`type`:"ADD", `version`:1}]->_13

The relations in this network are:

MATCH (s:nwnode)-[:RS]->(rn:relationnode)-[:RE]->(e:nwnode)
RETURN s.name as From,e.name as To ORDER BY From,To

Adding a node to the network

If a node has to be added to the network, we need to:

  • Create the new node

  • Create a relationnode

  • Create an [:UPDATE] this time with version:2

MATCH (nw:nw {name:"Network1"}),(sn:nwnode {name:"C"})
CREATE (_8:`nwnode` {`name`:"D"})
CREATE (_15:`relationnode` {`id`:3})
CREATE (sn)-[:`RS`]->_15-[:`RE`]->_8
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->_15

The relations in version 2 of our network are:

MATCH (s:nwnode)-[:RS]->(rn:relationnode)-[:RE]->(e:nwnode)
RETURN s.name as From,e.name as To ORDER BY From,To

Removing a node from the network

If a node has to be removed to the network, what we do is to add an [:UPDATE {type:'REMOVE', version:3}] relation to the concerned relationnodes. So, removing node "C" entirely from Network 1 is a matter of:

  • Finding the relationnodes connecting "C" with Network 1

  • Create [:UPDATE {type:'REMOVE', version:3}] relationships between Network 1 and these relationnodes

MATCH (nw:nw {name:"Network1"})-[:UPDATE]->(rn:relationnode)-[:RS|RE]-(n:nwnode {name:"C"})
WITH nw,COLLECT(DISTINCT rn) AS rns
FOREACH ( i IN rns |
  CREATE (nw)-[:`UPDATE` {`type`:"REMOVE", `version`:3}]->(i)
)

A full list of relations that exist now is given by this query:

MATCH (nw:nw {name:"Network1"})-[u:UPDATE]->(rn:relationnode),(s:nwnode)-[:RS]->(rn)-[:RE]->(e:nwnode)
RETURN u.version AS Version,u.type AS UpdateType,s.name AS From, e.name AS To
ORDER BY Version,UpdateType,From

To get the relations in version 3 of our network, we have to limit the search to the network, and just take into account the transactions for which the most recent [:UPDATE] that have a type = "ADD".

What you see is that by removing C we also cut D out of the network. Too bad, but fortunately we can also create relationships between existing nodes.

If a node has to be added to the network, we need to:

  • Get the nodes

  • Create a relationnode

  • Create an [:UPDATE] this time with version:4

MATCH (nw:nw {name:"Network1"}),(sn:nwnode {name:"B"}),(en:nwnode {name:"D"})
CREATE (rn:`relationnode` {`id`:7})
CREATE (sn)-[:`RS`]->(rn)-[:`RE`]->(en)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:4}]->(rn)

And the updated version of the network is:

Historical versions

A specific version of the network can be retrieved by just taking into account the [:UPDATE] relationships up to that version.

Version 1 of Network 1

And as a graph (only works for now 14MAY2014 when you are here http://jexp.github.io/graphgist/?40364ac2a52f57aa520a . Thanks @Jim_Salmons for pointing out)

Version 2 of Network 1

Version 3 of Network 1

Adding a second network

One of the reasons for this approach was that I need to be able to re-use the network nodes in a second network with its own relations.

Let’s create a Network 2 with 2 versions.

  • Version 1

    • C to A

  • Version 2

    • A to D

    • B to A

    • D to E

    • E to A

    • E to B

MATCH (na:nwnode {name:"A"}),(nb:nwnode {name:"B"}),(nc:nwnode {name:"C"}),(nd:nwnode {name:"D"})
CREATE (nw:`nw` {`name`:"Network2"})
CREATE (ne:`nwnode` {`name`:"E"})

CREATE (nc)-[:`RS`]->(rn1:relationnode)-[:`RE`]->(na)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:1}]->(rn1)
CREATE (nw)-[:`UPDATE` {`type`:"REMOVE", `version`:2}]->(rn1)

CREATE (nb)-[:`RS`]->(rn2:relationnode)-[:`RE`]->(na)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->(rn2)

CREATE (na)-[:`RS`]->(rn3:relationnode)-[:`RE`]->(nd)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->(rn3)

CREATE (nd)-[:`RS`]->(rn4:relationnode)-[:`RE`]->(ne)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->(rn4)

CREATE (ne)-[:`RS`]->(rn5:relationnode)-[:`RE`]->(nb)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->(rn5)

CREATE (ne)-[:`RS`]->(rn6:relationnode)-[:`RE`]->(na)
CREATE (nw)-[:`UPDATE` {`type`:"ADD", `version`:2}]->(rn6)

After which the relations of the current Network 2 are:

Just checking

Version 2 of Network 1 is still intact of course.

Afterthoughts

This is my first gist. Was fun setting it up. Would be great to have //graph thingies that visualise the query results, not the enitre graph. UPDATE : we have them on http://jexp.github.io/graphgist/?40364ac2a52f57aa520a :) and somewhere in the near future also on http://gist.neo4j.org/ I guess.

I prefer to do things as graphy as possible. Not sure if I succeeded in this one, but I try to keep in mind that opening and closing nodes and relationships instead of doing traversals comes at a cost.

Adding another property {status: "pending"} to the [:UPDATE] relationships will allow me to run cyphers answering questions like : "What if I do this?"

As I already said, adding timestamps to the [:UPDATE] relationships will make it time-aware. You could also create a linked list of version nodes and link the [:UPDATE] to those nodes.

Comparing different networks will be something for my next gist.

I will also be treating vizualsization aspects of working with relationnodes. Sometimes you want to see them, sometimes they get in the way because force-driven layouts may cause angles where you don’t want them. Fortunately Cypher allows you to tweak results in a way that a viz engine can handle it, and to fool the viz engine so that it thinks what you feed it, is a relationship.

Interested? Follow me on @tomzeppenfeldt / @ophileon Any comments appreciated too of course.