coloring

package
v0.0.0-...-a4a72b7 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 23, 2023 License: MIT Imports: 3 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL