Cycle finding algorithm

Question

I need do find a cycle beginning and ending at given point. It is not guaranteed that it exists. I use bool[,] points to indicate which point can be in cycle. Poins can be only on grid. points indicates if given point on grid can be in cycle. I need to find this cycle using as minimum number of points. One point can be used only once. Connection can be only vertical or horizontal.

Let this be our points (red is starting point):

removing dead ImageShack links

I realized that I can do this:

while(numberOfPointsChanged)
{
    //remove points that are alone in row or column
}

So i have:

removing dead ImageShack links

Now, I can find the path.

removing dead ImageShack links

But what if there are points that are not deleted by this loop but should not be in path?

I have written code:

class MyPoint
{
    public int X { get; set; }
    public int Y { get; set; }
    public List<MyPoint> Neighbours = new List<MyPoint>();
    public MyPoint parent = null;
    public bool marked = false;
}

    private static MyPoint LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart)
    {
        List<MyPoint> points = new List<MyPoint>();

        //here begins translation bool[,] to list of points
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }
        //end of translating

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]); //beginning point
        start.marked = true; //it is marked
        MyPoint last=null;   //last point. this will be returned
        queue.Add(points[0]);


        while(queue.Count>0)
        {
            MyPoint current = queue.First(); //taking point from queue
            queue.Remove(current);           //removing it

            foreach(MyPoint neighbour in current.Neighbours) //checking Neighbours
            {
                if (!neighbour.marked) //in neighbour isn't marked adding it to queue
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                //if neighbour is marked checking if it is startig point and if neighbour's parent is current point. if it is not that means that loop already got here so we start searching parents to got to starting point
                else if(!neighbour.Equals(start) && !neighbour.parent.Equals(current))
                {                        
                    current = neighbour;
                    while(true)
                    {
                        if (current.parent.Equals(start))
                        {
                            last = current;
                            break;
                        }
                        else
                            current = current.parent;

                    }
                    break;
                }
            }
        }

        return last;            
    }

But it doesn't work. The path it founds contains two points: start and it's first neighbour.
What am I doing wrong?

EDIT: Forgot to mention... After horizontal connection there has to be vertical, horizontal, vertical and so on... What is more in each row and column there need to be max two points (two or none) that are in the cycle. But this condition is the same as "The cycle has to be the shortest one".

Answer 1

That is what I have done. I don't know if it is optimised but it does work correctly. I have not done the sorting of the points as @marcog suggested.

private static bool LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart, out List<MyPoint> path)
    {
        List<MyPoint> points = new List<MyPoint>();
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]);
        start.marked = true;
        queue.Add(points[0]);

        path = new List<MyPoint>();

        bool found = false;

        while(queue.Count>0)
        {
            MyPoint current = queue.First();
            queue.Remove(current);

            foreach (MyPoint neighbour in current.Neighbours)
            {
                if (!neighbour.marked)
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                else
                {
                    if (neighbour.parent != null && neighbour.parent.Equals(current))
                        continue;

                    if (current.parent == null)
                        continue;

                    bool previousConnectionHorizontal = current.parent.Y == current.Y;
                    bool currentConnectionHorizontal = current.Y == neighbour.Y;

                    if (previousConnectionHorizontal != currentConnectionHorizontal)
                    {
                        MyPoint prev = current;

                        while (true)
                        {
                            path.Add(prev);
                            if (prev.Equals(start))
                                break;
                            prev = prev.parent;
                        }

                        path.Reverse();

                        prev = neighbour;

                        while (true)
                        {
                            if (prev.Equals(start))
                                break;
                            path.Add(prev);                                
                            prev = prev.parent;
                        }

                        found = true;
                        break;
                    }                      
                }
                if (found) break;
            }
            if (found) break;
        }

        if (path.Count == 0)
        {
            path = null;
            return false;
        }
        return true;   
    }   

Answer 2

First of all, you should change your representation to a more efficient one. You should make vertex a structure/class, which keeps the list of the connected vertices.

Having changed the representation, you can easily find the shortest cycle using breadth-first search.

You can speed the search up with the following trick: traverse the graph in the breadth-first order, marking the traversed vertices (and storing the "parent vertex" number on the way to the root at each vertex). AS soon as you find an already marked vertex, the search is finished. You can find the two paths from the found vertex to the root by walking back by the stored "parent" vertices.

---

Edit:
Are you sure you code is right? I tried the following:

while (queue.Count > 0)
{
    MyPoint current = queue.First(); //taking point from queue
    queue.Remove(current);           //removing it

    foreach (MyPoint neighbour in current.Neighbours) //checking Neighbours
    {
        if (!neighbour.marked) //if neighbour isn't marked adding it to queue
        {
            neighbour.marked = true;
            neighbour.parent = current;
            queue.Add(neighbour);
        }
        else if (!neighbour.Equals(current.parent)) // not considering own parent
        {
            // found!
            List<MyPoint> loop = new List<MyPoint>();
            MyPoint p = current;
            do
            {
                loop.Add(p);
                p = p.parent;
            }
            while (p != null);
            p = neighbour;
            while (!p.Equals(start))
            {
                loop.Add(p);
                p = p.parent;
            }
            return loop;
        }
    }
}

return null;

instead of the corresponding part in your code (I changed the return type to List<MyPoint>, too). It works and correctly finds a smaller loop, consisting of 3 points: the red point, the point directly above and the point directly below.

Answer 3

Your points removal step is worst case O(N^3) if implemented poorly, with the worst case being stripping a single point in each iteration. And since it doesn't always save you that much computation in the cycle detection, I'd avoid doing it as it also adds an extra layer of complexity to the solution.

Begin by creating an adjacency list from the set of points. You can do this efficiently in O(NlogN) if you sort the points by X and Y (separately) and iterate through the points in order of X and Y. Then to find the shortest cycle length (determined by number of points), start a BFS from each point by initially throwing all points on the queue. As you traverse an edge, store the source of the path along with the current point. Then you will know when the BFS returns to the source, in which case we've found a cycle. If you end up with an empty queue before finding a cycle, then none exists. Be careful not to track back immediately to the previous point or you will end up with a defunct cycle formed by two points. You might also want to avoid, for example, a cycle formed by the points (0, 0), (0, 2) and (0, 1) as this forms a straight line.

The BFS potentially has a worst case of being exponential, but I believe such a case can either be proven to not exist or be extremely rare as the denser the graph the quicker you'll find a cycle while the sparser the graph the smaller your queue will be. On average it is more likely to be closer to the same runtime as the adjacency list construction, or in the worst realistic cases O(N^2).

Answer 4

I think that I'd use an adapted variant of Dijkstra's algorithm which stops and returns the cycle whenever it arrives to any node for the second time. If this never happens, you don't have a cycle.

This approach should be much more efficient than a breadth-first or depth-first search, especially if you have many nodes. It is guarateed that you'll only visit each node once, thereby you have a linear runtime.