Approximation algorithms for the node coloring problem in graphs. More...

#include <ogdf/graphalg/NodeColoringWigderson.h>

Inheritance diagram for ogdf::NodeColoringWigderson:

Classes
struct	SearchWrapperWigderson
	Wraps the Wigderson recursive algorithm. More...

Public Types
enum class	BruteForceProcedure { sequentialColoringSimple , sequentialColoringDegree , pooled }
	Declares the procedure dealing with the brute force coloring. More...

enum class	MaxDegreeProcedure { smallestIndex , minDegreeRecursion , maxDegreeRecursion , minDegreeOriginal , maxDegreeOriginal , minDegreeNeighbors , maxDegreeNeighbors }
	Declares procedure to find the maximum degree nodes. More...

enum class	RecursionAnchorProcedure { trivialColoring , sequentialColoringSimple , sequentialColoringDegree , pooled }
	Declares the procedure dealing with the recursion anchor coloring. More...

Public Types inherited from ogdf::NodeColoringModule
using	NodeColor = unsigned int
	Data type of the node colors.

enum class	RamseyProcedure { smallestIndex , smallestDegree , largestDegree , extremalDegree }
	Declares the procedure of finding nodes in Ramsey's algorithm. More...

enum class	SearchProcedure { linearSearch , binarySearch , wigdersonSearch }
	Declares the search procedures. More...

Public Member Functions
	NodeColoringWigderson ()
	The constructor.

virtual NodeColor	call (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor start=0) override
	The actual algorithm call.

void	setBruteForceProcedure (BruteForceProcedure bruteForceProcedure)
	Sets the brute force procedure.

void	setMaxDegreeProcedure (MaxDegreeProcedure maxDegreeProcedure)
	Sets the procedure of finding maximum degree nodes.

void	setRecursionAnchorProcedure (RecursionAnchorProcedure recursionAnchorProcedure)
	Sets the recursion anchor procedure.

void	setSearchProcedure (SearchProcedure searchProcedure)
	Sets the search procedure to find the smallest possible parameter k such as the graph is k-colorable.

Public Member Functions inherited from ogdf::NodeColoringModule
	NodeColoringModule ()
	Default constructor.

virtual	~NodeColoringModule ()
	Destructor.

virtual bool	checkColoring (const Graph &graph, const NodeArray< NodeColor > &colors) const
	Checks if the given node coloring is valid.

virtual void	preprocessGraph (Graph &graph) const
	Preprocesses a graph so that a coloring algorithm can be applied.

Private Member Functions
bool	wigdersonCaller (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor &color, int k)
	Calls initially the recursive algorithm of Wigderson.

int	wigdersonFunction (int n, int k) const
	Calculates the function for the graph maximum degree specified by Wigderson.

bool	wigdersonRecursive (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor &color, int k, NodeArray< int > &degreesOriginal, List< node > &nodesToBeColored)
	Calls the recursive algorithm of Wigderson to find a feasible graph coloring.

Private Attributes
BruteForceProcedure	m_bruteForceProcedure

NodeColoringSimple	m_coloringSimple

MaxDegreeProcedure	m_maxDegreeProcedure

RecursionAnchorProcedure	m_recursionAnchorProcedure

SearchProcedure	m_searchProcedure

NodeColoringSequential	m_sequentialColoring

Additional Inherited Members
Protected Member Functions inherited from ogdf::NodeColoringModule
template<class CONTAINER >
bool	checkIndependentSet (const Graph &graph, const CONTAINER &nodes) const
	Checks if subgraph induced by the given nodes forms an independent set.

virtual void	cliqueRemoval (const Graph &graph, List< node > &independentSet) const
	Applies the clique removal algorithm for finding a large independent set in a given graph.

virtual void	createBuckets (const Graph &graph, int size, Array< Array< node > > &buckets) const
	Creates a partitioning of the node set into buckets of a given size.

virtual int	getMaximumDegreeNode (const Graph &graph, node &maxDegreeNode) const
	Searches for a maximum degree node in the graph.

virtual int	getMaximumDegreeNodes (const Graph &graph, List< node > &maxDegreeNodes) const
	Searches for all nodes with maximum degree in the graph.

virtual NodeColor	getMaximumNodeColor (NodeArray< NodeColor > &colors)
	Calculates the maximum node color index used in a certain node coloring.

virtual int	getMinimumDegreeNode (const Graph &graph, node &minDegreeNode) const
	Searches for a minimum degree node in the graph.

virtual int	getMinimumDegreeNodes (const Graph &graph, List< node > &minDegreeNodes) const
	Searches for all nodes with minimum degree in the graph.

int	getNeighborDegrees (const node &v) const
	Calculates the sum of neighbor nodes degrees for a given node v.

template<class LISTITERATOR >
void	getNeighbors (const Graph &graph, LISTITERATOR nodes, List< node > &neighbors) const
	Calculates the set of neighbors Y for a given set of nodes X.

template<class LISTITERATOR >
void	getNeighborsComplement (const Graph &graph, LISTITERATOR nodes, List< node > &complementNeighbors) const
	Calculates the set of complement neighbors Y for a given set of nodes X.

template<class LISTITERATOR >
void	mergeNodeLists (const Graph &graph, LISTITERATOR firstList, LISTITERATOR secondList, List< node > &mergedList) const
	Merges two lists of nodes and deletes the duplicates.

virtual void	ramseyAlgorithm (const Graph &graph, List< node > &clique, List< node > &independentSet) const
	Performs the Ramsey algorithm for finding heuristically large cliques and independents sets in a graph.

virtual void	reverseNodeTable (const Graph &graphOrig, const Graph &graphNew, const NodeArray< node > &orig2New, NodeArray< node > &new2Orig) const
	Reverses the mapping between the nodes sets of a graph and a subgraph.

int	searchBinary (SearchWrapper *searchWrapper, int start, int end) const
	Performs a binary search in a specified range with a given oracle.

int	searchLinear (SearchWrapper *searchWrapper, int start, int end) const
	Performs a linear search in a specified range with a given oracle.

int	searchWigderson (SearchWrapper *searchWrapper) const
	Performs a the search procedure specified by Wigderson.

Protected Attributes inherited from ogdf::NodeColoringModule
RamseyProcedure	m_ramseyProcedure
	The RamseyProcedure to be used to select nodes.

Detailed Description

Approximation algorithms for the node coloring problem in graphs.

This class implements the approximation given by Wigderson which colors the graph recursively until a bipartite graph is reached or the given approximation ratio can be reached by a primitive coloring algorithm.

Definition at line 53 of file NodeColoringWigderson.h.

Member Enumeration Documentation

◆ BruteForceProcedure

enum class ogdf::NodeColoringWigderson::BruteForceProcedure

strong

Declares the procedure dealing with the brute force coloring.

Enumerator
sequentialColoringSimple	Uses sequential coloring with the trivial node permutation.
sequentialColoringDegree	Uses sequential coloring with the nodes sorted decreasing by their degree.
pooled	Pools all nodes from the recursion anchor and then applies sequential coloring.

Definition at line 81 of file NodeColoringWigderson.h.

◆ MaxDegreeProcedure

enum class ogdf::NodeColoringWigderson::MaxDegreeProcedure

strong

Declares procedure to find the maximum degree nodes.

Enumerator
smallestIndex	Use the node with the smallest index.
minDegreeRecursion	Use the node which has the smallest degree in the recursive graph.
maxDegreeRecursion	Use the node which has the largest degree in the recursive graph.
minDegreeOriginal	Use the node which has the smallest degree in the original graph.
maxDegreeOriginal	Use the node which has the largest degree in the original graph.
minDegreeNeighbors	Use the node which neighbors have in sum the smallest degrees.
maxDegreeNeighbors	Use the node which neighbors have in sum the largest degrees.

Definition at line 58 of file NodeColoringWigderson.h.

◆ RecursionAnchorProcedure

enum class ogdf::NodeColoringWigderson::RecursionAnchorProcedure

strong

Declares the procedure dealing with the recursion anchor coloring.

Enumerator
trivialColoring	Uses trivial coloring, i.e. colors each node with a different color.
sequentialColoringSimple	Uses sequential coloring with the trivial node permutation.
sequentialColoringDegree	Uses sequential coloring with the nodes sorted decreasing by their degree.
pooled	Pools all nodes from the recursion anchor and then applies sequential coloring.

Definition at line 71 of file NodeColoringWigderson.h.

Constructor & Destructor Documentation

◆ NodeColoringWigderson()

ogdf::NodeColoringWigderson::NodeColoringWigderson ( )

inline

The constructor.

Initializes the search procedure with the Wigderson-Search by default. Initializes the procedure to find maximum degree nodes with the smallest index procedure.

Definition at line 92 of file NodeColoringWigderson.h.

Member Function Documentation

◆ call()

virtual NodeColor ogdf::NodeColoringWigderson::call	(	const Graph &	graph,
		NodeArray< NodeColor > &	colors,
		NodeColor	start = `0`
	)

overridevirtual

The actual algorithm call.

Parameters

graph	The graph for which the node coloring will be calculated.
colors	The resulting node coloring.
start	The first color index which will be used.

Returns: The number of colors used by the node coloring.

Implements ogdf::NodeColoringModule.

◆ setBruteForceProcedure()

void ogdf::NodeColoringWigderson::setBruteForceProcedure ( BruteForceProcedure bruteForceProcedure )

inline

Sets the brute force procedure.

Parameters

bruteForceProcedure The desired brute force coloring procedure

Definition at line 129 of file NodeColoringWigderson.h.

◆ setMaxDegreeProcedure()

void ogdf::NodeColoringWigderson::setMaxDegreeProcedure ( MaxDegreeProcedure maxDegreeProcedure )

inline

Sets the procedure of finding maximum degree nodes.

Parameters

maxDegreeProcedure The desired maximum degree finding procedure

Definition at line 113 of file NodeColoringWigderson.h.

◆ setRecursionAnchorProcedure()

void ogdf::NodeColoringWigderson::setRecursionAnchorProcedure ( RecursionAnchorProcedure recursionAnchorProcedure )

inline

Sets the recursion anchor procedure.

Parameters

recursionAnchorProcedure The desired recursion anchor coloring procedure

Definition at line 121 of file NodeColoringWigderson.h.

◆ setSearchProcedure()

void ogdf::NodeColoringWigderson::setSearchProcedure ( SearchProcedure searchProcedure )

inline

Sets the search procedure to find the smallest possible parameter k such as the graph is k-colorable.

Parameters

searchProcedure The desired search procedure

Definition at line 105 of file NodeColoringWigderson.h.

◆ wigdersonCaller()

bool ogdf::NodeColoringWigderson::wigdersonCaller	(	const Graph &	graph,
		NodeArray< NodeColor > &	colors,
		NodeColor &	color,
		int	k
	)

private

Calls initially the recursive algorithm of Wigderson.

The result is a certain graph coloring.

Parameters

graph	The input graph to be colored.
colors	The resulting coloring.
color	The start color.
k	The parameter k such that the graph is k-colorable.

Returns: True, iff a coloring was found for the given parameter k.

◆ wigdersonFunction()

int ogdf::NodeColoringWigderson::wigdersonFunction	(	int	n,
		int	k
	)		const

inlineprivate

Calculates the function for the graph maximum degree specified by Wigderson.

Parameters

n	Number of nodes.
k	Parameter, such that the graph is k-colorable.

Returns: The function value.

Definition at line 152 of file NodeColoringWigderson.h.

◆ wigdersonRecursive()

bool ogdf::NodeColoringWigderson::wigdersonRecursive	(	const Graph &	graph,
		NodeArray< NodeColor > &	colors,
		NodeColor &	color,
		int	k,
		NodeArray< int > &	degreesOriginal,
		List< node > &	nodesToBeColored
	)

private

Calls the recursive algorithm of Wigderson to find a feasible graph coloring.

Parameters

graph	The input graph to be colored.
colors	The resulting coloring.
color	The start color.
k	The parameter k such that the graph is k-colorable.
degreesOriginal	The node degrees in the initial original graph.
nodesToBeColored	Resulting list of nodes which need to be colored.

Returns: True, iff a coloring was found for the given parameter k.

Member Data Documentation

◆ m_bruteForceProcedure

BruteForceProcedure ogdf::NodeColoringWigderson::m_bruteForceProcedure

private

Definition at line 142 of file NodeColoringWigderson.h.

◆ m_coloringSimple

NodeColoringSimple ogdf::NodeColoringWigderson::m_coloringSimple

private

Definition at line 137 of file NodeColoringWigderson.h.

◆ m_maxDegreeProcedure

MaxDegreeProcedure ogdf::NodeColoringWigderson::m_maxDegreeProcedure

private

Definition at line 140 of file NodeColoringWigderson.h.

◆ m_recursionAnchorProcedure

RecursionAnchorProcedure ogdf::NodeColoringWigderson::m_recursionAnchorProcedure

private

Definition at line 141 of file NodeColoringWigderson.h.

◆ m_searchProcedure

SearchProcedure ogdf::NodeColoringWigderson::m_searchProcedure

private

Definition at line 139 of file NodeColoringWigderson.h.

◆ m_sequentialColoring

NodeColoringSequential ogdf::NodeColoringWigderson::m_sequentialColoring

private

Definition at line 138 of file NodeColoringWigderson.h.

The documentation for this class was generated from the following file:

include/ogdf/graphalg/NodeColoringWigderson.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ BruteForceProcedure

◆ MaxDegreeProcedure

◆ RecursionAnchorProcedure

Constructor & Destructor Documentation

◆ NodeColoringWigderson()

Member Function Documentation

◆ call()

◆ setBruteForceProcedure()

◆ setMaxDegreeProcedure()

◆ setRecursionAnchorProcedure()

◆ setSearchProcedure()

◆ wigdersonCaller()

◆ wigdersonFunction()

◆ wigdersonRecursive()

Member Data Documentation

◆ m_bruteForceProcedure

◆ m_coloringSimple

◆ m_maxDegreeProcedure

◆ m_recursionAnchorProcedure

◆ m_searchProcedure

◆ m_sequentialColoring

Open
Graph Drawing
Framework