Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::NodeColoringJohnson Class Reference

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

#include <ogdf/graphalg/NodeColoringJohnson.h>

+ Inheritance diagram for ogdf::NodeColoringJohnson:

Public Types

enum  MinDegreeProcedure { MinDegreeProcedure::smallestIndex, MinDegreeProcedure::minDegreeOriginal, MinDegreeProcedure::maxDegreeOriginal, MinDegreeProcedure::minDegreeSubgraph, MinDegreeProcedure::maxDegreeSubgraph }
 Declares procedure to find the minimum degree nodes. 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

 NodeColoringJohnson ()
 The constructor. More...
 
virtual NodeColor call (const Graph &graph, NodeArray< NodeColor > &colors, NodeColor start=0) override
 The actual algorithm call. More...
 
void setMinDegreeProcedure (MinDegreeProcedure minDegreeProcedure)
 Sets the procedure of finding minimum degree nodes. 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 Attributes

MinDegreeProcedure m_minDegreeProcedure
 

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 Johnson which tries to find heuristically large independent sets one other the other.

Definition at line 43 of file NodeColoringJohnson.h.

Member Enumeration Documentation

◆ MinDegreeProcedure

Declares procedure to find the minimum degree nodes.

Enumerator
smallestIndex 

Use the node with the smallest index.

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.

minDegreeSubgraph 

Use the node which has the smallest degree in the current subgraph.

maxDegreeSubgraph 

Use the node which has the largest degree in the current subgraph.

Definition at line 48 of file NodeColoringJohnson.h.

Constructor & Destructor Documentation

◆ NodeColoringJohnson()

ogdf::NodeColoringJohnson::NodeColoringJohnson ( )
inline

The constructor.

Initializes the procedure of finding minimum degree nodes with the smallest index.

Definition at line 60 of file NodeColoringJohnson.h.

Member Function Documentation

◆ call()

virtual NodeColor ogdf::NodeColoringJohnson::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.

◆ setMinDegreeProcedure()

void ogdf::NodeColoringJohnson::setMinDegreeProcedure ( MinDegreeProcedure  minDegreeProcedure)
inline

Sets the procedure of finding minimum degree nodes.

Parameters
minDegreeProcedureThe desired minimum degree finding procedure

Definition at line 66 of file NodeColoringJohnson.h.

Member Data Documentation

◆ m_minDegreeProcedure

MinDegreeProcedure ogdf::NodeColoringJohnson::m_minDegreeProcedure
private

Definition at line 74 of file NodeColoringJohnson.h.


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