Graph colouring: Difference between revisions
Content added Content deleted
m (→{{header|Raku}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 947: | Line 947: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
<lang zkl> |
<lang zkl>fcn colorGraph(nodeStr){ // "0-1 1-2 2-0 3" |
||
numEdges,graph := 0,Dictionary(); // ( 0:(1,2), 1:L(0,2), 2:(1,0), 3:() ) |
|||
⚫ | |||
foreach n in (nodeStr.split(" ")){ // parse string to graph |
|||
n=n - " "; |
|||
if(n.holds("-")){ |
|||
a,b := n.split("-"); // keep as string |
|||
graph.appendV(a,b); graph.appendV(b,a); |
|||
numEdges+=1; |
|||
} |
|||
else graph[n]=T; // island |
|||
} |
|||
colors,colorPool := Dictionary(), ["A".."Z"].walk(); |
|||
graph.pump(Void,'wrap([(node,nbrs)]){ // ( "1",(0,2), "3",() ) |
|||
clrs:=colorPool.copy(); // all colors are available, then remove neighbours |
|||
foreach i in (nbrs){ clrs.remove(colors.find(i)) } // if nbr has color, color not available |
|||
colors[node] = clrs[0]; // first available remaining color |
|||
}); |
|||
return(graph,colors,numEdges) |
|||
⚫ | |||
<lang zkl>fcn printColoredGraph(graphStr){ |
|||
graph,colors,numEdges := colorGraph(graphStr); |
|||
nodes:=graph.keys.sort(); |
|||
println("Graph: ",graphStr); |
|||
println("Node/color: ", |
|||
nodes.pump(List,'wrap(v){ String(v,"/",colors[v]) }).concat(", ")); |
|||
println("Node : neighbours --> colors:"); |
|||
foreach node in (nodes){ |
|||
ns:=graph[node]; |
|||
println(node," : ",ns.concat(" ")," --> ", |
|||
colors[node]," : ",ns.apply(colors.get).concat(" ")); |
|||
} |
|||
println("Number nodes: ",nodes.len()); |
|||
println("Number edges: ",numEdges); |
|||
println("Number colors: ", |
|||
colors.values.pump(Dictionary().add.fp1(Void)).len()); // create set, count |
|||
println(); |
|||
}</lang> |
|||
{{out}} |
{{out}} |
||
<pre style="height:45ex"> |
|||
<pre> |
|||
Graph: 0-1 1-2 2-0 3 |
|||
Node/color: 0/A, 1/B, 2/C, 3/A |
|||
Node : neighbours --> colors: |
|||
0 : 1 2 --> A : B C |
|||
1 : 0 2 --> B : A C |
|||
2 : 1 0 --> C : B A |
|||
3 : --> A : |
|||
Number nodes: 4 |
|||
Number edges: 3 |
|||
Number colors: 3 |
|||
Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7 |
|||
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B |
|||
Node : neighbours --> colors: |
|||
1 : 6 7 8 --> A : B B B |
|||
2 : 5 7 8 --> A : B B B |
|||
3 : 5 6 8 --> A : B B B |
|||
4 : 5 6 7 --> A : B B B |
|||
5 : 2 3 4 --> B : A A A |
|||
6 : 1 3 4 --> B : A A A |
|||
7 : 1 2 4 --> B : A A A |
|||
8 : 1 2 3 --> B : A A A |
|||
Number nodes: 8 |
|||
Number edges: 12 |
|||
Number colors: 2 |
|||
Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6 |
|||
Node/color: 1/A, 2/A, 3/B, 4/B, 5/C, 6/C, 7/D, 8/D |
|||
Node : neighbours --> colors: |
|||
1 : 4 6 8 --> A : B C D |
|||
2 : 3 5 7 --> A : B C D |
|||
3 : 2 6 8 --> B : A C D |
|||
4 : 1 5 7 --> B : A C D |
|||
5 : 2 4 8 --> C : A B D |
|||
6 : 1 3 7 --> C : A B D |
|||
7 : 2 4 6 --> D : A B C |
|||
8 : 1 3 5 --> D : A B C |
|||
Number nodes: 8 |
|||
Number edges: 12 |
|||
Number colors: 4 |
|||
Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7 |
|||
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B |
|||
Node : neighbours --> colors: |
|||
1 : 6 7 8 --> A : B B B |
|||
2 : 5 7 8 --> A : B B B |
|||
3 : 5 6 8 --> A : B B B |
|||
4 : 5 6 7 --> A : B B B |
|||
5 : 2 3 4 --> B : A A A |
|||
6 : 1 3 4 --> B : A A A |
|||
7 : 1 2 4 --> B : A A A |
|||
8 : 1 2 3 --> B : A A A |
|||
Number nodes: 8 |
|||
Number edges: 12 |
|||
Number colors: 2 |
|||
</pre> |
</pre> |