graph_coloring

Graph coloring is the assignment of colors to nodes such that two nodes connected with a relationship don’t have the same color. The goal is to minimize the number of colors while correctly coloring a graph.

Algorithm implementation is inspired by "Quantum Annealing (QA) (opens in a new tab)", a simple metaheuristic frequently used for solving discrete optimization problems.

QA is a simple strategy for exploring a solution space. The main idea is to start a search with several possible solutions. These solutions change through iterations and produce new “better” solutions. Each solution has a particular error value which depends on the error function that the algorithm optimizes. In the graph coloring scenario, the error function is often defined as the number of edges connecting nodes with the same color.

The algorithm is iterative. It applies several simple rules to change solutions in a loop (the same rules are applied multiple times). The algorithm terminates when a stop criterion is met, usually when the error becomes zero. One of the rules could be to randomly select the node involved in a conflict and change its colors.

Changes made in one iteration may not be permanent if they don’t improve the solution. But, with a certain probability, the new solution is accepted even if its error is not reduced. In that way, the algorithm is prevented from converging to local minimums too early.

Procedures

color_graph()

The procedure assigns colors to nodes in the whole graph such that two nodes connected with a relationship don’t have the same color.

Input:

• parameters: Dict[string, Any] (default={}) ➡ A dictionary that specifies the algorithm configuration by listing parameters.
• edge_property: string (default=weight) ➡ Relationship property that stores the relationship weight. Any relationship attribute not present defaults to 1.

Output:

• node: Vertex ➡ Represents the node.
• color: int ➡ Represents the assigned color.

Usage:

Use the following query assign colors:

CALL graph_coloring.color_graph()
YIELD node, color;

color_subgraph()

The procedure assigns colors to nodes in a subgraph such that two nodes connected with a relationship don’t have the same color.

Input:

• vertices: List[Vertex] ➡ List of vertices in the subgraph.
• edges: List[Edge] ➡ List of relationships in the subgraph.
• parameters: Dict[string, Any] (default={}) ➡ A dictionary that specifies the algorithm configuration by listing parameters.
• edge_property: string (default=weight) ➡ Relationship property that stores the relationship weight. Any relationship attribute not present defaults to 1.

Output:

• node: Vertex ➡ Represents the node.

• color: int ➡ Represents the assigned color.

Usage:

Use the following query to assign colors on a subgraph:

MATCH (a)-[e]->(b)
WITH collect(a) as nodes, collect (e) as edges
CALL graph_coloring.color_subgraph(nodes, edges, {no_of_colors: 2})
YIELD node, color;

Parameters

Example

MERGE (a:Node {id: 0}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 4}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 6}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 7}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 8}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 9}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 8}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 0}) MERGE (b:Node {id: 6}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 6}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 0}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 10}) MERGE (b:Node {id: 7}) CREATE (a)-[:RELATION]->(b);

CALL graph_coloring.color_graph({no_of_colors: 4})
YIELD node, color
RETURN node, color;

+-------+-------+
| node  | color |
+-------+-------+
| "130" | "1"   |
| "131" | "3"   |
| "132" | "0"   |
| "133" | "1"   |
| "134" | "2"   |
| "135" | "1"   |
| "136" | "3"   |
| "137" | "0"   |
| "138" | "0"   |
| "139" | "3"   |
| "140" | "1"   |
+-------+-------+