coloring

Documentation

Overview

Package coloring provides implementation of different graph coloring algorithms, e.g. coloring using BFS, using Backtracking, using greedy approach. Author(s): [Shivam](https://github.com/Shivam010)

Index

• func BipartiteCheck(N int, edges [][]int) bool
• type Color
• type Graph
  • func (g *Graph) AddEdge(one, two int)
  • func (g *Graph) AddVertex(v int)
  • func (g *Graph) ColorUsingBFS() (map[int]Color, int)
  • func (g *Graph) ColorUsingBacktracking() (map[int]Color, int)
  • func (g *Graph) ColorUsingGreedyApproach() (map[int]Color, int)
  • func (g *Graph) TryBipartiteColoring() map[int]Color
  • func (g *Graph) ValidateColorsOfVertex(colors map[int]Color) error

Functions

func BipartiteCheck

func BipartiteCheck(N int, edges [][]int) bool

basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartite

Types

type Color

type Color int

Color provides a type for vertex color

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph provides a structure to store an undirected graph. It is safe to use its empty object.

func (*Graph) AddEdge

func (g *Graph) AddEdge(one, two int)

AddEdge will add a new edge between the provided vertices in the graph

func (*Graph) AddVertex

func (g *Graph) AddVertex(v int)

AddVertex will add a new vertex in the graph, if the vertex already exist it will do nothing

func (*Graph) ColorUsingBFS

func (g *Graph) ColorUsingBFS() (map[int]Color, int)

ColorUsingBFS will return the Color of each vertex and the total number of different colors used, using BFS

func (*Graph) ColorUsingBacktracking

func (g *Graph) ColorUsingBacktracking() (map[int]Color, int)

ColorUsingBacktracking will return the Color of each vertex and the total number of different colors used, using backtracking

func (*Graph) ColorUsingGreedyApproach

func (g *Graph) ColorUsingGreedyApproach() (map[int]Color, int)

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.

func (*Graph) TryBipartiteColoring

func (g *Graph) TryBipartiteColoring() map[int]Color

func (*Graph) ValidateColorsOfVertex

func (g *Graph) ValidateColorsOfVertex(colors map[int]Color) error