Is there anyway to reduce algorithm c# complexity

Question

I created this code for the Department of Redundancy Department algorithm , It gets data from file and it checks each set if there is a redondant FD(Functional Dependency ) it works fine but it has a 26 Cyclomatic Complexity is there any way to reduce it even when i tried to refactor the if conditions into methods it didn't work Here you find the Explanation of the algorithm

    public struct node
    {
        public string left;
        public string right;
    }
    public static bool CheckRedondance(List<node> listNodes)
    {
        bool resultat = false;
        for (int i = 0; i < listNodes.Count; i++) //pour parcourir les DF du groupe
        {
            for (int j = i + 1; j < listNodes.Count; j++) //pour parcourir le reste du groupe
            {
                if (listNodes[i].left == listNodes[j].left) // pour trouver la partie gauche egale
                {
                    for (int k = 0; k < listNodes.Count; k++)
                    {
                        if (listNodes[k].left == listNodes[i].right)
                        {
                            Console.WriteLine("en commun : " + listNodes[k].left + "->" + listNodes[k].right + " avec " + listNodes[i].left + "->" + listNodes[i].right);
                            if (listNodes[k].right == listNodes[j].right)
                            {
                                Console.WriteLine("redondance dans " + listNodes[j].left + "->" + listNodes[j].right);
                                resultat = true;
                            }
                        }
                    }
                }
            }
        }
        return resultat;
    }

    public static bool CheckRedondance2(List<node> listNodes)
    {
        bool resultat = false;
        node nouvelleDF;
        nouvelleDF.right = "";
        nouvelleDF.left = "";
        for (int i = 0; i < listNodes.Count; i++)
        {
            for (int j = i + 1; j < listNodes.Count; j++)
            {
                if (listNodes[j].left.Contains(listNodes[i].left))
                {
                    if (listNodes[j].left.Length > 1)
                    {
                        string concatD, concatG;
                        concatG = listNodes[i].left + listNodes[j].left.Substring(1, listNodes[j].left.Length - 1);
                        concatD = listNodes[i].right + listNodes[j].left.Substring(1, listNodes[j].left.Length - 1);
                        if (concatD.Contains(listNodes[j].right))
                        {
                            Console.WriteLine("partie 2 :" + concatG + "->" + concatD);
                            nouvelleDF.right = listNodes[j].right;
                            nouvelleDF.left = concatG;
                            Console.WriteLine("nouvelle df " + nouvelleDF.left + "->" + nouvelleDF.right);

                            // concatD = /*listNodes[i].right;*/ listNodes[i].right + listNodes[j].left.Substring(1, listNodes[j].left.Length-1);
                            int nbIterations = 0; //pour connaitre l'existance de la même DF 
                            for (int k = 0; k < listNodes.Count; k++) //recherche de la nouvelle DF dans la liste et trouver la redondance du resultat 
                            {
                                if ((listNodes[k].right == nouvelleDF.right) && ((listNodes[k].left == nouvelleDF.left)))
                                {
                                    nbIterations = nbIterations + 1;
                                    if (nbIterations == 1)
                                    {
                                        Console.WriteLine("redondance dans " + listNodes[k].left + "->" + listNodes[k].right);
                                        resultat = true;
                                    }
                                }
                            }
                        }

                    }
                }
            }
        }
        return resultat;
    }

    static void Main()
    {
        var lines = File.ReadAllLines(@"C:/input.txt"); //lecture du fichier input
        int i = 0;  //la ligne du fichier
        int nb = 0; //la longueur de chaque groupe (et sera ecrasée à chaque fois) 
        List<node> listNodes = new List<node>(); //les DF de chaque groupe (node est une DF)
        int numEnsemble = 0;
        while (i < lines.Length)
        {
            var line = lines[i];
            if (!line.Contains("->"))
            {
                nb = Int32.Parse(line);
                if (nb != 0)
                {
                    numEnsemble++;
                    Console.WriteLine(" ");
                    Console.WriteLine("Ensemble numero " + numEnsemble);
                    //Console.WriteLine(nb);
                    for (int j = i; j <= i + nb; j++) //new groupe
                    {
                        var groupLine = lines[j];
                        if (groupLine.Contains("->"))
                        {
                            node localNode;  //expl: A->BC
                            string[] parts = groupLine.Split(new string[] { "->" }, StringSplitOptions.None);
                            localNode.left = parts[0].Trim(); //expl:A
                            localNode.right = parts[1].Trim();//expl: BC 
                            Console.WriteLine(localNode.left + "->" + localNode.right);
                            listNodes.Add(localNode);
                        }
                    }
                    if (!CheckRedondance(listNodes)) //premiere Methode expl: A->BD / BD->C / A->C 
                    {
                        if (!CheckRedondance2(listNodes)) //2eme Meth: expl: P->RST / PS->T
                        {
                            Console.WriteLine("Pas de redondance");
                        }
                    }
                    listNodes.Clear();
                    i += nb;
                }
            }
            else
            {
                i++;
            }
        }
        Console.ReadLine();
    }

What does it should do exactly? Do you will send a list of nodes to method to get information if there one of them is a sibling of another ones in list? — VitezslavSimon
– VitezslavSimon, Commented Dec 9, 2018 at 18:46
@VitezslavSimon take a look at this link u will find the algorithm explanation uva.onlinejudge.org/… — AOUADI Slim
– AOUADI Slim, Commented Dec 9, 2018 at 18:48
Is it ok? for (int k = 0; k < listNodes.Count; k++)? Really not for (int k = j+1; k < listNodes.Count; k++) ? — VitezslavSimon
– VitezslavSimon, Commented Dec 9, 2018 at 19:01
It depends what goal do you want to reach. Do you want to try to develop algorithm from theory for its understanding and being curious or you want to highly optimized technological algorithm behind any database technology? — VitezslavSimon
– VitezslavSimon, Commented Dec 9, 2018 at 19:07
Your question is a good one, however you may get more in depth answers if you moved your question to codereview.stackexchange.com That site is centered around questions like this one. — Scott Chamberlain
– Scott Chamberlain, Commented Dec 9, 2018 at 20:43

score 1 · Accepted Answer · 2018-12-09 20:57:30Z

So this can be done way more efficient with look-up datastructures. As far as I can tell you're looking to see if there's atleast 1 set of 3 nodes that matches the demand that node1.left = node2.left && node3.left == node1.right && node3.right == node2.right So you'll build up a lookup structure filling it with data that could create matches and then check if matches are found.

Now this can be optimized further but you could try something like this (with my test data I got the same results as your CheckRedondance but way faster:

public static bool CheckRedondanceEfficient(List<node> listNodes)
{
    var nodeLookup = new Dictionary<string, List<node>>();
    var matchLookup = new Dictionary<string, HashSet<string>>();
    foreach (node node in listNodes)
    {
        if (AddNode(node, nodeLookup, matchLookup))
            return true;
    }
    foreach (node node in listNodes)
    {
        if (matchLookup.TryGetValue(node.left, out HashSet<string> hashLookup) && hashLookup.Contains(node.right))
            return true;
    }
    return false;
}

private static bool AddNode(node node, Dictionary<string, List<node>> nodeLookup, Dictionary<string, HashSet<string>> matchLookup)
{
    if (matchLookup.TryGetValue(node.left, out HashSet<string> hashLookup) && hashLookup.Contains(node.right))
        return true;
    if (nodeLookup.TryGetValue(node.left, out List<node> nodeMatches))
    {
        foreach (node first in nodeMatches)
        {
            AddFirstMatch(first, node, matchLookup);
        }
        nodeMatches.Add(node);
    }
    else
    {
        nodeLookup.Add(node.left, new List<node>()
        {
            node
        });
    }
    return false;
}

private static void AddFirstMatch(node nodeFirst, node nodeSecond, Dictionary<string, HashSet<string>> matchLookup)
{
    HashSet<string> firstMatch;
    if (!matchLookup.TryGetValue(nodeFirst.right, out firstMatch))
    {
        firstMatch = new HashSet<string>();
        matchLookup.Add(nodeFirst.right, firstMatch);
        firstMatch.Add(nodeSecond.right);
    }
    else
        firstMatch.Add(nodeSecond.right);
}

You dont need to check Contains on a HashSet before adding. Thats why Add returns a bool to indicate whether the element was added.

VitezslavSimon · Accepted Answer · 2018-12-09 19:25:36Z

1) Idea, not full solution:

What about to change 1st structure in your file?

public struct node
{
    public List<string> conns;
}

Then you can use something like:

foreach (string element in nodeRight.conns) {
  if (nodeLeft.conns.Contains(element))
  {
     /*...*/
  }
}

Does it is highly important for you if in one node there is connection on left or on right side? If not, it can be usual for you. By this way I think you can save one for there. You only check if value is in list by using only standard functions there.

2) Another idea: I am not sure if it is possible according to task logic, but what about Backtracking algorithm? ( https://en.wikipedia.org/wiki/Backtracking )

You will alter your structures (add bool flag for each one member you have in your formulas) and provide recursion calling and marking by true when its visited or special return with another flag outside method if any member is visited more than once.

With processing another set flags will be reseted to false and again.

Collectives™ on Stack Overflow

Is there anyway to reduce algorithm c# complexity

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related