Approximation algorithms for the node coloring problem in graphs. More...
#include <ogdf/graphalg/NodeColoringWigderson.h>
Classes | |
struct | SearchWrapperWigderson |
Wraps the Wigderson recursive algorithm. 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 > °reesOriginal, List< node > &nodesToBeColored) |
Calls the recursive algorithm of Wigderson to find a feasible graph coloring. More... | |
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... | |
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.
|
strong |
Declares the procedure dealing with the brute force coloring.
Definition at line 75 of file NodeColoringWigderson.h.
|
strong |
Declares procedure to find the maximum degree nodes.
Definition at line 52 of file NodeColoringWigderson.h.
Declares the procedure dealing with the recursion anchor coloring.
Definition at line 65 of file NodeColoringWigderson.h.
|
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.
|
overridevirtual |
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. |
Implements ogdf::NodeColoringModule.
|
inline |
Sets the brute force procedure.
bruteForceProcedure | The desired brute force coloring procedure |
Definition at line 123 of file NodeColoringWigderson.h.
|
inline |
Sets the procedure of finding maximum degree nodes.
maxDegreeProcedure | The desired maximum degree finding procedure |
Definition at line 107 of file NodeColoringWigderson.h.
|
inline |
Sets the recursion anchor procedure.
recursionAnchorProcedure | The desired recursion anchor coloring procedure |
Definition at line 115 of file NodeColoringWigderson.h.
|
inline |
Sets the search procedure to find the smallest possible parameter k such as the graph is k-colorable.
searchProcedure | The desired search procedure |
Definition at line 99 of file NodeColoringWigderson.h.
|
private |
Calls initially the recursive algorithm of Wigderson.
The result is a certain graph coloring.
graph | The input graph to be colored. |
colors | The resulting coloring. |
color | The start color. |
k | The parameter k such that the graph is k-colorable. |
|
inlineprivate |
Calculates the function for the graph maximum degree specified by Wigderson.
n | Number of nodes. |
k | Parameter, such that the graph is k-colorable. |
Definition at line 146 of file NodeColoringWigderson.h.
|
private |
Calls the recursive algorithm of Wigderson to find a feasible graph coloring.
graph | The input graph to be colored. |
colors | The resulting coloring. |
color | The start color. |
k | The parameter k such that the graph is k-colorable. |
degreesOriginal | The node degrees in the initial original graph. |
nodesToBeColored | Resulting list of nodes which need to be colored. |
|
private |
Definition at line 136 of file NodeColoringWigderson.h.
|
private |
Definition at line 131 of file NodeColoringWigderson.h.
|
private |
Definition at line 134 of file NodeColoringWigderson.h.
|
private |
Definition at line 135 of file NodeColoringWigderson.h.
|
private |
Definition at line 133 of file NodeColoringWigderson.h.
|
private |
Definition at line 132 of file NodeColoringWigderson.h.