在长度< = k的有向图中找到所有循环 [英] Finding all cycles in directed graphs of length <= k

问题描述

是否可以在

Finding all cycles in undirected graphs

将边视为有向边，并且仅将长度为< = k的循环视为？

to consider edges as directed and only cycles of length <= k ?

推荐答案

我自己回答

static void Main(string[] args)
    {
        int k = 4;
        for (int i = 0; i < graph.GetLength(0); i++)
            for (int j = 0; j < graph.GetLength(1); j++)
            {
                findNewCycles(new int[] { graph[i, j] },k);
            }

        foreach (int[] cy in cycles)
        {
            string s = "" + cy[0];

            for (int i = 1; i < cy.Length; i++)
                s += "," + cy[i];

            Console.WriteLine(s);
        }
    }

    static void findNewCycles(int[] path, int k)
    {
        int n = path[0];
        int x;
        int[] sub = new int[path.Length + 1];

        if (path.Length < k + 1)
        {

            for (int i = 0; i < graph.GetLength(0); i++)
                for (int y = 0; y <= 1; y = y + 2)
                    if (graph[i, y] == n)
                    //  edge referes to our current node
                    {
                        x = graph[i, (y + 1) % 2];
                        if (!visited(x, path))
                        //  neighbor node not on path yet
                        {
                            sub[0] = x;
                            Array.Copy(path, 0, sub, 1, path.Length);
                            //  explore extended path
                            findNewCycles(sub,k);
                        }
                        else if ((path.Length > 2) && (x == path[path.Length - 1]))
                        //  cycle found
                        {
                            int[] p = normalize(path);
                            int[] inv = invert(p);
                            if (isNew(p) && isNew(inv))
                                cycles.Add(p);
                        }
                    }
        }


    }

    static bool equals(int[] a, int[] b)
    {
        bool ret = (a[0] == b[0]) && (a.Length == b.Length);

        for (int i = 1; ret && (i < a.Length); i++)
            if (a[i] != b[i])
            {
                ret = false;
            }

        return ret;
    }

    static int[] invert(int[] path)
    {
        int[] p = new int[path.Length];

        for (int i = 0; i < path.Length; i++)
            p[i] = path[path.Length - 1 - i];

        return normalize(p);
    }

    //  rotate cycle path such that it begins with the smallest node
    static int[] normalize(int[] path)
    {
        int[] p = new int[path.Length];
        int x = smallest(path);
        int n;

        Array.Copy(path, 0, p, 0, path.Length);

        while (p[0] != x)
        {
            n = p[0];
            Array.Copy(p, 1, p, 0, p.Length - 1);
            p[p.Length - 1] = n;
        }

        return p;
    }

    static bool isNew(int[] path)
    {
        bool ret = true;

        foreach (int[] p in cycles)
            if (equals(p, path))
            {
                ret = false;
                break;
            }

        return ret;
    }

    static int smallest(int[] path)
    {
        int min = path[0];

        foreach (int p in path)
            if (p < min)
                min = p;

        return min;
    }

    static bool visited(int n, int[] path)
    {
        bool ret = false;

        foreach (int p in path)
            if (p == n)
            {
                ret = true;
                break;
            }

        return ret;
    }
}

这篇关于在长度&lt; = k的有向图中找到所有循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！