8.1. The K-1 Coloring algorithm

This section describes the K-1 Coloring algorithm in the Neo4j Graph Algorithms library.

This topic includes:

8.1.1. Introduction

The K-1 Coloring algorithm assigns a color to every node in the graph, trying to optimize for two objectives:

  1. To make sure that every neighbor of a given node has a different color than the node itself.
  2. To use as few colors as possible.

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”.

8.1.2. Syntax

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

Table 8.1. Parameters
Name Type Default Optional Description

node label

string

null

yes

The node label to load from the graph. If null, load all nodes.

relationship

string

null

yes

The relationship type to load from the graph. If null, load all relationships.

config

map

{}

yes

Additional configuration, see below.

Table 8.2. Configuration
Name Type Default Optional Description

concurrency

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”.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

writeConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for writing the result.

write

boolean

true

yes

Specifies if the result should be written back as a node property.

writeProperty

string

 

yes

The property name written back the ID of the partition particular node belongs to.

graph

string

'huge'

yes

Use 'huge' when describing the subset of the graph with node label and relationship type parameters. Use 'cypher' for describing the subset using Cypher queries for nodes and relationships.

iterations

int

10

yes

The maximum number of iterations the algorithms runs with.

batchSize

int

10_000

yes

Controls the the number of relationships each parallel thread processes.

Table 8.3. Results
Name Type Description

loadMillis

int

Milliseconds for loading data.

computeMillis

int

Milliseconds for running the algorithm.

writeMillis

int

Milliseconds for writing result data back.

nodes

int

The number of nodes considered.

ranIterations

int

The actual number of iterations the algorithm ran.

didConverge

boolean

An indicator of whether the algorithm found a correct coloring.

colorCount

int

The number of colors used.

write

boolean

Specifies if the result was written back as a node property.

writeProperty

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

Table 8.4. Parameters
Name Type Default Optional Description

node label

string

null

yes

The node label to load from the graph. If null, load all nodes.

relationship type

string

null

yes

The relationship type to load from the graph. If null, load all relationships.

config

map

{}

yes

Additional configuration, see below.

Table 8.5. Configuration
Name Type Default Optional Description

concurrency

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”.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

graph

string

'huge'

yes

Use 'huge' when describing the subset of the graph with node label and relationship type parameters. Use 'cypher' for describing the subset using Cypher queries for nodes and relationships.

iterations

int

10

yes

The maximum number of iterations the algorithms runs with.

batchSize

int

10_000

yes

Controls the the number of relationships each parallel thread processes.

Table 8.6. Results
Name Type Description

nodeId

int

Node ID

color

int

Color ID

8.1.3. Examples

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.

8.1.3.1. Named graphs and Cypher projections

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;

Table 8.7. Results
Name Color

"Alice"

2

"Bridget"

1

"Charles"

0

"Doug"

0

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

Table 8.8. Results
Name Color

"Alice"

2

"Bridget"

1

"Charles"

0

"Doug"

0

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.