ColorUsingGreedyApproach will return the Color of each vertex and the total number of different colors used, using a greedy approach, based on the number of edges (or degree) from any vertex.
()
| 11 | // total number of different colors used, using a greedy approach, based on |
| 12 | // the number of edges (or degree) from any vertex. |
| 13 | func (g *Graph) ColorUsingGreedyApproach() (map[int]Color, int) { |
| 14 | degreeOfVertex := make([]struct{ degree, vertex int }, 0, g.vertices) |
| 15 | for v, neighbours := range g.edges { |
| 16 | degreeOfVertex = append(degreeOfVertex, |
| 17 | struct{ degree, vertex int }{ |
| 18 | vertex: v, |
| 19 | degree: len(neighbours), |
| 20 | }, |
| 21 | ) |
| 22 | } |
| 23 | // sort the degreeOfVertex in decreasing order of degrees |
| 24 | sort.Slice(degreeOfVertex, func(i, j int) bool { |
| 25 | return degreeOfVertex[i].degree > degreeOfVertex[j].degree |
| 26 | }) |
| 27 | |
| 28 | vertexColors := make(map[int]Color, g.vertices) |
| 29 | // Start with a color and assign the color to all possible vertices in the degreeOfVertex slice |
| 30 | // and then, re-iterate with new color for all those which are left |
| 31 | for color := 1; color <= g.vertices; color++ { |
| 32 | vertexLoop: |
| 33 | for _, val := range degreeOfVertex { |
| 34 | // skip, if already assigned |
| 35 | if _, ok := vertexColors[val.vertex]; ok { |
| 36 | continue vertexLoop |
| 37 | } |
| 38 | // Check its neighbours |
| 39 | for ng := range g.edges[val.vertex] { |
| 40 | if vertexColors[ng] == Color(color) { |
| 41 | // not possible to use this color for val.vertex |
| 42 | continue vertexLoop |
| 43 | } |
| 44 | } |
| 45 | // Assign color to the vertex |
| 46 | vertexColors[val.vertex] = Color(color) |
| 47 | } |
| 48 | // continue till all the vertices are colored |
| 49 | if len(vertexColors) == g.vertices { |
| 50 | return vertexColors, color |
| 51 | } |
| 52 | } |
| 53 | return vertexColors, g.vertices |
| 54 | } |