Modeling and resolving package dependencies

[jgaskins]

Working on a package-management system (like NPM or Rubygems) and I'm having trouble coming up with a query (or set of queries) that will resolve downstream package dependencies. It's currently modeled as Package nodes representing the packages themselves by name and each time you release a new version of your package it creates a Release node, connected to the Package via DEPENDS_ON:

CREATE (p1:Package { name: 'p1' })
CREATE (p2:Package { name: 'p2' })
CREATE (p3:Package { name: 'p3' })

CREATE (r1:Release { version: '1.0.0' })
CREATE (r2_1:Release { version: '1.0.0' })
CREATE (r2_2:Release { version: '1.0.1' })
CREATE (r3_1:Release { version: '1.0.0' })
CREATE (r3_2:Release { version: '1.1.0' })

CREATE   (r1)-[:DEPENDS_ON]->(r2_1)
CREATE (r2_1)-[:DEPENDS_ON]->(r3_1)
CREATE (r2_2)-[:DEPENDS_ON]->(r3_2)

The reality is a bit more involved (download count, ownership, unique constraint on release version by package name, etc) but irrelevant to dependency resolution.

We need to figure out the ideal set of releases given a spec. In this case, if my application depends on p1, I would expect to also then get the latest p2 and p3 releases (r2_2 and r3_2, respectively). My query currently looks something like this:

UNWIND $dependencies AS dep
MATCH (release:Release{name: dep.name})

// Ensure we stay within version boundaries if specified
WHERE CASE dep.max_version
WHEN NULL THEN true
ELSE release.version >= dep.min_version
END
AND CASE dep.min_version
WHEN NULL THEN true
ELSE release.version < dep.max_version
END

WITH DISTINCT release
// Get downstream dependencies
MATCH (release)-[:DEPENDS_ON*0..]->(dependency)

RETURN DISTINCT dependency

The dependencies parameter has this structure:

[
  {
    name: 'p1',
    # Version range is optional, the CASE statements default
    # to matching if not provided
    min_version: '1.0.0', # inclusive
    max_version: '2.0.0', # exclusive
  },
  # ...
]

This returns all matching downstream releases, though, and I absolutely cannot figure out how to get it to return only the latest versions of each one. I've been at this for 2 days and I feel like my approach is missing something and I just can't figure out what it is. Any ideas?

[Cobra]

Hello @jgaskins 😊

In your example, Package nodes don't have relationships. Can you provide the full sample dataset please?

Regards,
Cobra

[jgaskins]

@Cobra Ah, my mistake. Here it is with the relationships between Package and Release:

CREATE (p1:Package { name: 'p1' })
CREATE (p2:Package { name: 'p2' })
CREATE (p3:Package { name: 'p3' })

CREATE (r1:Release { version: '1.0.0' })
CREATE (r2_1:Release { version: '1.0.0' })
CREATE (r2_2:Release { version: '1.0.1' })
CREATE (r3_1:Release { version: '1.0.0' })
CREATE (r3_2:Release { version: '1.1.0' })

CREATE (p1)-[:HAS_RELEASE]->(r1)
CREATE (p2)-[:HAS_RELEASE]->(r2_1)
CREATE (p2)-[:HAS_RELEASE]->(r2_2)
CREATE (p3)-[:HAS_RELEASE]->(r3_1)
CREATE (p3)-[:HAS_RELEASE]->(r3_2)

CREATE   (r1)-[:DEPENDS_ON]->(r2_1)
CREATE (r2_1)-[:DEPENDS_ON]->(r3_1)
CREATE (r2_2)-[:DEPENDS_ON]->(r3_2)

@ 

[Cobra]

Thank you, for this dataset, what should be the result?

[jgaskins]

We need to figure out the ideal set of releases given some spec (the dependencies parameter in the original post, representing my application's first-order dependencies). If my application depends on p1, I would expect to get r1 and the latest p2 and p3 releases (r2_2 and r3_2, respectively).

Ideally, the query returns a flat list of Release nodes that represent the canonical dependencies, as in my original example.

[Cobra]

Would it be possible for you to add a property on Release node to be able to compare like them. You could call it order, the objective is to know that r2_2 > r2_1.

[jgaskins]

That’s the purpose of the version property on Release nodes.

[Cobra]

Yeah I know but you never know what could happen with string values:)

[Cobra]

This query should solve your issue:

MATCH (p:Package {name: "p1"})
CALL apoc.path.subgraphNodes(p, {
    relationshipFilter: "HAS_RELEASE|DEPENDS_ON>",
    bfs: false
})
YIELD node
WHERE node:Package
WITH node AS package
CALL {
    WITH package
    MATCH (package)-[:HAS_RELEASE]->(r:Release)
    RETURN max(r.version) AS version
}
RETURN package.name AS name, version ORDER BY name DESC

Regards,
Cobra