2
$\begingroup$

When programming with graphs, it is sometimes important that UndirectedEdge[a,b] and UndirectedEdge[b,a] are treated as equivalent. Up to M12.0 it was possible to handle this by temporarily setting Orderless on UndirectedEdge. But in M12.1, UndirectedEdge can have three arguments, so Orderless cannot be used.

What is a good alternative that does not compromise peformance?

This is the workaround I have been using in IGraph/M:

canonicalEdgeBlock::usage = "canonicalEdgeBlock[expr] evaluates expression while making sure that all UndirectedEdge expressions inside are ordered canonically.";
SetAttributes[canonicalEdgeBlock, HoldAllComplete]

(* In M12.1 and later, UndirectedEdge can have 3 arguments, so we cannot canonicalize simply with Orderless. *)
(* TODO  The workaround /; Not@OrderedQ[{a, b}] is 10x slower than Orderless! *)
If[$VersionNumber >= 12.1,
  canonicalEdgeBlock[expr_] :=
      Internal`InheritedBlock[{UndirectedEdge},
        Unprotect[UndirectedEdge];
        UndirectedEdge[a_, b_, rest___] /; Not@OrderedQ[{a, b}] := UndirectedEdge[b, a, rest];
        expr
      ]
  ,
  canonicalEdgeBlock[expr_] :=
      Internal`InheritedBlock[{UndirectedEdge},
        SetAttributes[UndirectedEdge, Orderless];
        expr
      ]
]

It comes at a cost of a 5x to 10x slowdown. I am looking for solutions that are faster.

Here's an example use of this utility function in IGraph/M.

$\endgroup$
2
  • 2
    $\begingroup$ What about comparing the adjacency matrices instead? In general, I find working with the symbolic expressions for directed/undirected edges super inefficient... $\endgroup$ – Henrik Schumacher Mar 19 '20 at 12:37
  • $\begingroup$ @HenrikSchumacher I am looking for a solution that ensures that undirected edges are always ordered canonically. Sometimes one must work with edges directly. For example, a function may take edges as input. Adjacency matrices can be applied in specific situations only. Also, some adjacency matrix manipulation, such as AdjacencyGraph, is also terribly slow. $\endgroup$ – Szabolcs Mar 29 '20 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.