Approximation algorithms for the node coloring problem in graphs. More...
#include <ogdf/graphalg/NodeColoringModule.h>
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... | |
Approximation algorithms for the node coloring problem in graphs.
This is the base class.
Definition at line 44 of file NodeColoringModule.h.
using ogdf::NodeColoringModule::NodeColor = unsigned int |
Data type of the node colors.
Definition at line 49 of file NodeColoringModule.h.
|
strong |
Declares the procedure of finding nodes in Ramsey's algorithm.
Definition at line 64 of file NodeColoringModule.h.
|
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.
|
inline |
Default constructor.
Initializes the Ramsey-procedure with the smallest index procedure.
Definition at line 75 of file NodeColoringModule.h.
|
inlinevirtual |
Destructor.
Definition at line 90 of file NodeColoringModule.h.
|
pure virtual |
The actual algorithm call.
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. |
Implemented in ogdf::NodeColoringWigderson, ogdf::NodeColoringBergerRompel, ogdf::NodeColoringJohnson, ogdf::NodeColoringBoppanaHalldorsson, ogdf::NodeColoringHalldorsson, ogdf::NodeColoringRecursiveLargestFirst, ogdf::NodeColoringSequential, and ogdf::NodeColoringSimple.
|
virtual |
Checks if the given node coloring is valid.
graph | The graph corresponding to the given coloring. |
colors | The given node coloring. |
|
inlineprotected |
Checks if subgraph induced by the given nodes forms an independent set.
CONTAINER | The type of container for the node set |
graph | The graph |
nodes | The subset of nodes |
Definition at line 212 of file NodeColoringModule.h.
|
protectedvirtual |
Applies the clique removal algorithm for finding a large independent set in a given graph.
graph | The given graph |
independentSet | The resulting independent set |
|
protectedvirtual |
Creates a partitioning of the node set into buckets of a given size.
graph | The input graph |
size | The bucket size |
buckets | The resulting bucket partitioning of the nodes |
|
protectedvirtual |
Searches for a maximum degree node in the graph.
graph | The input graph. |
maxDegreeNode | The resulting maximum degree node. |
|
protectedvirtual |
Searches for all nodes with maximum degree in the graph.
graph | The input graph. |
maxDegreeNodes | List of all nodes with maximum degree. |
|
protectedvirtual |
Calculates the maximum node color index used in a certain node coloring.
colors | The node coloring. |
|
protectedvirtual |
Searches for a minimum degree node in the graph.
graph | The input graph. |
minDegreeNode | The resulting minimum degree node. |
|
protectedvirtual |
Searches for all nodes with minimum degree in the graph.
graph | The input graph. |
minDegreeNodes | List of all nodes with minimum degree. |
|
protected |
Calculates the sum of neighbor nodes degrees for a given node v.
v | The given node |
|
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.
LISTITERATOR | The type of iterator for the node set |
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.
|
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.
LISTITERATOR | The type of iterator for the node set |
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.
|
inlineprotected |
Merges two lists of nodes and deletes the duplicates.
LISTITERATOR | Type of list iterator |
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.
|
inlinevirtual |
Preprocesses a graph so that a coloring algorithm can be applied.
The preprocessing removes self-loop edges and redundant edges.
graph | The graph to be preprocessed. |
Definition at line 107 of file NodeColoringModule.h.
|
protectedvirtual |
Reverses the mapping between the nodes sets of a graph and a subgraph.
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 |
|
protected |
Performs a binary search in a specified range with a given oracle.
The oracle tells if the current value is valid.
searchWrapper | The oracle |
start | Start interval of the range |
end | End interval of the range |
|
protected |
Performs a linear search in a specified range with a given oracle.
The oracle tells if the current value is valid.
searchWrapper | The oracle |
start | Start interval of the range |
end | End interval of the range |
|
protected |
Performs a the search procedure specified by Wigderson.
The oracle tells if the current value is valid.
searchWrapper | The oracle |
|
protected |
The RamseyProcedure to be used to select nodes.
Definition at line 111 of file NodeColoringModule.h.