Skip to main content

The graph_coloring module

color_graph(context, parameters, edge_property)#

A procedure that performs the graph coloring algorithm.

Parameters

  • context (mgp.ProcCtx) โ€“ The context of the procedure being executed.
  • parameters (mgp.Map) โ€“ (default={}) A dictionary that specifies the algorithm configuration. Configuration parameters are explained in the table below.
NameTypeDefaultDescription
algorithmStringQAAn optimization strategy used to find graph coloring.
no_of_colorsInteger10The number of colors used to color the nodes of the graph.
no_of_processesInteger1The number of processes used to execute the algorithm in parallel.
population_sizeInteger15The number of different solutions that are improved through iterations.
population_factoryStringChainChunkFactoryThe name of a function that generates an initial population.
init_algorithmsList[String][SDO, LDO]Contains algorithms used to initialize the solutions.
errorStringConflictErrorThe name of an error function that is minimized by an optimization strategy.
max_iterationsInteger10The maximum number of iterations of an algorithm.
iteration_callbacksList[String][]Contains iteration callbacks. Iteration callback is called after each iteration of the iterative algorithm. Iteration callback saves certain population information and calls specified actions if certain conditions are met.
communication_delayInteger10The number of iterations that must pass for neighboring parts to exchange solutions.
logging_delayInteger10The number of iteration after the algorithm information is logged.
QA_temperatureFloat0.035The temperature parameter of the quantum annealing algorithm.
QA_max_stepsFloat10The maximum number of steps in one iteration.
conflict_err_alphaFloat0.1The number that scales the sum of the conflicting edges in the error function formula.
conflict_err_betaFloat0.001The number that scales the correlation between solutions in the error function formula.
mutationStringSimpleMutationThe name of a function that changes the solutions.
multiple_mutation_no_of_nodesInteger2The number of nodes that will change color.
random_mutation_probabilityFloat0.1The probability that the color of the random node (it does not have to be conflicting) will be changed.
simple_tunneling_mutationStringMultipleMutationThe name of a mutation function.
simple_tunneling_probabilityFloat0.5The probability of changing an individual.
simple_tunneling_error_correctionFloat2The mutated individual is accepted only if its error is less than the error of the old individual multiplied by this parameter.
simple_tunneling_max_attemptsInteger25The maximum number of mutation attempts until the individual is accepted.
convergence_callback_toleranceInteger500The maximum number of iterations in which if the algorithm does not find a better solution convergence occurs and defined actions are called.
convergence_callback_actionsString[SimpleTunneling]Actions that are called when convergence is detected.
  • edge_property (str) โ€“ (default="weight") A string that determines the edge attribute that stores the edge weight. Any edge attribute not present defaults to 1.

Returns

The return value of the procedure is a map that contains the mapping of nodes to colors.

Return type

mgp.Record(node=str, color=str)

Example

The procedure can be invoked in Cypher using the following query:

CALL graph_coloring.color_graph() YIELD *;

color_subgraph(context, vertices, edges, parameters, edge_property)#

A procedure that performs graph coloring algorithm on the given subgraph.

Parameters

  • context (mgp.ProcCtx) โ€“ The context of the procedure being executed.
  • vertices (mgp.List[mgp.Vertex]) - List of vertices in the subgraph.
  • edges (mgp.List[mgp.Edge]) โ€“ List of edges in the subgraph.
  • parameters (mgp.Map) โ€“ (default={}) A dictionary that specifies the algorithm configuration. Configuration parameters are explained in the table below.
NameTypeDefaultDescription
algorithmStringQAAn optimization strategy used to find graph coloring.
no_of_colorsInteger10The number of colors used to color the nodes of the graph.
no_of_processesInteger1The number of processes used to execute the algorithm in parallel.
population_sizeInteger15The number of different solutions that are improved through iterations.
population_factoryStringChainChunkFactoryThe name of a function that generates an initial population.
init_algorithmsList[String][SDO, LDO]Contains algorithms used to initialize the solutions.
errorStringConflictErrorThe name of an error function that is minimized by an optimization strategy.
max_iterationsInteger10The maximum number of iterations of an algorithm.
iteration_callbacksList[String][]Contains iteration callbacks. Iteration callback is called after each iteration of the iterative algorithm. Iteration callback saves certain population information and calls specified actions if certain conditions are met.
communication_delayInteger10The number of iterations that must pass for neighboring parts to exchange solutions.
logging_delayInteger10The number of iteration after the algorithm information is logged.
QA_temperatureFloat0.035The temperature parameter of the quantum annealing algorithm.
QA_max_stepsFloat10The maximum number of steps in one iteration.
conflict_err_alphaFloat0.1The number that scales the sum of the conflicting edges in the error function formula.
conflict_err_betaFloat0.001The number that scales the correlation between solutions in the error function formula.
mutationStringSimpleMutationThe name of a function that changes the solutions.
multiple_mutation_no_of_nodesInteger2The number of nodes that will change color.
random_mutation_probabilityFloat0.1The probability that the color of the random node (it does not have to be conflicting) will be changed.
simple_tunneling_mutationStringMultipleMutationThe name of a mutation function.
simple_tunneling_probabilityFloat0.5The probability of changing an individual.
simple_tunneling_error_correctionFloat2The mutated individual is accepted only if its error is less than the error of the old individual multiplied by this parameter.
simple_tunneling_max_attemptsInteger25The maximum number of mutation attempts until the individual is accepted.
convergence_callback_toleranceInteger500The maximum number of iterations in which if the algorithm does not find a better solution convergence occurs and defined actions are called.
convergence_callback_actionsString[SimpleTunneling]Actions that are called when convergence is detected.
  • edge_property (str) โ€“ (default="weight") A string that determines the edge attribute that stores the edge weight. Any edge attribute not present defaults to 1.

Returns

The return value of the procedure is a map that contains the mapping of nodes to colors.

Return type

mgp.Record(node=str, color=str)

Example

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