CODEWITHSUNDEEP
pythongraphduplicates
Nightmare
Nightmare

Reputation: 85

Find how many duplicate connections are in a list of edges [python]

Given a list of edges such as, 

edges = [[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [10, 11], [12, 9], [12, 10]]

I need to find how many duplicate connections are in the list.

In this example: the connections occur in the order

dup = 0

1-2

1-2-3

then [2,3] are already connected so we increment dup by 1

1-2-3, 4-5

1-2-3, 4-5-6

then [5,6] are already connected so again we increment dup by 1

1-2-3, 4-5-6, 10-11

1-2-3, 4-5-6, 9-12, 10-11

1-2-3, 4-5-6, 9-10-11-12

return dup = 2

The last step is where my method messes up , because it counts [12,10] as a duplicate, since my current method is to add the numbers into a dictionary and check if both x and y are in the dictionary then i increment dup by 1

But what I really need to do is check if x and y are already connected, and if they are then increment dup by 1

But I am stuck trying to find a way to do this.

Upvotes: 0

Views: 387

Answers (2)

Tagc
Tagc

Reputation: 9076

While researching this problem I came across a package called networkx. Makes this problem really simple, apparently. I love how 90% of programming is just relying on smart people to do all the hard work, because I sure couldn't do it.

import networkx as nx

def find_duplicate_edges(edges):
    graph = nx.Graph()
    for n1, n2 in edges:
        if graph.has_node(n1) and graph.has_node(n2) and nx.has_path(graph, n1, n2):
            yield n1, n2
        else:
            graph.add_edge(n1, n2)

if __name__ == '__main__':
    edges = [[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [10, 11], [12, 9], [12, 10]]
    for edge in find_duplicate_edges(edges):
        print(edge)

Output

(2, 3)
(5, 6)

Upvotes: 0

Patrick
Patrick

Reputation: 590

It seems to me that you basically have an adjacency list, and what you need is an adjacency matrix. Here's how I would go about this:

  1. Make a 2-d array(this is the adjacency matrix). For the example you gave, this would be a 12x12 matrix. Initialize the matrix with all False values

  2. For each edge, enter a True value for the corresponding locations(i.e. for [1,2] you would enter True in locations [1,2] and [2,1])

  3. Now, you also need to mark the indirect connections as well. For your new True entry at [1,2] you would find all of the True values in row 2 and set the corresponding values in row 1 to True as well(and vise versa)

Note: Before updating your table you would check for duplicates by checking for locations where rows 1 and 2 are both True

Upvotes: 1

Related Questions