This section describes the K-1 Coloring algorithm in the Neo4j Graph Algorithms library.
This topic includes:
The K-1 Coloring algorithm assigns a color to every node in the graph, trying to optimize for two objectives:
Note that the graph coloring problem is proven to be NP-complete, which makes it intractable on anything but trivial graph sizes. For that reason the implemented algorithm is a greedy algorithm. Thus it is neither guaranteed that the result is an optimal solution, using as few colors as theoretically possible, nor does it always produce a correct result where no two neighboring nodes have different colors. However the precision of the latter can be controlled by the number of iterations this algorithm runs.
For more information on this algorithm, see:
Running this algorithm requires sufficient memory availability. Before running this algorithm, we recommend that you read Section 2.4, “Memory Requirements”. |
The following describes the API for running the algorithm and writing results back to Neo4j:
CALL algo.beta.k1coloring(label: STRING, relationship: STRING, {
write: BOOLEAN,
writeProperty: STRING
// additional configuration
})
YIELD nodes, setCount, loadMillis, computeMillis, writeMillis
Name | Type | Default | Optional | Description |
---|---|---|---|---|
node label |
string |
|
yes |
The node label to load from the graph. If |
relationship |
string |
|
yes |
The relationship type to load from the graph. If |
config |
map |
|
yes |
Additional configuration, see below. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
|
int |
available CPUs |
yes |
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see Section 1.4.2, “CPU”. |
|
int |
value of 'concurrency' |
yes |
The number of concurrent threads used for reading the graph. |
|
int |
value of 'concurrency' |
yes |
The number of concurrent threads used for writing the result. |
|
boolean |
|
yes |
Specifies if the result should be written back as a node property. |
|
string |
yes |
The property name written back the ID of the partition particular node belongs to. |
|
|
string |
|
yes |
Use |
|
int |
10 |
yes |
The maximum number of iterations the algorithms runs with. |
|
int |
10_000 |
yes |
Controls the the number of relationships each parallel thread processes. |
Name | Type | Description |
---|---|---|
|
int |
Milliseconds for loading data. |
|
int |
Milliseconds for running the algorithm. |
|
int |
Milliseconds for writing result data back. |
|
int |
The number of nodes considered. |
|
int |
The actual number of iterations the algorithm ran. |
|
boolean |
An indicator of whether the algorithm found a correct coloring. |
|
int |
The number of colors used. |
|
boolean |
Specifies if the result was written back as a node property. |
|
string |
The property name written back to. |
The following describes the API for running the algorithm and stream results:
CALL algo.beta.k1coloring.stream(label: STRING, relationship: STRING, {
// configuration
})
YIELD nodeId, color
Name | Type | Default | Optional | Description |
---|---|---|---|---|
node label |
string |
|
yes |
The node label to load from the graph. If null, load all nodes. |
relationship type |
string |
|
yes |
The relationship type to load from the graph. If null, load all relationships. |
config |
map |
|
yes |
Additional configuration, see below. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
|
int |
available CPUs |
yes |
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see Section 1.4.2, “CPU”. |
|
int |
value of 'concurrency' |
yes |
The number of concurrent threads used for reading the graph. |
|
string |
|
yes |
Use |
|
int |
10 |
yes |
The maximum number of iterations the algorithms runs with. |
|
int |
10_000 |
yes |
Controls the the number of relationships each parallel thread processes. |
Name | Type | Description |
---|---|---|
|
int |
Node ID |
|
int |
Color ID |
Consider the graph created by the following Cypher statement:
CREATE (nAlice:User {name: 'Alice'})
CREATE (nBridget:User {name: 'Bridget'})
CREATE (nCharles:User {name: 'Charles'})
CREATE (nDoug:User {name: 'Doug'})
CREATE (nAlice)-[:LINK]->(nBridget)
CREATE (nAlice)-[:LINK]->(nCharles)
CREATE (nAlice)-[:LINK]->(nDoug)
CREATE (nBridget)-[:LINK]->(nCharles)
This graph has a super node with name "Alice" that connects to all other nodes. It should therefore not be possible for any other node to be assigned to the color as the Alice node. In the following examples we will demonstrate using the K-1 Coloring algorithm on this graph.
In the examples below, we will rely on the implicit loading of graphs for the algorithm computation. However, like other algorithms K-1 Coloring also accepts named graphs and Cypher projections as inputs. See Projected Graph Model for more details.
Using a named graph:
CALL algo.graph.load('myGraph', 'User', 'LINK');
CALL algo.k1coloring.stream(null, null, {graph: 'myGraph'})
YIELD nodeId, color
RETURN algo.asNode(nodeId).name AS Name, color AS Color
ORDER BY Name;
Name | Color |
---|---|
|
|
|
|
|
|
|
|
Using a Cypher projection:
CALL algo.k1coloring.stream(
'MATCH (u:User) RETURN id(u) AS id',
'MATCH (u1:User)-[:LINK]->(u2:User)
RETURN id(u1) AS source, id(u2) AS target',
{graph:'cypher'}
)
YIELD nodeId, color
RETURN algo.asNode(nodeId).name AS Name, color AS Color
ORDER BY Name
Name | Color |
---|---|
|
|
|
|
|
|
|
|
These results are identical to those of the named graph, as the Cypher projection we use mimics the behaviour of the default loading configuration. Of course, the Cypher projection feature enables more advanced control over which exact parts of the graph to compute over; please see Section 2.2, “Cypher projection” for more details.