Application Areas

Find In- and Out-Components

Find the largest strongly connected component of a directed graph, along with the corresponding in- and out-components.

In[1]:=

g = \!\(\*

GraphicsBox[

NamespaceBox["NetworkGraphics",

DynamicModuleBox[{Typeset`graph = HoldComplete[

Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,

19, 20, 21, 22,

23}, {{{1, 2}, {2, 3}, {3, 1}, {3, 4}, {5, 1}, {6, 7}, {7,

8}, {8, 9}, {9, 10}, {10, 11}, {11, 12}, {12, 6}, {7, 11}, {

9, 12}, {13, 14}, {14, 15}, {15, 13}, {15, 16}, {17, 13}, {

18, 19}, {19, 20}, {20, 18}, {21, 22}, {22, 23}, {23, 21}, {

5, 11}, {1, 6}, {2, 8}, {6, 16}, {10, 15}, {18, 22}, {20,

23}}, Null}, {EdgeShapeFunction -> {"Arrow"}, EdgeStyle -> {

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]]}, ImageSize -> Medium,

VertexCoordinates -> CompressedData["

1:eJxTTMoPSmViYGAQB2IQ/T/ERZgv/5194Et98/fHLtvHR5WyKJ9/ZL/8y/TZ

5Y9f7o+F8PevgPIZQsHq9/tC1S/92SZnW7B+DwMYfLDffHlt+tUEAYf9kt85

1717bX9To1NqRamgQ/Hf5/MkPlzez1/Xy8txh8dhy4ESgRa9L/s/NRZ9+q7M

7LAVyp8Xc3tqvOYv+0qoeqONHomrav7Z74Ga9x8M2B3SwOCb/YKujEMPz0o7

wNzvs7ov4UmklAPM/VtCCudLLxN1gLk/oXS6rZyRiAPM/RB3SzjA3H+6pXVd

+m5lh99ge+7vN62uCpzhouDADJZ/sB+iTglNvSaaejU09Rpw9QB4HawR

"], VertexSize -> {{"Scaled", 0.02}}, VertexStyle -> {

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]]}}]], Typeset`boxes = GraphicsGroupBox[{{

Directive[

Hue[0.6, 0.2, 0.8],

EdgeForm[

Directive[

GrayLevel[0],

Opacity[0.7]]]],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]],

TagBox[

StyleBox[

DiskBox[{0.9510565162951535, 0.3090169943749475},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$1"],

TagBox[

StyleBox[

DiskBox[{0.5877852522924732, -0.8090169943749473},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$2"],

TagBox[

StyleBox[

DiskBox[{-0.587785252292473, -0.8090169943749475},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$3"],

TagBox[

StyleBox[

DiskBox[{-0.9510565162951536, 0.3090169943749473},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$4"],

TagBox[

StyleBox[

DiskBox[{-2.1814794835607965`*^-16, 1.}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$5"],

TagBox[

StyleBox[

DiskBox[{4.094564075455241, 0.872885722602227}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$6"],

TagBox[

StyleBox[

DiskBox[{4.364899077054553, -0.31152930753884006`},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$7"],

TagBox[

StyleBox[

DiskBox[{3.6074372347645816`, -1.2613564150633865`},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$8"],

TagBox[

StyleBox[

DiskBox[{2.392562765235419, -1.2613564150633867`},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$9"],

TagBox[

StyleBox[

DiskBox[{1.6351009229454472`, -0.3115293075388404},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$10"],

TagBox[

StyleBox[

DiskBox[{1.9054359245447583`, 0.8728857226022266},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$11"],

TagBox[

StyleBox[

DiskBox[{2.9999999999999996`, 1.4}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$12"],

TagBox[

StyleBox[

DiskBox[{6.951056516295154, 0.3090169943749475},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$13"],

TagBox[

StyleBox[

DiskBox[{6.587785252292473, -0.8090169943749473},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$14"],

TagBox[

StyleBox[

DiskBox[{5.412214747707527, -0.8090169943749475},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$15"],

TagBox[

StyleBox[

DiskBox[{5.048943483704846, 0.3090169943749473},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$16"],

TagBox[

StyleBox[

DiskBox[{6., 1.}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$17"],

TagBox[

StyleBox[

DiskBox[{9.86602540378444, -0.4999999999999997},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$18"],

TagBox[

StyleBox[

DiskBox[{8.13397459621556, -0.5000000000000003},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$19"],

TagBox[

StyleBox[

DiskBox[{9., 1.}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$20"],

TagBox[

StyleBox[

DiskBox[{12.86602540378444, -0.4999999999999997},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$21"],

TagBox[

StyleBox[

DiskBox[{11.13397459621556, -0.5000000000000003},

0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$22"],

TagBox[

StyleBox[

DiskBox[{12., 1.}, 0.14071054358298435`],

Directive[

Hue[0.6, 0.3, 1],

EdgeForm[

Hue[0.6, 0.8, 0.7]]], StripOnInput -> False], "DynamicName",

BoxID -> "VertexID$23"]}, {

Directive[

Opacity[0.7],

Hue[0.6, 0.7, 0.5]],

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$1", Automatic, Center],

DynamicLocation["VertexID$2", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$1", Automatic, Center],

DynamicLocation["VertexID$6", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$2", Automatic, Center],

DynamicLocation["VertexID$3", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$2", Automatic, Center],

DynamicLocation["VertexID$8", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$3", Automatic, Center],

DynamicLocation["VertexID$1", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$3", Automatic, Center],

DynamicLocation["VertexID$4", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$5", Automatic, Center],

DynamicLocation["VertexID$1", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$5", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$6", Automatic, Center],

DynamicLocation["VertexID$7", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$6", Automatic, Center],

DynamicLocation["VertexID$16", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$7", Automatic, Center],

DynamicLocation["VertexID$8", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$7", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$8", Automatic, Center],

DynamicLocation["VertexID$9", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$9", Automatic, Center],

DynamicLocation["VertexID$10", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$9", Automatic, Center],

DynamicLocation["VertexID$12", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$10", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$10", Automatic, Center],

DynamicLocation["VertexID$15", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$11", Automatic, Center],

DynamicLocation["VertexID$12", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$12", Automatic, Center],

DynamicLocation["VertexID$6", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$13", Automatic, Center],

DynamicLocation["VertexID$14", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$14", Automatic, Center],

DynamicLocation["VertexID$15", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$15", Automatic, Center],

DynamicLocation["VertexID$13", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$15", Automatic, Center],

DynamicLocation["VertexID$16", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$17", Automatic, Center],

DynamicLocation["VertexID$13", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$18", Automatic, Center],

DynamicLocation["VertexID$19", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$18", Automatic, Center],

DynamicLocation["VertexID$22", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$19", Automatic, Center],

DynamicLocation["VertexID$20", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$20", Automatic, Center],

DynamicLocation["VertexID$18", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$20", Automatic, Center],

DynamicLocation["VertexID$23", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$21", Automatic, Center],

DynamicLocation["VertexID$22", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$22", Automatic, Center],

DynamicLocation["VertexID$23", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$23", Automatic, Center],

DynamicLocation["VertexID$21", Automatic, Center]}]},

Directive[

Hue[0.6, 0.8, 0.5],

Arrowheads[Small]], StripOnInput -> False]}}]},

DynamicBox[GraphComputation`NetworkGraphicsBox[

1, Typeset`graph, Typeset`boxes], {

CachedValue :> Typeset`boxes, SingleEvaluation -> True,

SynchronousUpdating -> False, TrackedSymbols :> {}},

ImageSizeCache->{{6.179999999999998,

352.82000000000005`}, {-40.107200000000034`,

33.829433119637116`}}]]],

DefaultBaseStyle->{

"NetworkGraphics",

FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]},

FrameTicks->None,

ImageSize->Medium]\);

In[2]:=

In[3]:=

In[4]:=

In[5]:=

In[6]:=

Out[6]=