This section describes the Collapse Path algorithm in the Neo4j Graph Data Science library.
This topic includes:
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.
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
Name | Type | Default | Optional | Description |
---|---|---|---|---|
graphName |
String |
|
no |
The name of a graph stored in the catalog. |
configuration |
Map |
|
yes |
Configuration for algorithm-specifics and/or graph filtering. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
nodeLabels |
String[] |
|
yes |
Filter the named graph using the given node labels. |
concurrency |
Integer |
|
yes |
The number of concurrent threads used for running the algorithm. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
relationshipTypes |
String[] |
|
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 |
|
no |
Relationship type of the newly created relationships. |
allowSelfLoops |
Boolean |
|
yes |
Indicates whether it is possible to create self referencing relationships, i.e. relationships where the start and end node are identical. |
Name | Type | Description |
---|---|---|
|
Integer |
Milliseconds for loading data. |
|
Integer |
Milliseconds for running the algorithm. |
|
Integer |
Milliseconds for adding properties to the in-memory graph. |
|
Integer |
The number of relationships created by the algorithm. |
|
Map |
The configuration used for running the algorithm. |
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
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),