Maximum clique problem: fast heuristic

Question

I have implemented an algorithm which computes a maximum clique via a heuristic. The pseudo-code can be found in this Paper (see Algorithm 2).

Maximum Clique Problem

Given an undirected, simple Graph \$G=(V,E)\$, a clique \$C \subseteq V\$ is a subset of vertices such that all vertices in \$C\$ are connected, i.e. \$\forall v,w \in C : vw \in E\$. A clique \$\hat{C}\$ is maximum if and only if for all cliques \$C': |\hat{C}| \geq |C'|\$.

Problem: Find a maximum clique in \$G\$.

Furthermore, I want the following property to be fulfilled: Let \$C_1, C_2, \dots, C_k\$ be maximum cliques in \$G\$. Find \$ \hat{C} = {arg\,max}_{i=1,\dots,k} \,\, \sum_{v \in C_i} degree(v) \$

I want to compute a maximum clique which with the highest sum of degrees.

Heuristic

Some aliases which are located in a header file.

// boost.hpp
using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using VertexIt = boost::graph_traits<Graph>::vertex_iterator;
using AdjacentIt = boost::graph_traits<Graph>::adjacency_iterator;

The heuristic:

// Clique.cpp
// graph is a class member and is of type Graph
std::vector<Vertex> Coloring::findMaxClique() const noexcept {
    auto maxCliqueSize = 0;
    std::vector<Vertex> maxClique;
    std::vector<Vertex> tmpClique;

    VertexIt vertex, v_end;
    for (tie(vertex, v_end) = boost::vertices(graph); vertex != v_end; ++vertex) {
        if (boost::degree(*vertex, graph) >= maxCliqueSize) {
            tmpClique = findMaxCliqueWithVertex(*vertex, maxCliqueSize);

            if (tmpClique.size() >= 2 && static_cast<int>(tmpClique.size()) > maxCliqueSize) {
                maxClique = std::move(tmpClique);
                maxCliqueSize = static_cast<int>(maxClique.size());
            } else if (tmpClique.size() == maxClique.size()) {
                if (calculateDegreeSum(tmpClique) > calculateDegreeSum(maxClique)) {
                    maxClique = std::move(tmpClique);
                }
            }
        }
    }

    return maxClique;
}

inline int Coloring::calculateDegreeSum(const std::vector<Vertex> &clique) const noexcept {
    return std::accumulate(clique.begin(), clique.end(), 0, [this](int accumulator, const Vertex vertex) {
        return accumulator + boost::degree(vertex, graph);
    });
}

std::vector<Vertex> Coloring::findMaxCliqueWithVertex(const Vertex vertex, const int maxCliqueSize) const noexcept {
    std::vector<Vertex> clique;
    clique.reserve(maxCliqueSize);
    clique.emplace_back(vertex);

    std::vector<Vertex> candidateNeighbors;
    candidateNeighbors.reserve(maxCliqueSize);

    AdjacentIt adjVertex, adjVertEnd;
    for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(vertex, graph); adjVertex != adjVertEnd; ++adjVertex) {
        candidateNeighbors.emplace_back(*adjVertex);
    }

    std::vector<Vertex> tmp;
    tmp.reserve(maxCliqueSize);

    while (!candidateNeighbors.empty()) {
        const auto highestDegNeighborIt = std::max_element(candidateNeighbors.begin(), candidateNeighbors.end(), [this](const Vertex &lhs, const Vertex &rhs) {
            return boost::degree(lhs,graph) < boost::degree(rhs,graph); 
        });

        const auto highestDegVert = *highestDegNeighborIt;
        clique.emplace_back(highestDegVert);

        for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(highestDegVert, graph_); adjVertex != adjVertEnd; ++adjVertex) {
            if (std::find(candidateNeighbors.begin(), candidateNeighbors.end(), *adjVertex) != candidateNeighbors.end()) {
                tmp.emplace_back(*adjVertex);
            }
        }
        candidateNeighbors = std::move(tmp);
    }
    return clique;
}

How it works

1. for every vertex \$v \in V\$: try find a clique which includes \$v\$
   1. add \$v\$ to new clique \$C'\$
   2. consider neighbor-vertices of \$v\$. Let \$N_v := \{w \in V : vw \in E\}\$ be the neighborhood of a vertex \$v\$.
   3. select \$\hat{w} = {arg\,max}_{w\in N_v} degree(w)\$
   4. add \$\hat{w}\$ to \$C'\$
   5. now consider \$M := N_{\hat{w}} \cap N_v\$ and repeat the procedure of finding a vertex in \$M\$ with highest degree like above until no candidate-vertices exist
   6. return \$C'\$
2. if we find a new clique \$C'\$ which has the same size as our current maximum clique \$\Rightarrow\$ compute sum of degrees and save the one which has the higher sum value

Question/Concerns

• I am fairly new to C++ and just started to get to know C++11 features
• Because this algorithm is used several thousands of times for a graph
• I want this procedure to be fast as possible
• readable and clean coding style?
• maxCliqueSize can be removed as using maxClique.size() can be done in constant time (using std::vector<Vertex>)
• Did I use std::move correctly or should I use std::swap instead?
• Is there any way to alleviate the std::find as it is not a \$O(1)\$ operation. I could try to use a std::vector<bool> of length \$|V|\$ which represents candidate vertices when an entry is set to true.

So I would get this algorithm; however I need additional std::move operations and vector-emplacements.

std::vector<Vertex> Coloring::findMaxCliqueWithVertex(const Vertex vertex, const int maxCliqueSize) const noexcept {
    std::vector<Vertex> clique;
    clique.reserve(maxCliqueSize);
    clique.emplace_back(vertex);

    std::vector<Vertex> candidateNeighbors;
    std::vector<bool> candidateNeighborsVec(boost::num_vertices(graph));
    candidateNeighbors.reserve(maxCliqueSize);

    AdjacentIt adjVertex, adjVertEnd;
    for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(vertex, graph); adjVertex != adjVertEnd; ++adjVertex) {
        candidateNeighbors.emplace_back(*adjVertex);
        candidateNeighborsVec[*adjVertex] = true;
    }

    std::vector<Vertex> tmp;
    tmp.reserve(maxCliqueSize);

    while (!candidateNeighbors.empty()) {
        const auto highestDegNeighborIt = std::max_element(candidateNeighbors.begin(), candidateNeighbors.end(), [this](const Vertex &lhs, const Vertex &rhs) { 
            return boost::degree(lhs,graph) < boost::degree(rhs,graph); 
        });

        const auto highestDegVert = *highestDegNeighborIt;
        clique.emplace_back(highestDegVert);

        std::vector<bool> newCandidates(boost::num_vertices(graph));

        for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(highestDegVert, graph); adjVertex != adjVertEnd; ++adjVertex) {
            if (candidageNeighborsVec[*adjVertex])
                tmp.emplace_back(*adjVertex);
                newCandidatesVec[*adjVertex] = true;
            }
        }
        candidateNeighbors = std::move(tmp);
        candidateNeighborsVec = std::move(newCandidatesVec);
     }
    return clique;
}

Answer 1

std::move leaves the container it is used on in an unspecified (but valid) state after it is used on it.

while (!candidateNeighbors.empty()) {
    const auto highestDegNeighborIt = std::max_element(candidateNeighbors.begin(), candidateNeighbors.end(), [this](const Vertex &lhs, const Vertex &rhs) { 
        return boost::degree(lhs,graph) < boost::degree(rhs,graph); 
    });

    const auto highestDegVert = *highestDegNeighborIt;
    clique.emplace_back(highestDegVert);

    std::vector<bool> newCandidates(boost::num_vertices(graph));

    for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(highestDegVert, graph); adjVertex != adjVertEnd; ++adjVertex) {
        if (candidageNeighborsVec[*adjVertex])
            tmp.emplace_back(*adjVertex);
            newCandidatesVec[*adjVertex] = true;
        }
    }
    candidateNeighbors = std::move(tmp);
    candidateNeighborsVec = std::move(newCandidatesVec);
 }

Here std::move is called on the same variable multiple times in the loop. It is unspecified what the state of tmp is after, so calling clear() on it should be done to ensure that it's back to an empty state. Even if it's already the case with the implementation of std::vector used, it's unspecified behavior:

Unless otherwise specified, all standard library objects that have been moved from are placed in a valid but unspecified state. That is, only the functions without preconditions, such as the assignment operator, can be safely used on the object after it was moved from:

Actually, looking at the code, declaring the temporary variables at the beginning of the loop instead of outside of it will avoid you the call to clear() and may even improve performance.

For newCandidatesVec and candidateNeighborsVec, a swap and then newCandidatesVec.clear(); newCandidatesVec.resize(boost::num_vertices(graph)); may be more appropriate. That way the memory is not reallocated and the vector is reset to all false.

Note also that the improvement given by vector::reserve() is minimal (potentially counterproductive if maxCliqueSize is far from being reached). Here is a quote by Bjarne Stroustrup:

People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code). Again: measure before you optimize.

std::vector<bool> is poor in performance when checking and modifiying as it compresses data into bits. However the initialization of all bits to false will be 8 times faster. std::valarray<bool> will use 8 times more memory but will be faster when checking the value of one of its elements.

Although, why not use a std::unordered_set? The std::unordered_set::find function is \$O(1)\$.

    for (tie(adjVertex, adjVertEnd) = boost::adjacent_vertices(highestDegVert, graph_); adjVertex != adjVertEnd; ++adjVertex) {
        if (candidateNeighbors.find(adjVertex) != candidateNeighbors.end()) {
            //Can also use emplace, but emplace is supposed to be used
            // when you don't want to create an element and then feed it
            // to a container. Here the element is already created so the
            // copy constructor should be as efficient
            tmp.insert(adjVertex);
        }
    }

Note: std::unordered_set requires a hashing function to be created for its data type if it doesn't already exist, this simple one would do:

uint hash(Vertex vertex) {
    return hahs(*vertex);
}

Whether using a set or the previous valarray is faster depends on the size of your graph and the average degree of the vertices. By using valarray, one operation per node of the graph (the initialization of the elements of the array to false) is done, but the access and modification of the values after that is very fast.

You also check all the neighbors of the new vertex added to the clique against the current candidate vertices, but wouldn't instead checking all the current candidate vertices are neighbors of the new Vertex be faster? Since that set is bound to be smaller. That is, if checking if two vertices are neighbors is a fast operation on your graph, it probably depends on the data type used for the storage of the edges.

---

Finally, the compiler is very clever and does a lot of optimizations. If you want to improve the speed of the algorithm the first step is avoiding early optimizations and reducing the complexity.

The code will be more readable and more easily manipulable.

Then add the optimizations one by one and check each time performance is improved. As the compiler is clever, sometimes changes won't improve performance and may be even counterproductive. Test, measure, test, measure :(