Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 HypergraphNeighborhoods

Source Notebook

Enumerate all the neighborhoods of a hypergraph up to a given distance

Contributed by: Stephen Wolfram

ResourceFunction["HypergraphNeighborhoods"][hg,v,r]

gives all the neighborhoods of the hypergraph hg up to a distance r from v.

ResourceFunction["HypergraphNeighborhoods"][hg,r]

gives all the neighborhoods of the hypergraph hg up to a distance r from the middle vertex in a sorted vertex list.

Details and Options

ResourceFunction["HypergraphNeighborhoods"] converts hyperedges to single edges, so the hyperedge {1,2,3} is converted to {{1,2},{2,3},{1,3}}. A length-n hyperedge is converted into (n-1)! edges.
The distance-k neighborhood of a vertex is the set of vertices at graph distance k.

Examples

Basic Examples (2) 

With the face indices of an octahedron as a hypergraph, find the first two neighborhoods of vertex 3:

In[1]:=
ResourceFunction[ "HypergraphNeighborhoods"][{{4, 5, 6}, {4, 6, 2}, {4, 1, 2}, {4, 1, 5}, {5, 1, 3}, {5, 3, 6}, {3, 1, 2}, {6, 3, 2}}, 3, 2]
Out[1]=

Since vertex 3 is the middle-low vertex in (1,2,3,4,5,6), the two-argument form of the function returns the same result:

In[2]:=
ResourceFunction[ "HypergraphNeighborhoods"][{{4, 5, 6}, {4, 6, 2}, {4, 1, 2}, {4, 1, 5}, {5, 1, 3}, {5, 3, 6}, {3, 1, 2}, {6, 3, 2}}, 2]
Out[2]=

Scope (2) 

The edges of an octahedral graph give different neighborhoods:

In[3]:=
ResourceFunction[ "HypergraphNeighborhoods"][{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}}, 1, 2]
Out[3]=

The first two neighborhoods of vertex 8 in a more complex hypergraph:

In[4]:=
ResourceFunction[ "HypergraphNeighborhoods"][{{1, 1, 9}, {1, 9, 5}, {1, 5, 10}, {5, 10, 3}, {1, 3, 11}, {3, 11, 6}, {3, 6, 12}, {6, 12, 2}, {1, 2, 13}, {2, 13, 7}, {2, 7, 14}, {7, 14, 4}, {2, 4, 15}, {4, 15, 8}, {4, 8, 16}, {8, 16, 1}}, 8, 4]
Out[4]=

Version History

  • 2.0.0 – 14 April 2020
  • 1.0.0 – 18 February 2020

Related Resources

License Information