Comparing lists via (unsorted) graphs?

Question

I have a list (of lists) and like to identify elements that have the same "structure"! Here is a minimal example:

example = { {{m1,m2},{m2,m4}} , {{m1,m2},{m1,m4}} }

This list has two elements {{m1,m2},{m2,m4}} and {{m1,m2},{m1,m4}} (which both are lists again). Now, in the problem I am working on each element is associated to a product of Kronecker deltas according to

{{m1,m2},{m2,m4}} -> $\delta_{m1,m2} \delta_{m2,m4}$

with $\delta_{i,j}$ the Kronecker delta. In that sense, {{m1,m2},{m2,m4}} and {{m1,m2},{m1,m4}} are mathematically identical (have the "same structure").

Question: How can I write a Mathematica code that identifies these elements as the same and returns me a new list, where each element with the same structure appears only once together with its "multiplicity" in the original list?

My (failed) solution: I thought I could work with graphs and associate graphs G1 and G2 to {{m1,m2},{m2,m4}} and {{m1,m2},{m1,m4}}, respectively, with corresponding edges as indicated by the pairs. Then, G1 and G2 literally look the same, yet when I try

Tally[{G1,G2}]

I do not get {G1,2}, but {{G1,1},{G2,1}}. So somehow Mathematica is unable to identify graphs with the "same structure" as the same.

How can I solve the problem? Any hint is greatly appreciated! Many thanks!

Edit in response to comments:

The example above is a real sample list: m1, m2, ... are indices that never take on any numerical value. I just want to order them according to the structure I mentioned. The full code I tried is

Test = {{{m1, m2}, {m2, m4}}, {{m1, m2}, {m1, m4}}}; 
graphs = {};
For[i = 1, i <= Length[Test], i++,
 mvert = {m1, m2, m3, m4};
 medges = 
  Table[Test[[i, j]][[1]] <-> Test[[i, j]][[2]], {j, 1, 
    Length[Test[[1]]]}];
 graphs = Append[graphs, {Graph[mvert, medges]}];
 ]
Tally[graphs]

but it doesn't work. I think Dimensions and CountsBy also will not do the job, GroupBy might help but it seems complicated to find the right function according by which to group (that's why I used the graph method because I thought that's the best idea).

Answer 1

The issue is that Tally looks for structural identity, where you only care about whether the connected components are the same. To fix it, you can explicitly group graphs by their connected components (note that I have slightly modified the definition of graphs to remove one level of lists):

mvert = {m1, m2, m3, m4};
graphs = Graph[mvert, UndirectedEdge @@@ #] & /@ Test

GatherBy[graphs, Map[Sort]@*ConnectedComponents]
(* {{Graph[...], Graph[...]}} *)

The Map[Sort] part is to ensure that the individual vertices are properly sorted - this is probably not necessary, but the documentation doesn't guarantee that they are indeed sorted

Answer 2

If I understand your problem correctly, the following GroupBy approach may work. I expanded your example to include a "different" entry that would not be equivalent to the first two, so we can have meaningful counts:

example = { 
   {{m1, m2}, {m2, m4}},
   {{m1, m2}, {m1, m4}},
   {{m1, m1}, {m2, m2}} 
 };

Values@
 Map[First[#] -> Length[#] &]@
  GroupBy[example, (And @@ SameQ @@@ # &)]

(* Out:
{
  {{m1, m2}, {m2, m4}} -> 2,
  {{m1, m1}, {m2, m2}} -> 1
}
*)