Removing equivalent authors in a list

Question

I have a list of authors, where seeking duplicity. The indexes of these duplicates are stored in a list of lists named duplicity. For example, at index 0 in the list duplicity is nested list, which refer to indexes of authors list with duplicates author A, index 1 author duplicity B, etc. I also have list edge, where indexes of nodes(authors) are stored that are connected by an edge. Program passes through and removes duplicate authors by list duplicity.

For example I have stored in duplicity list indexes 1, 2, 3. These refers to authors list, where are stored names of authors. It also refers to edge list, where are stored start and end point of edges. For example if I have authors stored on indexes 1,2,3 and they are connected altogether, than the edge list is 1,2, 1,3, 2,3. Because authors on indexes 1,2,3 are same, I need make them one. So I pass edge list and replace all 2 and 3 to 1.

The problem is that progress of code below is very slow. I'm sure that in the code is something useless which raise complexity, but I can not figure it out. I think, the main failure in my code is the first part with the for loops. It many times passes authors list and if there are tens of thousands items, it's really slow. Can you help me optimize this code?

 for (int i = 0; i < authors.GetDuplicates().Count; i++)
        {
            for (int j = 0; j < edge.Count; j++)
            {
                for (int k = 0; k < authors.GetDuplicates()[i].Count - 1; k++)
                {
                    if (edge[j] == authors.GetDuplicates()[i].ElementAt(k))
                    {
                        edge[j] = authors.GetDuplicates()[i].ElementAt(k + 1);
                    }
                }
            }
        }

 public static List<List<int>> GetDuplicates(this IList<string> source)
    {
        HashSet<string> itemsSeen = new HashSet<string>();
        HashSet<string> itemsYielded = new HashSet<string>();
        List<List<int>> duplicates = new List<List<int>>();
        List<int> dupLow = new List<int>();
        HashSet<int> temp = new HashSet<int>();

        int c = 0;

        foreach (string item in source)
        {
            if (!itemsSeen.Add(item))
            {
                if (itemsYielded.Add(item))
                {
                    if (item != "-")
                    {
                        int w = 0;

                        for (int j = 0; j < authors.Count; j++)
                        {
                            if (authors[j] == authors[c])
                            {
                                temp.Add(w);
                            }
                            w++;
                        }

                        dupLow = new List<int>(temp);
                        duplicates.Add(dupLow);
                        temp.Clear();
                    }
                }
            }
            c++;
        }
        return duplicates;
    }

EDIT:
We have four authors, A and B are authors of one book and C and A are authors of different book. Authors within one book are connected by edge. We can see, there are two authors "A". So we replace in edges index of author A (index 0) to 3. At the end books are connected by common author.

authors | edge | remove dup. | bad result
[0] A    [0] 0   [0] 3    [0] 4
[1] B    [1] 1   [1] 1    [1] 1

[2] C    [2] 2   [2] 2    [2] 2
[3] A    [3] 3   [3] 3    [3] 3


The result should look like this:

Answer 1

I'm not sure I follow the code, but I would try removing the repeated calls to GetDuplicates:

foreach (var duplicate in authors.GetDuplicates())
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < duplicate.Count - 1; k++)
        {
            if (edge[j] == duplicate[k])
            {
                edge[j] = duplicate[k + 1];
            }
        }
    }
}

I've also replaced the calls to ElementAt with use of the indexer, as I think it's clearer.

Answer 2

This little bit of code

        if (!itemsSeen.Add(item))
        {
            if (itemsYielded.Add(item))
            {
                if (item != "-")
                {

can be simplified into

if (!itemsSeen.Add(item) && itemsYielded.Add(item) && item != "-")
{

---

I am not sure I follow exactly how the code works, but I think you could benefit from using List<>'s built in Contains() method. Check it out MSDN List(T).Contains Method

You should be able to get rid of the k for loop by using the Contains() Method

Answer 3

for (int i = 0; i < authors.GetDuplicates().Count; i++)
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < authors.GetDuplicates()[i].Count - 1; k++)
        {
            if (edge[j] == authors.GetDuplicates()[i].ElementAt(k))
            {
                edge[j] = authors.GetDuplicates()[i].ElementAt(k + 1);
            }
        }
    }
}  

What are you doing here ? You are calling GetDuplicates() on almost every line of code.

Assuming authors.GetDuplicates().Count == 3 with each containing list having Count == 2 and edge.Count == 3 you will for the best case call authors.GetDuplicates() 28 times , where one time is enough.

var duplicates = authors.GetDuplicates()
for (int i = 0; i < duplicates.Count; i++)
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < duplicates[i].Count - 1; k++)
        {
            if (edge[j] == duplicates[i].ElementAt(k))
            {
                edge[j] = duplicates[i].ElementAt(k + 1);
            }
        }
    }
}