Collapse Path

This section describes the Collapse Path algorithm in the Neo4j Graph Data Science library.

1. Introduction

The Collapse Path algorithm is a traversal algorithm capable of creating relationships between the start and end nodes of a traversal. In other words, the path between the start node and the end node is collapsed into a single relationship (a direct path). The algorithm is intended to support the creation of monopartite graphs required by many graph algorithms.

The main input for the algorithm is a list of relationship types. Starting from every node in the specified graph, these relationship types are traversed one after the other using the order specified in the configuration. Only nodes reached after traversing every relationship type specified are used as end nodes. Exactly one relationship is created for every pair of nodes for which at least one path from start to end node exists.

2. Syntax

Example 1. Collapse Path syntax per mode

Run Collapse Path in mutate mode on a named graph.

CALL gds.alpha.collapsePath.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  createMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

Table 1. Parameters
Name	Type	Default	Optional	Description
graphName	String	`n/a`	no	The name of a graph stored in the catalog.
configuration	Map	`{}`	yes	Configuration for algorithm-specifics and/or graph filtering.

Table 2. General configuration for algorithm execution on a named graph.
Name	Type	Default	Optional	Description
nodeLabels	String[]	`['*']`	yes	Filter the named graph using the given node labels.
concurrency	Integer	`4`	yes	The number of concurrent threads used for running the algorithm.

Table 3. Algorithm specific configuration
Name	Type	Default	Optional	Description
relationshipTypes	String[]	`n/a`	no	Ordered list of relationship types used for the traversal. The same relationship type can be added multiple times, in order to traverse them as indicated.
mutateRelationshipType	String	`n/a`	no	Relationship type of the newly created relationships.
allowSelfLoops	Boolean	`false`	yes	Indicates whether it is possible to create self referencing relationships, i.e. relationships where the start and end node are identical.

Table 4. Results
Name	Type	Description
`createMillis`	Integer	Milliseconds for loading data.
`computeMillis`	Integer	Milliseconds for running the algorithm.
`mutateMillis`	Integer	Milliseconds for adding properties to the in-memory graph.
`relationshipsWritten`	Integer	The number of relationships created by the algorithm.
`configuration`	Map	The configuration used for running the algorithm.

3. Examples

Consider the graph created by the following Cypher statement:

CREATE
  (Dan:Person),
  (Annie:Person),
  (Matt:Person),
  (Jeff:Person),

  (Guitar:Instrument),
  (Flute:Instrument),

  (Dan)-[:PLAYS]->(Guitar),
  (Annie)-[:PLAYS]->(Guitar),

  (Matt)-[:PLAYS]->(Flute),
  (Jeff)-[:PLAYS]->(Flute)

In this example we want to create a relationship, called PLAYS_SAME_INSTRUMENT, between Person nodes that play the same instrument. To achieve that we have to traverse a path specified by the following Cypher pattern:

(p1:Person)-[:PLAYS]->(:Instrument)-[:PLAYED_BY]->(p2:Person)

In our source graph only the PLAYS relationship type exists. The PLAYED_BY relationship type can be created by loading the PLAYS relationship type in REVERSE direction. The following query will create such a graph:

CALL gds.graph.create(
  'persons',
  ['Person', 'Instrument'],
  {
    PLAYS: {
      type: 'PLAYS',
      orientation: 'NATURAL'
    },
    PLAYED_BY: {
      type: 'PLAYS',
      orientation: 'REVERSE'
    }
})

Now we can run the algorithm by specifying the traversal PLAYS, PLAYED_BY in the relationshipTypes option.

CALL gds.alpha.collapsePath.mutate(
  'persons',
  {
    relationshipTypes: ['PLAYS', 'PLAYED_BY'],
    allowSelfLoops: false,
    mutateRelationshipType: 'PLAYS_SAME_INSTRUMENT'
  }
) YIELD relationshipsWritten

Table 5. Results
relationshipsWritten
4

The mutated graph will look like the following graph when filtered by the PLAYS_SAME_INSTRUMENT relationship

CREATE
  (Dan:Person),
  (Annie:Person),
  (Matt:Person),
  (Jeff:Person),

  (Guitar:Instrument),
  (Flute:Instrument),

  (Dan)-[:PLAYS_SAME_INSTRUMENT]->(Annie),
  (Annie)-[:PLAYS_SAME_INSTRUMENT]->(Dan),

  (Matt)-[:PLAYS_SAME_INSTRUMENT]->(Jeff),
  (Jeff)-[:PLAYS_SAME_INSTRUMENT]->(Matt),

Was this page helpful?