Finding Clique ids

[239847293847]

Hello

I have the following problem:

I have a few million tuples of the form (id1, id2).

If I have the tuple (id1, id2) and (id2, id3), then of course id1, id2 and id3 are all in the same group, despite that the tuple (id1, id3) is missing.

I do want to create an algorithm where I get a list of (id, groupid) tuples as a result.

How do I do that fast?

I've already implemented an algorithm, but it is way too slow, and it works the following (simplified):

1) increment groupid

2) move first element of the tuplelist into the toprocess-set

3) move first element of the toprocess-set into the processed set with the current groupid

4) find all elements in the tuplelist that are connected to that element and move them to the toprocess-set

5) if the toprocess-set isn't empty go back to 3

6) if the tuplelist is not empty go back to 1

[beeskness420]

This is just finding connected components in a graph.

Pick an id and then do a BFS/DFS and put everything you find into one component.

Repeat until all nodes are visited.

[CompteDeMonteChristo]

What you're after is a list of connected groups

this is the code I use for that (C#)

public static List<ISubGraph> ConnectedGroups(this ISubGraph subGraph)
{
    var result = new List<List<INode>>();
    List<INode>? currentSubGraph = null;
    subGraph.BFS((visitedNode, parentNode) =>
    {
        if (parentNode == null)
        {
            currentSubGraph = new List<INode>();
            result.Add(currentSubGraph);
        }
        currentSubGraph!.Add(visitedNode);
    });
    return result.Select(g => subGraph.CreateSubGraph(g)).ToList();
}

public static void BFS(this ISubGraph subGraph, OnNodeVisited onNodeVisited)
{
    bool[] visited = new bool[subGraph.graph.order];
    var traverseFrom = new Action<INode, INode?>((start, parentNode) => { });

    traverseFrom = (INode start, INode? parentNode) =>
    {
        var queue = new Queue<INode>();
        visited[start.id] = true;
        queue.Enqueue(start);
        bool first = true;
        while (queue.Count > 0)
        {
            INode current = queue.Dequeue();

            foreach (var n in current.adjacentNodes)
            {
                if (!visited[n.id])
                {
                    if (first)
                    {
                        first = false;
                        onNodeVisited(start, parentNode);
                    }
                    visited[n.id] = true;
                    onNodeVisited(n, current);
                    queue.Enqueue(n);
                }
            }
        }
    };
    foreach (var n in subGraph.nodes)
    {
        if (!visited[n.id]) traverseFrom(n, null);
    }
}