Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::NodeColoringModule Class Referenceabstract

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

Data type of the node colors.

Definition at line 49 of file NodeColoringModule.h.

Member Enumeration Documentation

◆ RamseyProcedure

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

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

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
graphThe graph corresponding to the given coloring.
colorsThe 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
CONTAINERThe type of container for the node set
Parameters
graphThe graph
nodesThe 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
graphThe given graph
independentSetThe 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
graphThe input graph
sizeThe bucket size
bucketsThe 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
graphThe input graph.
maxDegreeNodeThe 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
graphThe input graph.
maxDegreeNodesList 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
colorsThe 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
graphThe input graph.
minDegreeNodeThe 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
graphThe input graph.
minDegreeNodesList 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
vThe 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
LISTITERATORThe type of iterator for the node set
Parameters
graphThe input graph
nodesThe nodes of whose neighbors will be determined
neighborsThe 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
LISTITERATORThe type of iterator for the node set
Parameters
graphThe input graph
nodesThe nodes of whose complement neighbors will be determined
complementNeighborsThe 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
LISTITERATORType of list iterator
Parameters
graphThe corresponding graph
firstListIterator of the first list
secondListIterator of the second list
mergedListReference 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
graphThe 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
graphThe input graph
cliqueList with the resulting clique
independentSetList 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
graphOrigThe original graph
graphNewThe new (sub-)graph
orig2NewExisting node table from the original graph to the new graph
new2OrigResulting 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
searchWrapperThe oracle
startStart interval of the range
endEnd 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
searchWrapperThe oracle
startStart interval of the range
endEnd 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
searchWrapperThe 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: