How to stop Networkx from changing the order of nodes from (u,v) to (v,u) in an undirected Graph?

Question

This is a follow up to my previous question.

The question is on the order in which the nodes are saved in the edge list while creating an undirected graph. I have a graph created using the below code. A simple graph is created and new nodes and edges are added between two nodes that already exist.

import networkx as nx
import matplotlib.pyplot as plt
from pprint import pprint

G = nx.OrderedGraph()
head_nodes = range(0, 9)
tail_nodes = range(1, 10)
edge_ls = list(zip(head_nodes, tail_nodes))
G.add_nodes_from(range(0, 10))
G.add_edges_from(edge_ls)

head = 0
tail = 1
G.remove_edge(head, tail)
Nnodes = G.number_of_nodes()
newnodes = [head, Nnodes+1, Nnodes+2, Nnodes+3, tail] # head and tail already exists
newedges = [(x, y) for x, y in zip(newnodes[0:len(newnodes)-1], newnodes[1:len(newnodes)])]
G.add_edges_from(newedges)
I = nx.incidence_matrix(G)
pprint(I)
pprint(G.edges())
nx.draw(G, with_labels=True)
plt.show()

The output of using an undirected graph is:

EdgeView([(0, 11), (1, 2), (1, 13), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (11, 12), (12, 13)])

From the output, we can observe that the edge that was created using G.add_edge(13,1) is displayed as (1,13). I understand this happens because the graph is undirected.

When a directed graph (G.OrderedDiGraph)is used, the output is:

EdgeView([(0, 11), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (11, 12), (12, 13), (13, 1)])

(13, 1) is as I expected the result to be.

However, I am interested to know if there is a particular way in which the nodes can be named so that one can avoid Networkx from reordering the nodes from (u,v) , which is the user input, to (v,u) in an undirected graph.

EDIT: I am avoiding the use of diGraph because there are inputs like this for which diGraph yields the following result

In this directed graph, nodes 24 and 28 have a sum of indegree and outdegree to be 1. However, I want the arrows to be directed from node 24 to 28, similar to unidirectional flow in a traffic network where there could be different routes for the traffic to flow from point 24 to point 28. The directions created by diGraph of Networkx doesn't represent my real system. Therefore, I don't want to use diGraph.

Answer 1

As I said previously and Joel has said in his answer, you need to store the edges in your own data structure that suits your need instead of relying on the graph. Pick a data structure and define some function add_edge which adds to both that data structure and your graph, and only use that function to add edges. If you simply want to remember all the edges you ever had, this will do:

edges = set()

def add_edge(u, v):
    G.add_edge(u, v)
    edges.add((u, v))

If you want to retrieve some subset of the original edges based on a change to the graph (e.g. you want to see which edges remain after removing nodes) then use a dictionary which maps both orderings of each edge to the original:

edges = {}

def add_edge(u, v):
    G.add_edge(u, v)
    edges[(u, v)] = (u, v)
    edges[(v, u)] = (u, v)

Then after you change the graph you can get the original edges like so:

{edges[edge] for edge in G.edges()}

Answer 2

No, this is not possible with networkx. Even if you try to use an OrderedGraph, the best you will get is

a consistent order not a particular order.

When you choose to use a Graph instead of a DiGraph, you are explicitly stating that it is undirected, so direction does not matter, and it would be inefficient for networkx to save information about the direction. In the underlying data structure, it doesn't save an edge list. Rather it saves a dict which says what the neighbors of each node are (so no information is stored about the order the user entered it in). When it reconstructs an EdgeView, it uses this dict, so all information about how the user entered it is already lost.

If you need to do this, I would recommend using a DiGraph. If you need it to be some hybrid of directed (tracking the order of an edge) while still undirected (treating each edge as having both directions), I would recommend storing the edge directions separately from the networkx graph.