Local Color ----------- You have been asked to write a program that will run as a local algorithm in a network of processors and improve a coloring of the network graph. A network graph is an undirected graph. The vertices are called nodes and the edges are called connections. Two nodes sharing a connection are neighbors. The number of connections attached to a node is the degree of the node, and the degree of the network, denoted by D, is the maximum degree of any node. If a node has degree d, we identify its connections by integers in the range 0, ..., d-1. The number of nodes in the network is N, and we identify nodes by integers in the range 0, ..., N-1. A coloring is an assignment of a color to each node such that NO neighbors have the same color. If there are C colors, we represent the colors by integers in the range 0, ..., C-1. The problem is that given a coloring with C > D+1 colors, improve the coloring to one with at most D+1 colors, using a local distributed algorithm. A local distributed algorithm is a deterministic program code that runs at each node and executes in K cycles. At the beginning of each cycle but the first each node receives a message from each of its neighbors. The node then computes and for each cycle but the last, outputs a message for each of its neighbors. At the beginning of the first cycle each node receives a single input message and at the end of the last cycle each node outputs a single output message. Your program executes one cycle at one node, and is invoked by the judge's `monitor' program K*N times to perform the local distributed computation and produce an answer. Importantly, in our problem K is set equal to C, the number of original colors. Messages are single lines of ASCII text whose maximum length is 1,000 characters. Each node has a memory that is represented as a message from the node to itself, i.e., is output by the node at the end of a cycle and input by the node at the beginning of its next cycle. Your program is called by a monitor program in order to execute each cycle of each node. The monitor pro- gram, which is named `localcolor_network', is provided by the judge. Your program is named `localcolor'. You can invoke these programs by the command localcolor_network localcolor Input to Your Program ----- -- ---- ------- For each cycle of each node, first a line containing the following information: N K node_id node_degree cycle_number where N is the total number of nodes, K the total number of cycles, the N nodes have node_id's in the range 0, ..., N-1, and the K cycles are number 0, ..., K-1. Then for the first cycle (cycle 0) a single line. C initial_node_color where C is the initial number of node colors and the node is given an initial color in the range 0, ..., C-1. For cycles other than the first, the above first input line is followed by lines containing messages output by the previous cycle. The first of these is a line that contains the contents of the memory of the node at the end of the previous cycle (the message from the node to itself). This line is followed by a line for each con- nection containing the message from the connection's neighbor. These connection message lines are in order of the connection number relative to the node, from 0 through node_degree-1. You define the format of all message lines. Message lines may not be longer than 1,000 characters and must contain only printable ASCII characters and single spaces (they need to be printable to debug, and they are not permitted to contain form feeds, line feeds, tabs, or any control character other than single space). Input ends with an end of file, at which point your program should terminate (as there are no more test cases). Output from Your Program ------ ---- ---- ------- The output from your program for all cycles but the last is a sequence of message lines. First, the line con- taining the contents of the node's memory (the message from the node to itself). Then for each connection a line containing the message output by the cycle for the connection. These lines are in order of the connec- tion number, from 0 through node_degree-1. Lastly one line containing just `END' (used to detect bugs). For the last cycle of an algorithm execution output only one line containing just an integer in the range 0, ..., D that is the color of the node after the algorithm has completed, followed by one line containing just `END'. The monitor program will check that two neighbors do not have the same color at this point, and that all colors are in the range 0,..., D. Your algorithm will be declared to be successful for the test case if this is so. Input to the Monitor ----- -- --- ------- For each test case, first a line containing just the test case name. Then a second line containing N D C SEED where N is the number of nodes, D the maximum node degree, C is the number of initial colors, and SEED is a 9-digit unsigned integer that is the seed of a pseudo- random number generator used by the monitor to generate the graph. 2 <= D <= 20 D + 1 <= N <= 1,000 D + 1 < C <= 100 Input ends with an end of file. Output from the Monitor ------ ---- --- ------- For each test case, first a copy of the test case input lines, and then a line containing just `OK' if the solution is a coloring with D+1 colors, or a line containing FAILED node n1 and neighbor n2 both colored c if neighboring nodes n1 and n2 were both colored c, or a line containing FAILED node n colored c if node n was colored with c < 0 or c > D. If there was some error in message format, the output will be FAILED ... where ... describes the error. Debugging --------- You can add debugging arguments to the program command: localcolor_network localcolor debug_argument ... If you do this your program will be invoked by the monitor using the command localcolor debug_argument ... and the monitor will output the input and output for each node and cycle in addition to the usual output of the monitor. The input/output for a node and cycle is surrounded by lines containing just `*****' and the input is separated from the output by a line containing just `-----'. You can put debugging information in your messages, and used the debug arguments to tune this information. Sample Input ------ ----- -- SAMPLE 1 -- 10 3 20 783927645 -- SAMPLE 2 -- 20 10 50 259140687 Sample Output ------ ------ -- SAMPLE 1 -- OK -- SAMPLE 2 -- OK Reference --------- For a discussion of local distributed algorithms, more examples, and impossibility results see A Survey of Local Algorithms, Jukka Suomela, ACM Computing Surveys, Vol. 45, No. 2, 2013. File: localcolor.txt Author: Bob Walton Date: Mon Oct 14 02:53:43 EDT 2013 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2013/10/14 07:10:46 $ $RCSfile: localcolor.txt,v $ $Revision: 1.9 $