How to compare topologies of graphs with same tip names but different internal vertex names


I am trying to do an analysis where I compare two directed acyclic graphs to see if the topologies are similar or different. The tip vertices have the same names, but the internal vertices have different names (a product of how these graphs were created by a different program, admixtools2). I have tried identical_graphs(), intersection(), and difference(). However, it seems that vertices must have the same names across graphs if similarities are to be called. Is there any way to compare graph topology if the graphs don’t share internal vertex names?

Thank you in advance!

For an example, here are two graphs which have the same exact topologies. The tip vertices have the names diploperennis_, mexicana_, parviglumis_, Nold_, and maize_. The graph objects are named g0 and g2.

> g0

IGRAPH 39726c3 DNW- 11 11 -- 
+ attr: name (v/c), type (e/c), weight (e/n), low (e/n), high (e/n)
+ edges from 39726c3 (vertex names):
 [1] R     ->diploperennis_ R     ->Rr             Rr    ->Rrl            Rr    ->admix         
 [5] Rrl   ->mexicana_      admix ->Nold_          admix ->admixw         admixw->parviglumis_  
 [9] Rrl   ->admixy         admixy->maize_         admixw->admixy  

> g2

IGRAPH 270d00c DNW- 11 11 -- 
+ attr: name (v/c), type (e/c), weight (e/n), low (e/n), high (e/n)
+ edges from 270d00c (vertex names):
 [1] R    ->diploperennis_ R    ->Rr             Rr   ->Rrr            Rrr  ->mexicana_     
 [5] Rrrr ->parviglumis_   Rrrp ->Rrrr           admix->maize_         Rrr  ->admix         
 [9] Rr   ->Rrrp           Rrrr ->admix          Rrrp ->Nold_   

and here’s the output if using identical_graphs() or intersection() on these two graphs:

> igraph::identical_graphs(g0,g2) #should be true 

> igraph::intersection(g0,g2) #shows which edges are shared between graphs
IGRAPH 4d6dff6 DN-- 14 2 -- 
+ attr: name (v/c), type_1 (e/c), type_2 (e/c), weight_1 (e/n), weight_2 (e/n), low_1
| (e/n), low_2 (e/n), high_1 (e/n), high_2 (e/n)
+ edges from 4d6dff6 (vertex names):
[1] R->diploperennis_ R->Rr    

I suppose you are looking for isomorphic().

Look up the concept of graph isomorphism.

1 Like