Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::NodeColoringWigderson Class Reference

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  BruteForceProcedure { BruteForceProcedure::sequentialColoringSimple, BruteForceProcedure::sequentialColoringDegree, BruteForceProcedure::pooled }
 Declares the procedure dealing with the brute force coloring. More...
 
enum  MaxDegreeProcedure { MaxDegreeProcedure::smallestIndex, MaxDegreeProcedure::minDegreeRecursion, MaxDegreeProcedure::maxDegreeRecursion, MaxDegreeProcedure::minDegreeOriginal, MaxDegreeProcedure::maxDegreeOriginal, MaxDegreeProcedure::minDegreeNeighbors, MaxDegreeProcedure::maxDegreeNeighbors }
 Declares procedure to find the maximum degree nodes. More...
 
enum  RecursionAnchorProcedure { RecursionAnchorProcedure::trivialColoring, RecursionAnchorProcedure::sequentialColoringSimple, RecursionAnchorProcedure::sequentialColoringDegree, RecursionAnchorProcedure::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. 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

 NodeColoringWigderson ()
 The constructor. More...
 
virtual NodeColor call (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor start=0) override
 The actual algorithm call. More...
 
void setBruteForceProcedure (BruteForceProcedure bruteForceProcedure)
 Sets the brute force procedure. More...
 
void setMaxDegreeProcedure (MaxDegreeProcedure maxDegreeProcedure)
 Sets the procedure of finding maximum degree nodes. More...
 
void setRecursionAnchorProcedure (RecursionAnchorProcedure recursionAnchorProcedure)
 Sets the recursion anchor procedure. More...
 
void setSearchProcedure (SearchProcedure searchProcedure)
 Sets the search procedure to find the smallest possible parameter k such as the graph is k-colorable. 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...
 

Private Member Functions

bool wigdersonCaller (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor &color, int k)
 Calls initially the recursive algorithm of Wigderson. More...
 
int wigdersonFunction (int n, int k) const
 Calculates the function for the graph maximum degree specified by Wigderson. More...
 
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. More...
 

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. 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 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 47 of file NodeColoringWigderson.h.

Member Enumeration Documentation

◆ BruteForceProcedure

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 75 of file NodeColoringWigderson.h.

◆ MaxDegreeProcedure

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 52 of file NodeColoringWigderson.h.

◆ RecursionAnchorProcedure

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 65 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 86 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
graphThe graph for which the node coloring will be calculated.
colorsThe resulting node coloring.
startThe 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
bruteForceProcedureThe desired brute force coloring procedure

Definition at line 123 of file NodeColoringWigderson.h.

◆ setMaxDegreeProcedure()

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

Sets the procedure of finding maximum degree nodes.

Parameters
maxDegreeProcedureThe desired maximum degree finding procedure

Definition at line 107 of file NodeColoringWigderson.h.

◆ setRecursionAnchorProcedure()

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

Sets the recursion anchor procedure.

Parameters
recursionAnchorProcedureThe desired recursion anchor coloring procedure

Definition at line 115 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
searchProcedureThe desired search procedure

Definition at line 99 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
graphThe input graph to be colored.
colorsThe resulting coloring.
colorThe start color.
kThe 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
nNumber of nodes.
kParameter, such that the graph is k-colorable.
Returns
The function value.

Definition at line 146 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
graphThe input graph to be colored.
colorsThe resulting coloring.
colorThe start color.
kThe parameter k such that the graph is k-colorable.
degreesOriginalThe node degrees in the initial original graph.
nodesToBeColoredResulting 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 136 of file NodeColoringWigderson.h.

◆ m_coloringSimple

NodeColoringSimple ogdf::NodeColoringWigderson::m_coloringSimple
private

Definition at line 131 of file NodeColoringWigderson.h.

◆ m_maxDegreeProcedure

MaxDegreeProcedure ogdf::NodeColoringWigderson::m_maxDegreeProcedure
private

Definition at line 134 of file NodeColoringWigderson.h.

◆ m_recursionAnchorProcedure

RecursionAnchorProcedure ogdf::NodeColoringWigderson::m_recursionAnchorProcedure
private

Definition at line 135 of file NodeColoringWigderson.h.

◆ m_searchProcedure

SearchProcedure ogdf::NodeColoringWigderson::m_searchProcedure
private

Definition at line 133 of file NodeColoringWigderson.h.

◆ m_sequentialColoring

NodeColoringSequential ogdf::NodeColoringWigderson::m_sequentialColoring
private

Definition at line 132 of file NodeColoringWigderson.h.


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