Speed up a simple edge connecting algorithm
Just a collection of thoughts...

Terminology

Since you're talking about graphs, it might help the readers if you talk about nodes (your edges) and edges (your links).

Your graph is directed, and as far as I can tell, you're looking for the "strongly connected components".

Use simpler objects

Lists of pairs of pairs aren't very readable IMHO. When showing examples, you can replace them with lists of strings:

edges = ['AB', 'CD', 'EF', 'GH']
links = ['HA', 'BG', 'FC', 'DE']


Python strings are basically tuples of characters, so you don't have to change much in your code. The above example is isomorphic to yours and is much more concise.

KeyError

When calling edges[links[e[1]], you're hoping there won't be any KeyError. Your example would fail with :

edges = ['AB', 'CD', 'EF', 'GH']
links = ['HA', 'BG', 'FC']


Links between multiple edges

What happens in the case of link connecting more than 2 edges, for example

edges = ['AB', 'GH', 'AC']
links = ['HA']


? Your current algorithm doesn't seem to take it into account. A defaultdict(list) might help, for example to keep a list of nodes beginning with A and another list for nodes finishing with H.

Output format

If you only sort the edges, without grouping them in connected components, you're losing information which you have to recover later. You could return a list of sets of edges instead of a flat list of edges.

[{'AB', 'GH'}, {'CD', 'EF'}]


networkx

If you work with graph theory in Python, you should take a look at networkx. It's fast, easy to use and offers many algorithms. All you need to do is to preprocess your data and feed it to a nx.DiGraph.

Your example could become:

import networkx as nx
from collections import defaultdict
import matplotlib

edges = ['AB', 'CD', 'EF', 'GH']
links = ['HA', 'BG', 'FC', 'DE']

G = nx.DiGraph()

from_dict = defaultdict(list)
to_dict = defaultdict(list)

for edge in edges:
    node = ''.join(edge)
    G.add_node(node)
    to_dict[node[0]].append(node)
    from_dict[node[1]].append(node)

for link in links:
    for node1 in from_dict[link[0]]:
        for node2 in to_dict[link[1]]:
            G.add_edge(node1, node2)

list(nx.strongly_connected_components(G))
# [{'AB', 'GH'}, {'CD', 'EF'}]
nx.draw(G, with_labels = True)


It displays:



You get more information, it's more robust, you get diagrams if you want, it can handle more complex cases and (who knows?) it might be faster than your solution for large datasets.