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

#include <ogdf/graphalg/NodeColoringSequential.h>

Inheritance diagram for ogdf::NodeColoringSequential:

Classes
class	NodeDegreeComparer
	Class for comparing two nodes by the node degree. More...

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

virtual NodeColor	colorByDegree (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor start=0)
	Performs the sequential nodes coloring. More...

virtual NodeColor	colorByIndex (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor start=0)
	Performs the sequential nodes coloring. More...

virtual NodeColor	fromPermutation (const Graph &graph, NodeArray< NodeColor > &colors, List< node > &nodePermutation, NodeColor start=0, bool lookForNeighbors=false)
	Colors a graph with the sequential coloring algorithm from a given node permutation. More...

virtual void	sortByDegree (List< node > &nodes)
	Sorts a list of nodes decreasingly by the degree. More...

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

virtual	~NodeColoringModule ()
	Destructor. 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...

Additional Inherited Members
Public Types inherited from ogdf::NodeColoringModule
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...

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. 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 inherited from ogdf::NodeColoringModule
RamseyProcedure	m_ramseyProcedure
	The RamseyProcedure to be used to select nodes. More...

Detailed Description

Approximation algorithms for the node coloring problem in graphs.

This class applies the sequential coloring algorithm which greedily assigns to each node the first available color.

Definition at line 48 of file NodeColoringSequential.h.

Member Function Documentation

◆ call()

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

inlineoverridevirtual

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.

Definition at line 50 of file NodeColoringSequential.h.

◆ colorByDegree()

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

virtual

Performs the sequential nodes coloring.

The nodes are thereby sorted by the smallest index.

Parameters

graph	The graph to be colored
colors	The resulting coloring
start	The starting color index

Returns: The number of colors used

◆ colorByIndex()

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

virtual

Performs the sequential nodes coloring.

The nodes are thereby sorted by the largest degree.

Parameters

graph	The graph to be colored
colors	The resulting coloring
start	The starting color index

Returns: The number of colors used

◆ fromPermutation()

virtual NodeColor ogdf::NodeColoringSequential::fromPermutation	(	const Graph &	graph,
		NodeArray< NodeColor > &	colors,
		List< node > &	nodePermutation,
		NodeColor	start = `0`,
		bool	lookForNeighbors = `false`
	)

virtual

Colors a graph with the sequential coloring algorithm from a given node permutation.

Parameters

graph	The graph to be colored
colors	The resulting coloring
nodePermutation	The given node permutation
start	The starting color index
lookForNeighbors	Iff true, all nodes, including those not contained in the list will be considered

Returns: The number of colors used

◆ sortByDegree()

virtual void ogdf::NodeColoringSequential::sortByDegree ( List< node > & nodes )

virtual

Sorts a list of nodes decreasingly by the degree.

Parameters

nodes List of nodes to be sorted.

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

include/ogdf/graphalg/NodeColoringSequential.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ call()

◆ colorByDegree()

◆ colorByIndex()

◆ fromPermutation()

◆ sortByDegree()

Open
Graph Drawing
Framework