Returning the size of the largest clique in a graph

Question

This function is to return the size of the largest clique in a graph. When I run this code, I am running out of space at runtime. Also, it is insanely slow, so any speed tips would be appreciated.

int cliqueSize(graph &g, std::vector<VertexID> nodes, std::vector<EdgeID> edges)
{
    std::vector<std::vector<VertexID> > previous_cliques;

    // start with all the singular nodes...
    for (unsigned i = 0; i < nodes.size(); i++)
    {
        std::vector<VertexID> tmp;
        tmp.push_back(nodes[i]);
        previous_cliques.push_back(tmp);
    }

    for (unsigned clique_size = 1; clique_size < nodes.size(); clique_size++)
    {
        std::vector<std::vector<VertexID> > new_cliques;
        // go through all the nodes to try to add to the clique.
        for (unsigned i = 0; i < nodes.size(); i++)
        {
            // try to add node i to clique j.
            for (unsigned j = 0; j < previous_cliques.size(); j++)
            {
                // make sure node j is not already in the clique.
                if (std::find(previous_cliques[j].begin(), previous_cliques[j].end(), nodes[i]) == previous_cliques[j].end()) 
                {
                    std::vector<VertexID> potential_clique(previous_cliques[j]);
                    potential_clique.push_back(nodes[i]);

                    // isClique has no issues, just checks if the given graph is a clique...   
                    if (isClique(g, potential_clique, edges))
                    {
                        new_cliques.push_back(potential_clique);
                    }
                }
            }
        }
        // no new cliques? 
        if (new_cliques.size() == 0) { return clique_size; }
        else { previous_cliques = new_cliques; }
    }
    return nodes.size();
}

Answer 1

• First of all, start passing things by const reference more. You're passing both nodes and edges by value, which will make a copy.
• Instead of looping through the containers by index, you should use iterators.
• Pushing tmp into previous_cliques will make a copy.

The following may be faster:

std::vector<VertexID> tmp(1);
for (...) {
    tmp[0] = nodes[i];
    previous_cliques.push_back(tmp);
}

(If you're worried about scope, just wrap it in braces.)

• Checking for emptiness with size() may be less efficient than with empty(); unlikely in the case of a vector, though (I think size() must be O(1)).
• You're not showing us isClique, so it's hard to comment on that. Make sure you're passing be const reference there. Also consider not copying previous_cliques until you know you want to push it into new_cliques and instead handling nodes[i] as a special case (may be faster, may be slower).
• If you're using C++11, the emplace functions are your friend.

Answer 2

Comments on algorithm

Your current algorithm is O(N^3) This can definitely be turned into O(N^2)

From reading the code you want to build a list of all sub-graphs that exist in your graph.

I think you are doing t wrong and building several of the subsets repeatedly.

There is a simple technique for this.
Think of each node in the graph as represented by a bit in a very large integer where the integer has one bit for every node in the graph. Node 0 is bit 0 and Node 5 is bit 5 etc. Thus the full graph is represented by the integer with all the bits set to one.

Any sub set of the graph is then represented by an integer with some bits off and some bits on. Thus you can generate all the different sub-sets of the graph by looping through all bit patterns in the integer and this can be done simply by starting at 1 and incrementing the integer until all the bits have been set (Each increment represents a new set).

Assuming you have more nodes than will fit into a normal integer you should probably use the boost::dynamic_bitset(If you have 64 or fewer nodes you can use a normal integer (assuming you have 64 bit integer type)).

/*
 * This function adds 1 to the bitset.
 *
 * Since the bitset does not natively support addition we do it manually. 
 * If XOR a bit with 1 leaves it as one then we did not overflow so we can break out
 * otherwise the bit is zero meaning it was previously one which means we have a bit 
 * overflow which must be added 1 to the next bit etc.
 */
void increment(boost::dynamic_bitset<>& bitset)
{
    for(int loop = 0;loop < bitset.count(); ++loop)
    {
        if ((bitset[loop] ^= 0x1) == 0x1)
        {    break;
        }
    }
}

int cliqueSize(graph &g, std::vector<VertexID> const& nodes, std::vector<EdgeID> const& edges)
{
    static boost::dynamic_bitset   empty;
    empty.resize(nodes.size());

    int                       cliquesCount = 0;
    boost::dynamic_bitset<>   set(nodes.size());
    set[0] = 1;

    while(set != empty()) // break when all bits are zero.
    {
        // Build the next potential clique
        // Every bit that is a 1 in set means that that nodes is in the clique.
        std::vector<VertexID>  cliques;
        for(int loop = 0;loop < nodes.size(); ++loop)
        {
            if (set[loop])
            {
                cliques.push_back(nodes[loop]);
            }
        }

        // If this is a clique increment the count.
        if (isClique(g, cliques, edges))
        {
             ++cliquesCount;
        }

        // Increment the set bits by 1 each loop.
        // This effectively iterates through all different bit patterns.
        increment(set)
    }
    return cliquesCount;
}

Comment on code

You should prefer to pass parameters by const reference if you can.

int cliqueSize(graph &g, std::vector<VertexID> const& nodes, std::vector<EdgeID> const& edges)
                                              ^^^^^^^^                          ^^^^^^^^

std::vector<std::vector<VertexID> > previous_cliques;

The following can be simplified a bit:

    std::vector<VertexID> tmp;
    tmp.push_back(nodes[i]);
    previous_cliques.push_back(tmp);

    // Easier to read like this:
    previous_cliques.push_back(std::vector<VertexID>(1, nodes[i]));

    // If you have C++11 (emplace_back uses move semantics to put the object in the vector)
    previous_cliques.emplace_back(std::vector<VertexID>(1, nodes[i]));

Prefer to use pre-increment for loop variables.

for (unsigned clique_size = 1; clique_size < nodes.size(); ++clique_size)
                                                           ^^

Though it makes no difference for POD types. It gets you in the habit of always using the pre-increment version. This will help you out when the type is not an integer type as generally speaking the pre-increment is more efficient. Also if you change the type from integer (to say iterator) it will automatically be the most efficient version.

You are returning the wrong value:

return nodes.size();

// I think you mean:
return new_cliques.size();

Answer 3

Initial conditions

If each element of edges always represents a clique of two elements of nodes, start by returning 0 if nodes is empty else 1 if edges is empty, else begin looping with clique_size = 2 and each element of previous_cliques initialized to each edge's VertexID pair rather than to each node's single VertexID.

Vector flattening

Since each round N produces some variable number of N-ary cliques, it may be faster, though a bit trickier, to build previous_cliques as a flat vector of VertexID where every Nth element represents the start of a new clique.

A variant on this idea would further capitalize on the flatness of the previous_cliques/new_cliques vectors by using a "double buffering" scheme that limited itself to a single pair of VertexID vectors, possibly allowed to grow as needed and retained for the duration of the function. The vectors would take turns in the roles of previous_cliques/new_cliques and each have an explicit elements_used high water index potentially different from its actual initialized size. The high water would get reset when it took on the role of new_cliques and trailing elements from past rounds simply ignored.

All of this is somewhat second-guessing the memory manager and some of the benefits could be achieved more abstractly by packaging it as actual new/deletes with an alternative recycling-savvy Allocator strategy, if that's your idea of time well-spent.

Clique-first iteration

With or without this optimization, if the node loop is nested within the clique loop instead of vice versa, each clique in previous_cliques can get copied once into a temp vector, with its new last element simply assigned into by each candidate VertexID in turn (vs. using push_back). Then the grown vector, if it is a clique, can be copied into new_cliques (flattened or not). This will reap SOME of the benefits of "only copy on success" as suggested in the excellent answer by @Anton while still allowing passing a simple vector (const &) to isClique.

Optimizing for mathematical properties of cliques

Assuming that the clique semantics are independent of the order in which their VertexIDs are added, i.e. there is no useful distinction between clique {B,A} and clique {A,B} or between the results of {A,B} + C and {A,C} + B, culling of equivalent cliques can boost efficiency. An ordering of VertexIDs -- even an arbitrary ordering that's stable for the duration of the function -- can be used to only count "canonical form" cliques that list their elements in order. With that restriction in place, many uninteresting duplicate cases can be eliminated just by skipping in the inner loop any VertextIDs that sort at or before the previous clique's last VertexID.

Another optimization is possible because/assuming N-ary cliques are composed of N overlapping (N-1)-ary cliques. At a minimum, this means that when the total number of N-ary cliques is N or fewer, N can be returned as the largest clique size.

And there may be more, if you can stand it

N-1 of those N overlapping (N-1)-ary cliques will reference each of the VertexIDs in the N-ary clique. So, as a possible trade-off, track the number of times each VertexID was listed in any N-ary clique -- like in a VertexID-keyed map, preferably a sorted one for use in the range-skipping inner loop mentioned above. This allows any VertexID that was listed fewer than N times to be removed from the set of VertexIDs considered for adding in later rounds. Any N-ary clique that contained it would also be not worth building on. Either of these might be especially tricky and/or expensive to track, though.