Rosetta Code

Graph colouring: Difference between revisions

Page Discussion

Graph colouring (view source)

Revision as of 11:30, 12 March 2020

4,246 bytes added ,  4 years ago
→‎{{header|Go}}: Now uses both 'greedy' and Welsh-Powell algorithms. Preamble rewritten.
m (Whoops.)
(→‎{{header|Go}}: Now uses both 'greedy' and Welsh-Powell algorithms. Preamble rewritten.)
Line 150:
 
=={{header|Go}}==
AAs difficultymentioned within thisthe task is thatdescription, there is apparently no known ''efficient'' algorithm which can guarantee that a minimum number of colors is used for a given graph. MyThe solutionfollowing isuses based onboth the so-called "'greedy' algorithm" which is(as described [https://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/ here]) and whichthe I'veWelsh-Powell algorithm (as described [http://mrsleblancsmath.pbworks.com/w/file/fetch/46119304/vertex%20coloring%20algorithm.pdf here]), suitably adjusted to the needs of this task.
 
The results are exactly the same for both algorithms. Whilst one would normally expect Welsh-Powell to give better results overall, the last three examples are not well suited to it as each node has exactly the same number of neighbors i.e. the valences are equal.
 
The results agree with the Python entry for examples 1 and 2 but, for example 3, Python gives 2 colors compared to my 4 and, for example 4, Python gives 3 colors compared to my 2.
<lang go>package main
 
import "fmt"(
"fmt"
"sort"
)
 
type graph struct {
Line 163 ⟶ 168:
}
 
type nodeval struct {
func newGraph(nn, st int) *graph {
n int // number of node
v int // valence of node i.e. number of neighbors
}
 
func contains(s []int, n int) bool {
for _, e := range s {
if e == n {
return true
}
}
return false
}
 
func newGraph(nn, st int) graph {
nbr := make([][]int, nn)
return &graph{nn, st, nbr}
}
 
Line 177 ⟶ 196:
}
 
// Uses 'greedy' algorithm.
func (g graph) coloring() []int {
func (g graph) greedyColoring() []int {
// create a slice with a color for each node, starting with color 0
cols := make([]int, g.nn) // all zero by default including the first node
Line 193 ⟶ 213:
}
}
// findfimd the first available color
c := 0
for ; c < g.nn; c++ {
Line 208 ⟶ 228:
}
}
}
return cols
}
 
// Uses Welsh-Powell algorithm.
func (g graph) wpColoring() []int {
// create nodeval for each node
nvs := make([]nodeval, g.nn)
for i := 0; i < g.nn; i++ {
v := len(g.nbr[i])
if v == 1 && g.nbr[i][0] == i { // isolated node
v = 0
}
nvs[i] = nodeval{i, v}
}
// sort the nodevals in descending order by valence
sort.Slice(nvs, func(i, j int) bool {
return nvs[i].v > nvs[j].v
})
// create colors slice with entries for each node
cols := make([]int, g.nn)
for i := range cols {
cols[i] = -1 // set all nodes to no color (-1) initially
}
currCol := 0 // start with color 0
for f := 0; f < g.nn-1; f++ {
h := nvs[f].n
if cols[h] != -1 { // already assigned a color
continue
}
cols[h] = currCol
// assign same color to all subsequent uncolored nodes which are
// not connected to a previous colored one
outer:
for i := f + 1; i < g.nn; i++ {
j := nvs[i].n
if cols[j] != -1 { // already colored
continue
}
for k := f; k < i; k++ {
l := nvs[k].n
if cols[l] == -1 { // not yet colored
continue
}
if contains(g.nbr[j], l) {
continue outer // node j is connected to an earlier colored node
}
}
cols[j] = currCol
}
currCol++
}
return cols
Line 213 ⟶ 284:
 
func main() {
fns := [](func(graph) []int){graph.greedyColoring, graph.wpColoring}
titles := []string{"'Greedy'", "Welsh-Powell"}
nns := []int{4, 8, 8, 8}
starts := []int{0, 1, 1, 1}
Line 222 ⟶ 295:
edges4 := [][2]int{{1, 6}, {7, 1}, {8, 1}, {5, 2}, {2, 7}, {2, 8},
{3, 5}, {6, 3}, {3, 8}, {4, 5}, {4, 6}, {4, 7}}
for ij, edgesfn := range [][][2]int{edges1, edges2, edges3, edges4}fns {
fmt.Println("ExampleUsing the", i+1titles[j], "algorithm:\n")
for i, edges := range [][][2]int{edges1, edges2, edges3, edges4} {
g := newGraph(nns[i], starts[i])
for _, e := rangefmt.Println(" edges {Example", i+1)
g.addEdge := newGraph(enns[0i], estarts[1i])
} for _, e := range edges {
cols := g.coloringaddEdge(e[0], e[1])
ecount := 0 // counts edges
for _, e := range edges {
if e[0] != e[1] {
fmt.Printf(" Edge %d-%d -> Color %d, %d\n", e[0], e[1],
cols[e[0]-g.st], cols[e[1]-g.st])
ecount++
} else {
fmt.Printf(" Node %d -> Color %d\n", e[0], cols[e[0]-g.st])
}
} cols := fn(g)
maxCol ecount := 0 // maximum color numbercounts usededges
for _, cole := range colsedges {
if cole[0] >!= maxCole[1] {
maxCol = col fmt.Printf(" Edge %d-%d -> Color %d, %d\n", e[0], e[1],
cols[e[0]-g.st], cols[e[1]-g.st])
ecount++
} else {
fmt.Printf(" Node %d -> Color %d\n", e[0], cols[e[0]-g.st])
}
}
maxCol := 0 // maximum color number used
for _, col := range cols {
if col > maxCol {
maxCol = col
}
}
fmt.Println(" Number of nodes :", nns[i])
fmt.Println(" Number of edges :", ecount)
fmt.Println(" Number of colors :", maxCol+1)
fmt.Println()
}
fmt.Println(" Number of nodes :", nns[i])
fmt.Println(" Number of edges :", ecount)
fmt.Println(" Number of colors :", maxCol+1)
fmt.Println()
}
}</lang>
Line 254 ⟶ 330:
{{out}}
<pre>
Using the 'Greedy' algorithm:
Example 1
 
Edge 0-1 -> Color 0, 1
Example 1
Edge 1-2 -> Color 1, 2
Edge 2-0-1 -> Color 20, 01
Node 3Edge 1-2 -> Color 01, 2
Edge 2-0 -> Color 2, 0
Number of nodes : 4
Node 3 -> Color 0
Number of edges : 3
Number of colorsnodes : 34
Number of edges : 3
Number of colors : 3
 
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
 
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
 
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
 
Using the Welsh-Powell algorithm:
 
Example 1
Edge 0-1 -> Color 0, 1
Edge 1-2 -> Color 1, 2
Edge 2-0 -> Color 2, 0
Node 3 -> Color 0
Number of nodes : 4
Number of edges : 3
Number of colors : 3
 
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
 
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
 
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
</pre>
 
PureFox
9,487

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/298977"