How to correctly contract an edge in a network?

Question

Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined.

Let me cite the definition I do have at hand:

_{Source: JAMES B. ORLIN - A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM, Section 4.1. Contraction}

[...] any edge, say $(k, \ell)$, can be contracted into a single node $p$. The contraction operation consists of: letting $b(p) = b(k) + b(\ell)$ and $e(p) = e(k) + e(\ell)$; replacing each edge $(i, k)$ or $(i, \ell)$ by the edge $(i, p)$; replacing each edge $(k, i)$ or $(\ell, i)$ by the edge $(p, i)$; and letting the cost of an edge in the contracted network equal that of the edge it replaces.[...]

$b$ and $p$ are functions defining values for certain properties of a node; their meaning is unimportant for understanding contraction.

Consider the following graph described in "adjacency speak", where e.g. node 0 has an edge to the nodes 1, 2 and 5; node 5 has no outgoing edges; node 3 has an edge to node 4 and so on...

0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
5

Now I want to contract the edge $(1,2)$. Note that there is an edge $(2,1)$, too. Should the application of the contraction operation yield the following directed graph, where the newly introduced node $p$ has the id $6$?

0 -> 6, 5
3 -> 4
4 -> 5
5
6 -> 3, 3, 5, 6 # Note that we got two edges from node 6 to node 3.
                # Note that we also have an edge from 6 to 6, i.e. a loop.

Thanks a lot!

Answer 1

The very next sentence (!) of Orlin's paper says

We point out that the contraction operation may lead to the creation of multiple arcs, i.e., several arcs with the same head and tale nodes.

In some contexts, you might want to replace multiple arcs between the same two nodes with a single arc whose weight (or capacity or whatever it's being called) is the sum of the weights of the original arcs; in other contexts, it might make more sense to keep them separate. Orlin is keeping them separate.

For example, if the arcs represent trading relationships between companies, it makes sense to merge the arcs: if companies $A$ and $B$ both sell to $C$ and $A$ and $B$ merge, it makes more sense to say that $C$ is a customer of the new company once, with a single arc, than to say that it's a customer twice, by having two arcs. On the other hand, if arcs represent roads between towns and two towns merge, it makes sense to keep the arcs separate: if there's a road from each of $A$ and $B$ to $C$ and $A$ and $B$ merge, there are still two roads from the merged town to $C$.

So, contracting the arc $(1,2)$ into a new node $6$ has the following effects:

• it converts the arc $(1,2)$ into the loop $(6,6)$;
• it converts the arc $(2,1)$ into a second copy of the loop $(6,6)$;
• replaces the arcs $(0,1)$ and $(0.2)$ with two copies of $(0,6)$;