2
$\begingroup$

I have a directed graph, eg:

$$A\to B\to C$$

$A$ and $C$ may have multiple in- and out-edges, but B has exactly one in- and one out-edge.

I want to remove node $B$ and replace the edges $(A,B)$ and $(B,C)$ with a single edge $(A,C)$.

Is there a name for this operation? In particular a name or algorithm for finding all nodes such as $B$ and removing them from the graph.

$\endgroup$
3
$\begingroup$

You're contracting the edge $(A,B)$ (or, equivalently, $(B,C)$).

To contract an edge $(x,y)$ is to delete the vertex $y$ and make all its neighbours except $x$ itself be neighbours of $x$ instead.

$\endgroup$
  • 1
    $\begingroup$ Thanks very much, this has enabled me to find the appropriate method in python networkx library that does exactly what I wanted. Interestingly I had also found this described as 'smoothing' here en.wikipedia.org/wiki/… $\endgroup$ – Anentropic Dec 2 '16 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.