Isomorphism with MultiDiGraph and weighted edges

50 views
Skip to first unread message

Nicholas Bauman

unread,
Apr 11, 2024, 9:10:44 PMApr 11
to networkx-discuss

I am trying to get NetworkX to determine if two graphs are equivalent. Some things about the graphs:

  1. There are 5 vertices labeled "A", "B" (twice), "C", and "D".
  2. Edges to and from vertex "A" are given weights that do not repeat.
  3. The remaining edges do not have weights.

The following is an example of two graphs I am comparing:

import networkx as nx

G1 = nx.MultiDiGraph()
G2 = nx.MultiDiGraph()
G1.add_node(0, name = "A")
G1.add_node(1, name = "D")
G1.add_node(2, name = "B")
G1.add_node(3, name = "B")
G1.add_node(4, name = "C")
G2.add_node(0, name = "A")
G2.add_node(1, name = "D")
G2.add_node(2, name = "B")
G2.add_node(3, name = "B")
G2.add_node(4, name = "C")
G1.add_edges_from([(0, 4, {'weight': 1}), (4, 0, {'weight': 4}), (1, 4), (4, 1), (1, 3), (2, 1), (0, 2, {'weight': 2}), (3, 0, {'weight': 3})])
G2.add_edges_from([(0, 4, {'weight': 2}), (4, 0, {'weight': 4}), (1, 4), (4, 1), (1, 3), (2, 1), (0, 2, {'weight': 1}), (3, 0, {'weight': 3})])
nm = nx.isomorphism.categorical_node_match(["name","name","name","name"], ["A","B","C","D"])
em = nx.isomorphism.numerical_edge_match(['weight','weight','weight','weight'], [1,2,3,4])
print(nx.is_isomorphic(G1,G2, node_match=nm, edge_match=em))



The is_isomorphic function returns True for this case. However, I thought the "weight" attribute would make the function return False because the edges with weights 1 and 2 go to different vertices.

Is this expected, and if so, does it make it so that these two graphs return false?

Reply all
Reply to author
Forward
0 new messages