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

#include <ogdf/graphalg/NodeColoringModule.h>

Inheritance diagram for ogdf::NodeColoringModule:

Classes
struct	SearchWrapper
	Wraps the search for the minimum parameter k so that the same code can be reused for all algorithms. More...

struct	SubsetIterator
	Struct to iterate over all node subsets of a given size. More...

Public Types
using	NodeColor = unsigned int
	Data type of the node colors. More...

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

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

Public Member Functions
	NodeColoringModule ()
	Default constructor. More...

virtual	~NodeColoringModule ()
	Destructor. More...

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

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

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

Protected Member Functions
template<class CONTAINER >
bool	checkIndependentSet (const Graph &graph, const CONTAINER &nodes) const
	Checks if subgraph induced by the given nodes forms an independent set. More...

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. More...

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. More...

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

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

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

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

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

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

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. More...

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. More...

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. More...

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. More...

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. More...

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

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

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

Protected Attributes
RamseyProcedure	m_ramseyProcedure
	The RamseyProcedure to be used to select nodes. More...

Detailed Description

Approximation algorithms for the node coloring problem in graphs.

This is the base class.

Definition at line 44 of file NodeColoringModule.h.

Member Typedef Documentation

◆ NodeColor

using ogdf::NodeColoringModule::NodeColor = unsigned int

Data type of the node colors.

Definition at line 49 of file NodeColoringModule.h.

Member Enumeration Documentation

◆ RamseyProcedure

enum ogdf::NodeColoringModule::RamseyProcedure

strong

Declares the procedure of finding nodes in Ramsey's algorithm.

Enumerator
smallestIndex	Uses the node with the smallest index.
smallestDegree	Uses the node with the smallest degree.
largestDegree	Uses the node with the largest degree.
extremalDegree	Uses the node with the extremal degree.

Definition at line 64 of file NodeColoringModule.h.

◆ SearchProcedure

enum ogdf::NodeColoringModule::SearchProcedure

strong

Declares the search procedures.

Enumerator
linearSearch	Use a linear search.
binarySearch	Use a binary search.
wigdersonSearch	Use the search procedure specified by Wigderson.

Definition at line 54 of file NodeColoringModule.h.

Constructor & Destructor Documentation

◆ NodeColoringModule()

ogdf::NodeColoringModule::NodeColoringModule ( )

inline

Default constructor.

Initializes the Ramsey-procedure with the smallest index procedure.

Definition at line 75 of file NodeColoringModule.h.

◆ ~NodeColoringModule()

virtual ogdf::NodeColoringModule::~NodeColoringModule ( )

inlinevirtual

Destructor.

Definition at line 90 of file NodeColoringModule.h.

Member Function Documentation

◆ call()

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

pure virtual

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.

Implemented in ogdf::NodeColoringWigderson, ogdf::NodeColoringBergerRompel, ogdf::NodeColoringJohnson, ogdf::NodeColoringBoppanaHalldorsson, ogdf::NodeColoringHalldorsson, ogdf::NodeColoringRecursiveLargestFirst, ogdf::NodeColoringSequential, and ogdf::NodeColoringSimple.

◆ checkColoring()

virtual bool ogdf::NodeColoringModule::checkColoring	(	const Graph &	graph,
		const NodeArray< NodeColor > &	colors
	)		const

virtual

Checks if the given node coloring is valid.

Parameters

graph	The graph corresponding to the given coloring.
colors	The given node coloring.

Returns: True, iff the coloring is valid, false otherwise.

◆ checkIndependentSet()

template<class CONTAINER >

bool ogdf::NodeColoringModule::checkIndependentSet	(	const Graph &	graph,
		const CONTAINER &	nodes
	)		const

inlineprotected

Checks if subgraph induced by the given nodes forms an independent set.

Template Parameters

CONTAINER The type of container for the node set

Parameters

graph	The graph
nodes	The subset of nodes

Returns: true, iff the subset is independent

Definition at line 212 of file NodeColoringModule.h.

◆ cliqueRemoval()

virtual void ogdf::NodeColoringModule::cliqueRemoval	(	const Graph &	graph,
		List< node > &	independentSet
	)		const

protectedvirtual

Applies the clique removal algorithm for finding a large independent set in a given graph.

Parameters

graph	The given graph
independentSet	The resulting independent set

◆ createBuckets()

virtual void ogdf::NodeColoringModule::createBuckets	(	const Graph &	graph,
		int	size,
		Array< Array< node >> &	buckets
	)		const

protectedvirtual

Creates a partitioning of the node set into buckets of a given size.

Parameters

graph	The input graph
size	The bucket size
buckets	The resulting bucket partitioning of the nodes

◆ getMaximumDegreeNode()

virtual int ogdf::NodeColoringModule::getMaximumDegreeNode	(	const Graph &	graph,
		node &	maxDegreeNode
	)		const

protectedvirtual

Searches for a maximum degree node in the graph.

Parameters

graph	The input graph.
maxDegreeNode	The resulting maximum degree node.

Returns: The maximum degree of the graph.

◆ getMaximumDegreeNodes()

virtual int ogdf::NodeColoringModule::getMaximumDegreeNodes	(	const Graph &	graph,
		List< node > &	maxDegreeNodes
	)		const

protectedvirtual

Searches for all nodes with maximum degree in the graph.

Parameters

graph	The input graph.
maxDegreeNodes	List of all nodes with maximum degree.

Returns: The maximum degree of the graph.

◆ getMaximumNodeColor()

virtual NodeColor ogdf::NodeColoringModule::getMaximumNodeColor ( NodeArray< NodeColor > & colors )

protectedvirtual

Calculates the maximum node color index used in a certain node coloring.

Parameters

colors The node coloring.

Returns: Maximum node color index.

◆ getMinimumDegreeNode()

virtual int ogdf::NodeColoringModule::getMinimumDegreeNode	(	const Graph &	graph,
		node &	minDegreeNode
	)		const

protectedvirtual

Searches for a minimum degree node in the graph.

Parameters

graph	The input graph.
minDegreeNode	The resulting minimum degree node.

Returns: The minimum degree of the graph.

◆ getMinimumDegreeNodes()

virtual int ogdf::NodeColoringModule::getMinimumDegreeNodes	(	const Graph &	graph,
		List< node > &	minDegreeNodes
	)		const

protectedvirtual

Searches for all nodes with minimum degree in the graph.

Parameters

graph	The input graph.
minDegreeNodes	List of all nodes with minimum degree.

Returns: The minimum degree of the graph.

◆ getNeighborDegrees()

int ogdf::NodeColoringModule::getNeighborDegrees ( const node & v ) const

protected

Calculates the sum of neighbor nodes degrees for a given node v.

Parameters

v	The given node

Returns: The sum of the neighbor's degrees

◆ getNeighbors()

template<class LISTITERATOR >

void ogdf::NodeColoringModule::getNeighbors	(	const Graph &	graph,
		LISTITERATOR	nodes,
		List< node > &	neighbors
	)		const

inlineprotected

Calculates the set of neighbors Y for a given set of nodes X.

Thereby, Y is the union of all neighbors for each node x in X.

Template Parameters

LISTITERATOR The type of iterator for the node set

Parameters

graph	The input graph
nodes	The nodes of whose neighbors will be determined
neighbors	The resulting list of neighbors

Definition at line 247 of file NodeColoringModule.h.

◆ getNeighborsComplement()

template<class LISTITERATOR >

void ogdf::NodeColoringModule::getNeighborsComplement	(	const Graph &	graph,
		LISTITERATOR	nodes,
		List< node > &	complementNeighbors
	)		const

inlineprotected

Calculates the set of complement neighbors Y for a given set of nodes X.

Thereby, Y contains every node which is not in X and is not a neighbor of a node in X.

Template Parameters

LISTITERATOR The type of iterator for the node set

Parameters

graph	The input graph
nodes	The nodes of whose complement neighbors will be determined
complementNeighbors	The resulting list of complement neighbors

Definition at line 286 of file NodeColoringModule.h.

◆ mergeNodeLists()

template<class LISTITERATOR >

void ogdf::NodeColoringModule::mergeNodeLists	(	const Graph &	graph,
		LISTITERATOR	firstList,
		LISTITERATOR	secondList,
		List< node > &	mergedList
	)		const

inlineprotected

Merges two lists of nodes and deletes the duplicates.

Template Parameters

LISTITERATOR Type of list iterator

Parameters

graph	The corresponding graph
firstList	Iterator of the first list
secondList	Iterator of the second list
mergedList	Reference to the resulting merged list

Definition at line 325 of file NodeColoringModule.h.

◆ preprocessGraph()

virtual void ogdf::NodeColoringModule::preprocessGraph ( Graph & graph ) const

inlinevirtual

Preprocesses a graph so that a coloring algorithm can be applied.

The preprocessing removes self-loop edges and redundant edges.

Parameters

graph The graph to be preprocessed.

Definition at line 107 of file NodeColoringModule.h.

◆ ramseyAlgorithm()

virtual void ogdf::NodeColoringModule::ramseyAlgorithm	(	const Graph &	graph,
		List< node > &	clique,
		List< node > &	independentSet
	)		const

protectedvirtual

Performs the Ramsey algorithm for finding heuristically large cliques and independents sets in a graph.

Parameters

graph	The input graph
clique	List with the resulting clique
independentSet	List with the resulting independent set

◆ reverseNodeTable()

virtual void ogdf::NodeColoringModule::reverseNodeTable	(	const Graph &	graphOrig,
		const Graph &	graphNew,
		const NodeArray< node > &	orig2New,
		NodeArray< node > &	new2Orig
	)		const

protectedvirtual

Reverses the mapping between the nodes sets of a graph and a subgraph.

Parameters

graphOrig	The original graph
graphNew	The new (sub-)graph
orig2New	Existing node table from the original graph to the new graph
new2Orig	Resulting node table from the new graph to the original graph

◆ searchBinary()

int ogdf::NodeColoringModule::searchBinary	(	SearchWrapper *	searchWrapper,
		int	start,
		int	end
	)		const

protected

Performs a binary search in a specified range with a given oracle.

The oracle tells if the current value is valid.

Parameters

searchWrapper	The oracle
start	Start interval of the range
end	End interval of the range

Returns: The smallest valid parameter determined

◆ searchLinear()

int ogdf::NodeColoringModule::searchLinear	(	SearchWrapper *	searchWrapper,
		int	start,
		int	end
	)		const

protected

Performs a linear search in a specified range with a given oracle.

The oracle tells if the current value is valid.

Parameters

searchWrapper	The oracle
start	Start interval of the range
end	End interval of the range

Returns: The smallest valid parameter determined

◆ searchWigderson()

int ogdf::NodeColoringModule::searchWigderson ( SearchWrapper * searchWrapper ) const

protected

Performs a the search procedure specified by Wigderson.

The oracle tells if the current value is valid.

Parameters

searchWrapper The oracle

Returns: The smallest valid parameter determined

Member Data Documentation

◆ m_ramseyProcedure

RamseyProcedure ogdf::NodeColoringModule::m_ramseyProcedure

protected

The RamseyProcedure to be used to select nodes.

Definition at line 111 of file NodeColoringModule.h.

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

include/ogdf/graphalg/NodeColoringModule.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ NodeColor

Member Enumeration Documentation

◆ RamseyProcedure

◆ SearchProcedure

Constructor & Destructor Documentation

◆ NodeColoringModule()

◆ ~NodeColoringModule()

Member Function Documentation

◆ call()

◆ checkColoring()

◆ checkIndependentSet()

◆ cliqueRemoval()

◆ createBuckets()

◆ getMaximumDegreeNode()

◆ getMaximumDegreeNodes()

◆ getMaximumNodeColor()

◆ getMinimumDegreeNode()

◆ getMinimumDegreeNodes()

◆ getNeighborDegrees()

◆ getNeighbors()

◆ getNeighborsComplement()

◆ mergeNodeLists()

◆ preprocessGraph()

◆ ramseyAlgorithm()

◆ reverseNodeTable()

◆ searchBinary()

◆ searchLinear()

◆ searchWigderson()

Member Data Documentation

◆ m_ramseyProcedure

Open
Graph Drawing
Framework