I like this algorithm: def connected_components(neighbors): seen = set() def component(node): nodes = set([node]) while nodes: node = nodes.pop() seen.add(node) nodes |= neighbors[node] – seen yield node for node in neighbors: if node not in seen: yield component(node) Not only is it short and elegant, but also fast. Use it like so (Python 2.7): old_graph … Read more
This is a common problem in image processing. There are many variations, such as flood filling a region in an image, or finding what pixels belong to the same region. One common approach is to use depth first search. The idea is that you traverse your image from left to right and top to bottom … Read more
These are the connected components of a graph, and can be found using a graphing library such as networkx. For your second example: >>> edges = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6), (8, 9)] >>> graph = nx.Graph(edges) >>> [tuple(c) for c in nx.connected_components(graph)] [(1, 2, 3, 4, 5, … Read more
The OpenCV 3.0 docs for connectedComponents() don’t mention Python but it actually is implemented. See for e.g. this SO question. On OpenCV 3.4.0 and above, the docs do include the Python signatures, as can be seen on the current master docs. The function call is simple: num_labels, labels_im = cv2.connectedComponents(img) and you can specify a … Read more
The function works as follows: # Import the cv2 library import cv2 # Read the image you want connected components of src = cv2.imread(‘/directorypath/image.bmp’) # Threshold it so it becomes binary ret, thresh = cv2.threshold(src,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU) # You need to choose 4 or 8 for connectivity type connectivity = 4 # Perform the operation output = … Read more
You can see your list as a notation for a Graph, ie [‘a’,’b’,’c’] is a graph with 3 nodes connected to each other. The problem you are trying to solve is finding connected components in this graph. You can use NetworkX for this, which has the advantage that it’s pretty much guaranteed to be correct: … Read more