Anonymous user
Graph colouring: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|Raku}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 947:
=={{header|zkl}}==
<lang zkl>
numEdges,graph := 0,Dictionary(); // ( 0:(1,2), 1:L(0,2), 2:(1,0), 3:() )
<lang zkl></lang>▼
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}}
<pre style="height:45ex">
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>
| |||