Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language
This resource function is obsolete. Use the function NeighborhoodGraph instead.

Function Repository Resource:

 SubgraphExpand

Source Notebook

Expand a subgraph inside the space of a graph

Contributed by: Bradley Klee

ResourceFunction["SubgraphExpand"][g,{v1,v1,…},r]

selects the subgraph of graph consisting of all edges between only those vertices of g whose GraphDistance through g to the nearest vertex vi is less than or equal to radius r.

ResourceFunction["SubgraphExpand"][g,sg,r]

accepts subgraph sg as the initial value (or kernel) of the expansion.

Details

ResourceFunction["SubgraphExpand"] accepts the same options as Graph.

Examples

Basic Examples (2) 

Expand a cycle graph around one vertex:

In[1]:=
ResourceFunction["SubgraphExpand"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7, 8}, {Null, SparseArray[ Automatic, {8, 8}, 0, {1, {{0, 2, 4, 6, 8, 10, 12, 14, 16}, {{2}, {8}, {1}, { 3}, {2}, {4}, {3}, {5}, {4}, {6}, {5}, {7}, {6}, {8}, { 1}, {7}}}, Pattern}]}, {GraphLayout -> "CircularEmbedding"}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{-0.707106781186548, 0.7071067811865482}, {-7.044813998280222*^-16, 1.}, { 0.707106781186547, 0.7071067811865467}, { 1., -1.133107779529596*^-15}, { 0.7071067811865481, -0.7071067811865483}, { 6.049014748177263*^-16, -1.}, {-0.7071067811865471, -0.7071067811865468}, {-1., 1.0106430996148606`*^-15}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[{{1, 2}, {1, 8}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, { 6, 7}, {7, 8}}, 0.02261146496815286]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.02261146496815286], DiskBox[2, 0.02261146496815286], DiskBox[3, 0.02261146496815286], DiskBox[4, 0.02261146496815286], DiskBox[5, 0.02261146496815286], DiskBox[6, 0.02261146496815286], DiskBox[7, 0.02261146496815286], DiskBox[8, 0.02261146496815286]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FormatType->TraditionalForm, FrameTicks->None]\), {1}, 2]
Out[1]=

Expand a grid graph around its central vertex at several radii:

In[2]:=
ResourceFunction["SubgraphExpand"][GridGraph[{5, 5}], {13}, #, GraphLayout -> "SpringElectricalEmbedding"] & /@ Range[0, 4]
Out[2]=

Use directed edges to only expand the grid graph into the Northeast quadrant:

In[3]:=
ResourceFunction["SubgraphExpand"][ GridGraph[{5, 5}, DirectedEdges -> True], {13}, #, GraphLayout -> "SpringElectricalEmbedding"] & /@ Range[0, 4]
Out[3]=

Scope (2) 

Expand a graph around multiple initial vertices:

In[4]:=
ResourceFunction["SubgraphExpand"][ PetersenGraph[6, 4], {1, 3, 5}, #] & /@ Range[0, 3]
Out[4]=

Define a graph:

In[5]:=
graph = RandomGraph[{20, 40}]
Out[5]=

Extract a subgraph:

In[6]:=
subgraph = Subgraph[graph, Range[5]]
Out[6]=

Expand that subgraph by radius one:

In[7]:=
ResourceFunction["SubgraphExpand"][graph, subgraph, 1]
Out[7]=

Possible Issues (2) 

SubgraphExpand does not recognize subgraph isomorphism:

In[8]:=
ResourceFunction["SubgraphExpand"][ButterflyGraph[3], ButterflyGraph[2], #, VertexCoordinates -> MapIndexed[#2[[1]] -> #1 &, GraphEmbedding[ButterflyGraph[3]]] ] & /@ Range[0, 3]
Out[8]=

This can be fixed by manually choosing vertices:

In[9]:=
ResourceFunction["SubgraphExpand"][ButterflyGraph[3], {4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14}, #, VertexCoordinates -> MapIndexed[#2[[1]] -> #1 &, GraphEmbedding[ButterflyGraph[3]]] ] & /@ Range[0, 4]
Out[9]=

Neat Examples (1) 

Expand a polyhedral skeleton graph into three dimensions:

In[10]:=
With[{g0 = Graph3D[PolyhedronData["TruncatedIcosahedron", "Skeleton"], Sequence[ GraphLayout -> "SpringElectricalEmbedding", VertexCoordinates -> Automatic]]}, Grid[Partition[ Graph3D@ResourceFunction["SubgraphExpand"][g0, {1}, #] & /@ Range[GraphDiameter[g0]], 3], Sequence[ Frame -> All, Spacings -> {2, 2}, FrameStyle -> LightGray]]]
Out[10]=

Publisher

Brad Klee

Version History

  • 1.0.0 – 26 April 2022

Related Resources

License Information