8.1. The K-1 Coloring algorithm

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

This topic includes:

Introduction
Syntax
Examples

8.1.1. Introduction

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

To make sure that every neighbor of a given node has a different color than the node itself.
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.