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),