Function Repository Resource:

EdgeBetweenQ

Source Notebook

Quickly test for existence of an edge between two vertices

Contributed by: Michael Sollami

ResourceFunction["EdgeBetweenQ"][g,e]

yields True if e connects two vertices in the graph g and False otherwise.

Details and Options

ResourceFunction["EdgeBetweenQ"] works on both Graph and EdgeTaggedGraph objects.
ResourceFunction["EdgeBetweenQ"] runs in time O(1).

Examples

Basic Examples (2) 

Determine if two vertices are connected by any edge:

In[1]:=
g = Graph@{UndirectedEdge[1,2,1], UndirectedEdge[1,2,2], UndirectedEdge[2,3,1]}
Out[1]=
In[2]:=
ResourceFunction["EdgeBetweenQ"][g, 1 \[UndirectedEdge] 2]
Out[2]=

Note that EdgeQ will give False because it takes edge properties, such as tags, into account:

In[3]:=
EdgeQ[g, 1 \[UndirectedEdge] 2]
Out[3]=

Scope (2) 

EdgeBetweenQ works regardless of edge tag or edge type:

In[4]:=
g = EdgeTaggedGraph[{1 \[UndirectedEdge] 2, 1 \[DirectedEdge] 2, 2 -> 3}];
EdgeList[g]
Out[5]=
In[6]:=
tests = {
UndirectedEdge[1, 2], 
UndirectedEdge[2, 3], 
UndirectedEdge[3, 1], 
UndirectedEdge[1, 2, 1], 
DirectedEdge[1, 2, Infinity], 
DirectedEdge[2, 3]};
ResourceFunction["PrettyGrid"][{"" -> tests,
  "EdgeQ" -> (EdgeQ[g, #] & /@ tests),
  "EdgeBetweenQ" -> (ResourceFunction["EdgeBetweenQ"][g, #] & /@ tests)}, Spacings -> {3, 1}]
Out[7]=

Check whether an edge is part of a large edge-tagged graph:

In[8]:=
SeedRandom[123];
g = EdgeTaggedGraph@RandomGraph[{10000, 500000}];
ResourceFunction["EdgeBetweenQ"][g, UndirectedEdge[799, 8081]] // RepeatedTiming
Out[9]=

Publisher

Michael Sollami

Version History

  • 1.0.0 – 01 April 2020

Related Resources

License Information