75 lines
19 KiB
Plaintext
75 lines
19 KiB
Plaintext
(phixonline)-->
|
|
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Graph_colouring.exw</span>
|
|
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
|
|
0-1 1-2 2-0 3
|
|
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
|
|
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
|
|
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
|
|
"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000080;font-style:italic;">-- fill/try each colours[next], recursing as rqd and saving any improvements.
|
|
-- nodes/links are read-only here, colours is the main workspace, soln/best are
|
|
-- the results, next is 1..length(nodes), and used is length(unique(colours)).
|
|
-- On really big graphs I might consider making nodes..best static, esp colours,
|
|
-- in which case you will probably also want a "colours[next] = 0" reset below.</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
|
|
<span style="color: #000000;">colours</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">while</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">bool</span> <span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">colours</span><span style="color: #0000FF;">[</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
|
|
<span style="color: #008080;">exit</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">avail</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">colours</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">newused</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">used</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newused</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">elsif</span> <span style="color: #000000;">newused</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">newused</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)}</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">rdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">rdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,{})</span>
|
|
<span style="color: #000000;">rdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rdx</span><span style="color: #0000FF;">}</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">tt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">),</span>
|
|
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
|
|
<span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">right</span>
|
|
<span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">left</span>
|
|
<span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">ln</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"test%d: %d nodes, %d edges, "</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">linkcount</span><span style="color: #0000FF;">})</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">colours</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">),</span>
|
|
<span style="color: #000000;">soln</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- fallback solution</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ln</span>
|
|
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d colours:%v\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">))</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<!--
|