colour_graph: Greedy graph colouring algorithm

In shazhe/mvst0: Multi-variate ST modelling on globe

Description

This algorithm colours the nodes in sequential order, where the order is given through a breadth first search algorithm started on a pre-specified start-node.

Usage

colour_graph(adj.matrix, numcolours, method = "BFS", startnode = 1,
  obs = NULL)

Arguments

adj.matrix	the graphs adjacency matrix (usually sparse)
numcolours	the maximum number of colours to try out with the BFS and DSATUR methods. The function gives an error if this is exceeded.
method	takes values "BFS", "DSATUR" or "backtrack" for the breadth-first-search, the maximum-degree-of-saturation and the backtracking respectively. In the latter method, a four-colour configuration is attempted using brute force, where the order is obtained by first running a DSATUR run.
startnode	the starting node for the BFS algorithm
obs	an m x n matrix identifiying which partitions each observations affect. If present, the algorithm will not produce a colouring where an observation influences two or more partitions of the same colour (as such this increases the chromatic number of the problem). This option is only available with BFS and DSATUR

Value

a data frame with the associated colour for each vertex (also class)

Author(s)

Andrew Zammit Mangion

References

http://community.topcoder.com/longcontest/?module=Static&d1=match_editorials&d2=intel_mtcs_10

shazhe/mvst0 documentation built on May 29, 2019, 9:20 p.m.