8
\$\begingroup\$

I've been looking for an implementation of Tarjan's algorithm in C#/C++ for a strongly-connected components in graphs, and couldn't find any implementation without use of additional Stack - most of them just follow wikipedia pseudocode. I've decided to create one in case if someone is looking for it. Please take a look and codereview. The main point is that mark the SCC as completed once I'm done with descendand processing, and that any cross-edge towards completed SCC will be ignored.

using System;
using System.Collections.Generic;
using System.Linq;

public class Graph
{
    private int _verticesCount;
    private List<int>[] _vertexAdjancedVertices; // i-th element contains info about all adjanced vertices of vertex #i

    public Graph(int[,] edges)
    {
        _verticesCount = edges.Cast<int>().Max() + 1;
        _vertexAdjancedVertices = new List<int>[_verticesCount];
        for (int i = 0; i < _verticesCount; ++i)
            _vertexAdjancedVertices[i] = new List<int>();

        for(int i = 0; i < edges.GetLength(0); ++i)
            AddDirectedEdge(edges[i, 0], edges[i, 1]);
    }

    public void AddEdge(int vertex1, int vertex2, bool directed = false)
    {
        AddDirectedEdge(vertex1, vertex2);
        if (!directed)
            AddDirectedEdge(vertex2, vertex1);
    }

    public void AddDirectedEdge(int vertex1, int vertex2)
    {
        _vertexAdjancedVertices[vertex1].Add(vertex2);
    }

    public List<List<int>> GetStronglyConnectedComponents()
    {
        //DFS
        var processed = new bool[_verticesCount];
        var minConnectedValue = new int[_verticesCount];
        var sccCompleted = new bool[_verticesCount];
        int currentTime = 0;

        for(int startingVertex = 0; startingVertex < _verticesCount; ++startingVertex)
            if (!processed[startingVertex])
                GetStronglyConnectedComponents(startingVertex, ref currentTime, processed, minConnectedValue, sccCompleted);

        var res = minConnectedValue.Select((mcv, i) => new {Vertex = i, MinConnectedValue = mcv})
            .GroupBy(vmcv => vmcv.MinConnectedValue)
            .Select(g => g.Select(vmcv => vmcv.Vertex).ToList()).ToList();
        return res;
    }

    private void GetStronglyConnectedComponents(int vertex, ref int currentTime, bool[] processed, int[] minConnectedValue, bool[] sccCompleted)
    {
        processed[vertex] = true;
        ++currentTime;
        //var currentDiscoveryTime = currentTime;
        minConnectedValue[vertex] = currentTime; // initialize to current time
        sccCompleted[vertex] = false;
        foreach (var neighbour in _vertexAdjancedVertices[vertex])
        {
            if (!processed[neighbour])
            {
                GetStronglyConnectedComponents(neighbour, ref currentTime, processed, minConnectedValue, sccCompleted);
                minConnectedValue[vertex] = Math.Min(minConnectedValue[vertex], minConnectedValue[neighbour]); // if we will ever find cycle
            }
            else if (!sccCompleted[minConnectedValue[neighbour]]) // ignore references to completed sccs
            {
                minConnectedValue[vertex] = Math.Min(minConnectedValue[vertex], minConnectedValue[neighbour]); // we've reached processed vertex - use it as a minConnectedValue we could reach to (if smaller)
            }
        }
        if (minConnectedValue[vertex] == vertex) // we are going up to the stack, meaning that we are done with all the descendands
            sccCompleted[vertex] = true; // mark as completed in case if we are the root of current scc
    }
};

Usage:

    var g = new Graph(new[,] {
        {1, 2}, {2, 3}, {2, 4}, {2, 5}, {3, 1}, {4, 1}, {4, 6}, {4, 8}, {5, 6}, {6, 7}, {7, 5}, {8, 6}
    });

    var sccs = g.GetStronglyConnectedComponents();

    Console.WriteLine("g1");
    foreach (var scc in sccs)
        Console.WriteLine(String.Join(",",scc)); // print out
\$\endgroup\$
  • \$\begingroup\$ It appears, upon my admittedly hasty reading of this code, that you've merely replaced an external stack with three external arrays. Is that an accurate observation? If so, I'm confused as to why three arrays would be more-desirable than one stack. Could you elaborate on that at all? \$\endgroup\$ – Travis Snoozy Apr 22 '14 at 20:42
  • 1
    \$\begingroup\$ So -- I implemented the algorithm with a stack, as per the wikipedia pseudocode, and the result does not match the result your implementation returns. Have you actually verified, against another known-working implementation, that your implementation is generating correct results? \$\endgroup\$ – Travis Snoozy Apr 22 '14 at 21:46
  • \$\begingroup\$ The code works on sample data I tried, could you share yours? The wikipedia keeps the same amount of data: minConnectedValue as .lowLink field, processed as .index field (they use 'undefined') and the only field I introduced is 'completed'. I'm using two bools plus one int per field, wikipedia: two ints per field. The main difference is in the wikipedia there is a call "w is in S" which is Stack.Contains, which has linear time. I.e. the direct implementation in the example is O(n*n), in the notes they suggest using additional flag to workaround that. \$\endgroup\$ – Mikl X Apr 22 '14 at 22:00
  • \$\begingroup\$ The output discrepancy I mentioned above was in my code; sorry for any concern I caused there. Your answer matches that given by another implementation. I'm going to be spending some quality time with your "going up the stack" code, though... I'm very suspicious it will work the same as the stack-based code in all cases. That's why I'm curious as to how thoroughly you have/haven't verified it against existing implementations. :) \$\endgroup\$ – Travis Snoozy Apr 22 '14 at 22:44
  • 1
    \$\begingroup\$ Your implementation appears to be sensitive to the order the edges are given in. If you use {4, 8}, {1, 2}, {8, 6}, {2, 5}, {3, 1}, {7, 5}, {4, 1}, {2, 4}, {4, 6}, {5, 6}, {6, 7}, {2, 3} instead of your original ordering, it results in a different answer. Neither stack-based implementation is sensitive to edge ordering. I'm not sure if this qualifies the code as "broken" or not, but if you know exactly how to characterize the edge ordering requirements of the input, I'd suggest updating your question with that information. \$\endgroup\$ – Travis Snoozy Apr 22 '14 at 23:09
5
\$\begingroup\$

Brace Usage

It is generally considered best practice to always use braces with control statements (such as "if" and "for" statements). If you are concerned with whitespace, consider that placing the opening brace on the same line as the control statement means that the total increase in code size is only 1 line (for the closing brace). It has the added benefit of causing the compiler to complain if you later delete the statement, without deleting the entire block of code attached to it.

Preincrement vs. Postincrement

While both preincrement (++i) and postincrement (i++) do the same thing in isolation, I generally prefer to read the latter. The latter also happens to behave the way most people expect when refactoring the code (render the value, then increment), whereas the former tends to be a very special case (increment first, then render the value) which can cause errors and confusion during refactoring and maintenance. As such, I would recommend using preincrement operators only in the rare occasions they are actually needed (they're a flag that you need to slow down and read that chunk of code carefully).

Algorithm Behavior

The algorithm's output varies based on the order that the edges are presented to the class. Either the class needs to ensure that its internal edge lists are always in the appropriate order assumed/required by the algorithm, or the algorithm needs to be modified to handle edges in an arbitrary order (which the stack-based algorithm does).

The original question's test vector results in:

0
1,2,3,4
5,6,7
8

Whereas reordering the edges to be:

{4, 8}, {1, 2}, {8, 6}, {2, 5}, {3, 1}, {7, 5}, {4, 1}, {2, 4}, {4, 6}, {5, 6}, {6, 7}, {2, 3}

Results in an output of:

0
1,2,3,4
5,6,7,8

There may be additional deficiencies/broken cases surrounding this particular implementation. I ceased investigation upon finding this problem, but I would strongly suggest extensive verification against a known-working stack-based implementation after taking any corrective actions on your stackless algorithm.

Container Types

As a general rule of thumb, when returning a container, you should return the most-generic container interface type appropriate. It is almost never appropriate to return a concrete container, such as a List<T> or Dictionary<T>. In the case of public List<List<int>> GetStronglyConnectedComponents(), it should probably return ICollection<ICollection<int>> (since knowing how many groups and how many vertices are in each group makes sense enough to not use IEnumerable<T>, but all of the IList<T> functionality seems overkill).

Comments

Comments are far easier to read when they are above the line they are commenting, rather than to the right. Comments on the right of lines tend to contribute to overly-long lines, they tend to not be well-aligned (and come out of alignment upon refactoring), and tend to get lost/pushed off the side of the screen. All of this makes it much more difficult to do a comments-only skim of the code to get the gist of what it's supposed to be doing, prior to analyzing the code proper, or when quickly trying to find the part of the code you need to modify. The only benefit of comments on the right is that they take up less horizontal space -- but the hit to readability, and therefore usefulness, makes this placement unacceptable to me in most cases.

Some of the comments could also use improvement. "If we will ever find cycle" is confusing; it's either an incomplete thought, or placed on the wrong line. "Initialize to current time" is self-evident; it would be more useful to know why initializing to the current time is important (and possibly comment what currentTime is/does). "DFS" I assume means "depth-first search," and if so, should go into the recursive GetStronglyConnectedComponents call (right before the if statement that kicks off the actual depth-first searching), not the root call.

The "var currentDiscoveryTime[...]" comment is also dead code, and should be removed.

Structures

It would be nice from an aesthetic standpoint to, e.g., pass around a single array of a structure containing your working data, rather than three same-sized arrays.

Speed

If you're simply aiming to get to an \$O(1)\$ sidestep of the stack lookup, consider the easier alternative of keeping a secondary data structure (such as your List<bool>) that you can modify to mirror the stack, allowing you \$O(1)\$ insertion and lookup in \$2N\$ space. This would eliminate your need to get clever with edge orderings (which will take time to sort) or subtle algorithm alterations (translating the stack to effectively an array), while getting you the speedup you want. It's not as cool or elegant as the algorithmic gymnastics of doing away with the stack altogether, but it's much more likely to be maintainable, fast, and correct in the future. ;)

\$\endgroup\$
  • \$\begingroup\$ Derp. I just noticed that the Wikipedia article even indicates in its Remarks section that "The test for whether w is on the stack should be done in constant time, for example, by testing a flag stored on each node that indicates whether it is on the stack." My suggestion in the "Speed" section, therefore, isn't any different from your provided source material. :) \$\endgroup\$ – Travis Snoozy Apr 23 '14 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.