Working Material

Graph algorithms

Vojtěch (Vojtech) Bartík (Bartik)

Author

Vojtěch (Vojtech) Bartík (Bartik)

Title

Graph algorithms

Description

Defines functions realizing some well known algorithms for simple graphs (or their modifications) and producing not only expected results but also tables (and in some cases also animations) helping to understand how these algorithms work.

Graph Algorithms

Demo

Vojtěch Bartík, February 2021

Convention : All graphs are supposed simple without loops. Vertices are positive natural numbers and all edges are supposed to be directed or undirected.

In[]:=

Off[EdgeWeightedGraphQ::argx,General::argx,Graph::supp,Unset::norep];

Axiliary Definitions

EdgeListQ[E]
returns True if
E
may be considered as the EdgeList of a directed or undirected graph in the sense of Mathematica, and False in the opposite case.
EdgeListQ[E,∞]
returns True if
Graph[E]
is undirected graph in the sense of Mathematica and False in the opposite case.


WeightedEdgeListQ[E]
returns True if
First/@E
may be considered as the EdgeList of a directed or undirected graph with the
EdgeWeightLast/@E
in the sense of Mathematica, and False in the opposite case.
WeightedEdgeListQ[E,∞]
returns True if
Graph[First/@E,EdgeWeight->Last/@E]
is the undirected graph in the sense of Mathematica, and False in the opposite case.


WeightedAdjacencyMatrixQ[M]
returns True if
M
is a square matrix with numeric entries and zeros on the diagonal, and False in the opposite case.
WeightedAdjacencyMatrixQ[M,∞]
returns True if
M
is a symmetric square matrix with numeric non-diagonal entries and
∞
’s on the diagonal, and False in the opposite case.


ToEdgeList


ToWeightedEdgeList


ToWeightedAdjacencyMatrix


ToGraph


ToEdgeWeightedGraph


Random EdgeLists, Matrices and Graphs

RandomEdgeList, RandomWeightedEdgeList


RandomWeightedAdjacencyMatrix


RandomAcyclicGraph


Components

Example 1

In[]:=

V8=Range[1,10];E8={{2,3},{3,4},{4,3},{5,9},{6,8},{7,8},{7,10},{8,10}};gE8=ToGraph[E8,EdgeShapeFunctionGraphElementData[{"Arrow","ArrowSize".05}],DirectedEdgesTrue,VertexLabels"Name",VertexSize0.1,VertexStyleRed,ImagePadding20,GraphLayoutAutomatic,VertexCoordinatesEllipse[6,3,10]]

Out[]=

In[]:=

{AdjacentVertices[gE8,#,-1]&/@V8,AdjacentVertices[gE8,#,1]&/@V8,AdjacentVertices[E8,#,0]&/@V8,AdjacentVertices[E8,#]&/@V8}//Column[#,Center,Spacings1]&

Out[]=

{{},{},{2,4},{3},{},{},{},{6,7},{5},{7,8}}

{{},{3},{4},{3},{9},{8},{8,10},{10},{},{}}

{{},{3},{2,4},{3},{9},{8},{8,10},{6,7,10},{5},{7,8}}

In[]:=

{AccesibleVertices[gE8,#,-1]&/@V8,AccesibleVertices[gE8,#,1]&/@V8,AccesibleVertices[E8,#,0]&/@V8,AccesibleVertices[E8,#]&/@V8}//Column[#,Center,Spacings1]&

Out[]=

{{1},{2},{2,3,4},{2,3,4},{5},{6},{7},{6,7,8},{5,9},{6,7,8,10}}

{{1},{2,3,4},{3,4},{3,4},{5,9},{6,8,10},{7,8,10},{8,10},{9},{10}}

{{1},{2,3,4},{2,3,4},{2,3,4},{5,9},{6,7,8,10},{6,7,8,10},{6,7,8,10},{5,9},{6,7,8,10}}

In[]:=

{Components@E8,Components@gE8,StrongComponents@E8//Sort,ConnectedComponents@gE8//Sort}//Column[#,Center]&

Out[]=

{{1},{2,3,4},{5,9},{6,7,8,10}}

{{1},{2},{5},{6},{7},{8},{9},{10},{3,4}}

Example 2

In[]:=

V9=Range[13];E9={{1,3},{1,11},{2,6},{3,9},{4,12},{5,7},{6,10},{7,13},{9,11}};gE9∞=ToGraph[E9,∞,ImagePadding20,GraphLayoutAutomatic,VertexLabels"Name",VertexSize0.15,VertexStyleRed,VertexCoordinatesEllipse[6,3,13]]

Out[]=

In[]:=

{AdjacentVertices[gE9∞,#,-1]&/@V9,AdjacentVertices[gE9∞,#,1]&/@V9,AdjacentVertices[E9,#,0]&/@V9,AdjacentVertices[E9,#]&/@V9}//Column[#,Center,Spacings1]&

Out[]=

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

{{3,11},{6},{9},{12},{7},{10},{13},{},{11},{},{},{},{}}

{{3,11},{6},{1,9},{12},{7},{2,10},{5,13},{},{3,11},{6},{1,9},{4},{7}}

In[]:=

{AccesibleVertices[gE9∞,#,-1]&/@V9,AccesibleVertices[gE9∞,#,1]&/@V9,AccesibleVertices[gE9∞,#,0]&/@V9,AccesibleVertices[gE9∞,#]&/@V9}//Column[#,Center,Spacings1]&

Out[]=

{{1},{2},{1,3},{4},{5},{2,6},{5,7},{8},{1,3,9},{2,6,10},{1,3,9,11},{4,12},{5,7,13}}

{{1,3,9,11},{2,6,10},{3,9,11},{4,12},{5,7,13},{6,10},{7,13},{8},{9,11},{10},{11},{12},{13}}

{{1,3,9,11},{2,6,10},{1,3,9,11},{4,12},{5,7,13},{2,6,10},{5,7,13},{8},{1,3,9,11},{2,6,10},{1,3,9,11},{4,12},{5,7,13}}

In[]:=

{Components@E9,Components@gE9∞,ConnectedComponents@gE9∞}//Column[#,Center]&

Out[]=

{{1,3,9,11},{2,6,10},{4,12},{5,7,13},{8}}

{{1,3,11,9},{5,7,13},{6,2,10},{12,4},{8}}

In[]:=

{StrongComponents@E9//Sort,ConnectedComponents@ToGraph[E9]//Sort}//Column[#,Center]&

Out[]=

{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13}}

Minimal Spanning Tree

Options

Alternatives for optional arguments of Jarnik-Prim’ algorithm: -- Dividers -> {{Thin,Thin,{Dotted},Thin,Thin},Thin} | any admissible data,-- FrameColor → Red,-- GraphLayout  Automatic | any Graph layout, -- ImagePadding -> 10 | any number,-- ImageSize -> Automatic | {450, 150} | any size,-- ItemColor → Green | any color,-- SelectionRule -> First | Last | RandomChoice,-- ShowTree -> True | False,-- Sort -> False | True,-- Spacings → {1, 1} | any pair of positive numbers | Automatic,-- Trace  True | False,-- Tree  True | False,-- TreeEdgeStyle  {Thickness[0.004], Red} | any admissible Graph EdgeStyle,-- VertexCoordinates  Automatic | Ellipse[a, b] ,-- VertexLabels -> “Name” | any admissible Graph VertexLabels,-- VertexLabelStyle  Directive[Blue, 10, Bold] | any admissible Graph VertexLabelStyle.-- VertexSize -> Tiny | Automatic | Small | Medium | Large | number | {“Scaled”, number},-- VertexStyle  Blue | any color.

In[]:=

Options[JarnikPrimTree]

Out[]=

Dividers{{Thickness[Tiny],Thickness[Tiny],{Dashing[{0,Small}]},Thickness[Tiny],Thickness[Tiny]},Thickness[Tiny]},FrameColor

,GraphLayoutAutomatic,ImagePadding10,ImageSizeAutomatic,ItemColor

,SelectionRuleFirst,ShowTreeTrue,SortFalse,Spacings{0.7,0.7},TraceTrue,TreeTrue,TreeEdgeStyleThickness[0.004],

,VertexCoordinatesAutomatic,VertexLabelsName,VertexLabelStyleDirective

,10,Bold,VertexSizeTiny,VertexStyle



Alternatives for optional arguments of Borůvka-Kruskal’s algorithm -- AdjustedEdgeList → True, -- GraphLayout  Automatic | any Graph layout,-- ImagePadding -> 10 | any number,-- ImageSize -> Automatic | {450, 150} | any size,-- SelectionRule -> First | Last | RandomChoice,-- ShowTree -> True | False,-- Sort -> False | True,-- Spacings → {1, 1} | any pair of positive numbers | Automatic,-- Trace  True | False,-- Tree  True | False,-- TreeEdgeStyle  {Thickness[0.004], Red} | any admissible Graph EdgeStyle,-- VertexCoordinates  Automatic | Ellipse[a, b],-- VertexLabels -> “Name” | any admissible Graph VertexLabels,-- VertexLabelStyle  Directive[Blue, 10, Bold] | any admissible Graph VertexLabelStyle,-- VertexSize -> Tiny | Automatic | Small | Medium | Large | number | {“Scaled”, number},-- VertexStyle  Blue | any color.

In[]:=

Options[BoruvkaKruskalTree]

Out[]=

AdjustedEdgeListTrue,GraphLayoutAutomatic,ImagePadding10,ImageSizeAutomatic,SelectionRuleFirst,ShowTreeTrue,SortFalse,Spacings{0.7,0.7},TraceTrue,TreeTrue,TreeEdgeStyleThickness[0.004],

,VertexCoordinatesAutomatic,VertexLabelsName,VertexLabelStyleDirective

,10,Bold,VertexSizeTiny,VertexStyle



Example 3

In[]:=

M1=

∞	8	2	2	9	2
8	∞	-5	-1	∞	19
2	-5	∞	-5	3	14
2	-1	-5	∞	3	-2
9	∞	3	3	∞	2
2	19	14	-2	2	∞

;

In[]:=

EM1=ToWeightedEdgeList[M1];gM1=ToEdgeWeightedGraph[M1];Column[{EM1,gM1,EdgeList[gM1],Options[gM1,EdgeWeight]},Center,Spacings1]

Out[]=

{{{1,2},8},{{1,3},2},{{1,4},2},{{1,5},9},{{1,6},2},{{2,3},-5},{{2,4},-1},{{2,6},19},{{3,4},-5},{{3,5},3},{{3,6},14},{{4,5},3},{{4,6},-2},{{5,6},2}}

Graph

Vertex count: 6

Edge count: 14



{12,13,14,15,16,23,24,26,34,35,36,45,46,56}

{EdgeWeight{8,2,2,9,2,-5,-1,19,-5,3,14,3,-2,2}}

In[]:=

JarnikPrimTree[EM1,1]

{{{1,3},2},{{3,2},-5},{{3,4},-5},{{4,6},-2},{{6,5},2}}

Total Weight-8

★

Selected Edge

★

{1,3}2

★

-5

★

-5

{3,2}-5

★

-5

{3,4}-5

★

-2

{4,6}-2

★

{6,5}2

In[]:=

JarnikPrimTree[gM1,1,ShowTreeFalse];

{{{1,3},2},{{3,2},-5},{{3,4},-5},{{4,6},-2},{{6,5},2}}

Total Weight-8

★

Selected Edge

★

{1,3}2

★

-5

★

-5

{3,2}-5

★

-5

{3,4}-5

★

-2

{4,6}-2

★

{6,5}2

In[]:=

JarnikPrimTree[gM1,1,ShowTreeFalse,TraceFalse];

{{{1,3},2},{{3,2},-5},{{3,4},-5},{{4,6},-2},{{6,5},2}}

Total Weight-8

In[]:=

BoruvkaKruskalTree[M1];

{{{2,3},-5},{{3,4},-5},{{4,6},-2},{{1,3},2},{{5,6},2}}

Total Weight-8

{{{2,3},-5},{{3,4},-5},{{4,6},-2},{{2,4},-1},{{1,3},2},{{1,4},2},{{1,6},2},{{5,6},2},{{3,5},3},{{4,5},3},{{1,2},8},{{1,5},9},{{3,6},14},{{2,6},19}}

Selected edge	Forest components
{2,3}-5	{{2,3}}
{3,4}-5	{{2,3,4}}
{4,6}-2	{{2,3,4,6}}
{1,3}2	{{1,2,3,4,6}}
{5,6}2	{{1,2,3,4,5,6}}

In[]:=

BoruvkaKruskalTree[EM1,ShowTreeFalse];

{{{2,3},-5},{{3,4},-5},{{4,6},-2},{{1,3},2},{{5,6},2}}

Total Weight-8

{{{2,3},-5},{{3,4},-5},{{4,6},-2},{{2,4},-1},{{1,3},2},{{1,4},2},{{1,6},2},{{5,6},2},{{3,5},3},{{4,5},3},{{1,2},8},{{1,5},9},{{3,6},14},{{2,6},19}}

Selected edge	Forest components
{2,3}-5	{{2,3}}
{3,4}-5	{{2,3,4}}
{4,6}-2	{{2,3,4,6}}
{1,3}2	{{1,2,3,4,6}}
{5,6}2	{{1,2,3,4,5,6}}

In[]:=

BoruvkaKruskalTree[gM1,ShowTreeFalse,TraceFalse];

{{{2,3},-5},{{3,4},-5},{{4,6},-2},{{1,3},2},{{5,6},2}}

Total Weight-8

Example 4

In[]:=

M2=

∞	2	2	3	2	-4	2
2	∞	∞	2	∞	3	1
2	∞	∞	-3	4	1	∞
3	2	-3	∞	1	2	4
2	∞	4	1	∞	2	∞
-4	3	1	2	2	∞	1
2	1	∞	4	∞	1	∞

;

In[]:=

EM2=ToWeightedEdgeList[M2];gM2=ToEdgeWeightedGraph[M2,GraphLayoutNone];EM2

Out[]=

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

In[]:=

JarnikPrimTree[M2,2,AspectRatio1/3,SelectionRuleLast];

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

Total Weight-3

★

Selected Edge

★

∞

{2,7}1

★

∞

★

{7,6}1

-4

★

{6,1}-4

★

{6,3}1

★

-3

★

{3,4}-3

★

{4,5}1

In[]:=

BoruvkaKruskalTree[M2,AspectRatio1/3,SelectionRuleLast];

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

Total Weight-3

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

Selected edge	Forest components
{1,6}-4	{{1,6}}
{3,4}-3	{{1,6},{3,4}}
{6,7}1	{{1,6,7},{3,4}}
{4,5}1	{{1,6,7},{3,4,5}}
{3,6}1	{{1,3,4,5,6,7}}
{2,7}1	{{1,2,3,4,5,6,7}}

Example 5

In[]:=

M3=

∞	1	-2	4	-1	2	3
1	∞	∞	-2	4	∞	-4
-2	∞	∞	1	3	2	-2
4	-2	1	∞	-3	-2	-1
-1	4	3	-3	∞	1	4
2	∞	2	-2	1	∞	-3
3	-4	-2	-1	4	-3	∞

;

In[]:=

EM3=ToWeightedEdgeList[M3];gM3=ToEdgeWeightedGraph[M3];EM3

Out[]=

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

In[]:=

JarnikPrimTree[EM3,3,SelectionRuleRandomChoice,SortTrue,VertexCoordinatesEllipse[6,2]];

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

Total Weight-16

★

Selected Edge

-2

∞

★

-2

{3,7}-2

-2

-4

★

-1

-3

★

{2,7}-4

-2

★

-2

-3

★

{6,7}-3

-2

★

-2

★

{2,4}-2

-2

★

-3

★

{4,5}-3

-2

★

{1,3}-2

In[]:=

BoruvkaKruskalTree[EM3,SelectionRuleRandomChoice,SortTrue,TraceTrue,VertexCoordinatesEllipse[6,2]];

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

Total Weight-16

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

Selected edge	Forest components
{2,7}-4	{{2,7}}
{4,5}-3	{{2,7},{4,5}}
{6,7}-3	{{2,6,7},{4,5}}
{4,6}-2	{{2,4,5,6,7}}
{1,3}-2	{{2,4,5,6,7},{1,3}}
{3,7}-2	{{1,2,3,4,5,6,7}}

Example 6

In[]:=

M4=

∞	-1	∞	-2	4	3	1	∞
-1	∞	∞	∞	4	-1	3	-1
∞	∞	∞	-3	∞	3	2	∞
-2	∞	-3	∞	∞	∞	3	3
4	4	∞	∞	∞	-4	-1	2
3	-1	3	∞	-4	∞	4	4
1	3	2	3	-1	4	∞	-4
∞	-1	∞	3	2	4	-4	∞

;

In[]:=

EM4=ToWeightedEdgeList[M4];gM4=ToEdgeWeightedGraph[M4];EM4

Out[]=

{{{1,2},-1},{{1,4},-2},{{1,5},4},{{1,6},3},{{1,7},1},{{2,5},4},{{2,6},-1},{{2,7},3},{{2,8},-1},{{3,4},-3},{{3,6},3},{{3,7},2},{{4,7},3},{{4,8},3},{{5,6},-4},{{5,7},-1},{{5,8},2},{{6,7},4},{{6,8},4},{{7,8},-4}}

In[]:=

JarnikPrimTree[gM4,4,SelectionRuleRandomChoice,SortTrue,TraceFalse,VertexCoordinatesEllipse[6,2]];

{{{1,2},-1},{{1,4},-2},{{2,6},-1},{{2,8},-1},{{3,4},-3},{{5,6},-4},{{7,8},-4}}

Total Weight-16

In[]:=

BoruvkaKruskalTree[gM4,SelectionRuleRandomChoice,SortTrue,TraceFalse,VertexCoordinatesEllipse[6,2]];

{{{1,2},-1},{{1,4},-2},{{2,6},-1},{{2,8},-1},{{3,4},-3},{{5,6},-4},{{7,8},-4}}

Total Weight-16

Example 7

In[]:=

M5=

∞	∞	-3	3	∞	∞	2	4
∞	∞	2	-3	2	4	∞	3
-3	2	∞	2	-2	-1	4	∞
3	-3	2	∞	∞	∞	∞	3
∞	2	-2	∞	∞	∞	-1	∞
∞	4	-1	∞	∞	∞	3	-2
2	∞	4	∞	-1	3	∞	∞
4	3	∞	3	∞	-2	∞	∞

;

In[]:=

EM5=ToWeightedEdgeList[M5];gM5=ToEdgeWeightedGraph[M5];EM5

Out[]=

{{{1,3},-3},{{1,4},3},{{1,7},2},{{1,8},4},{{2,3},2},{{2,4},-3},{{2,5},2},{{2,6},4},{{2,8},3},{{3,4},2},{{3,5},-2},{{3,6},-1},{{3,7},4},{{4,8},3},{{5,7},-1},{{6,7},3},{{6,8},-2}}

In[]:=

JarnikPrimTree[M5,5,ShowTreeFalse,TraceFalse];

{{{5,3},-2},{{3,1},-3},{{3,6},-1},{{6,8},-2},{{5,7},-1},{{5,2},2},{{2,4},-3}}

Total Weight-10

In[]:=

BoruvkaKruskalTree[EM5,ShowTreeFalse,TraceFalse];

{{{1,3},-3},{{2,4},-3},{{3,5},-2},{{6,8},-2},{{3,6},-1},{{5,7},-1},{{2,3},2}}

Total Weight-10

Example 8

In[]:=

M6=

∞	∞	-2	1	-1	1	∞	-1	1	∞
∞	∞	2	4	∞	∞	∞	∞	∞	-4
-2	2	∞	∞	∞	∞	∞	∞	2	∞
1	4	∞	∞	-3	-3	-2	∞	∞	3
-1	∞	∞	-3	∞	∞	∞	∞	1	∞
1	∞	∞	-3	∞	∞	∞	∞	∞	-4
∞	∞	∞	-2	∞	∞	∞	-3	-4	3
-1	∞	∞	∞	∞	∞	-3	∞	∞	∞
1	∞	2	∞	1	∞	-4	∞	∞	3
∞	-4	∞	3	∞	-4	3	∞	3	∞

;

In[]:=

EM6=ToWeightedEdgeList[M6];gM6=ToEdgeWeightedGraph[M6];EM6

Out[]=

{{{1,3},-2},{{1,4},1},{{1,5},-1},{{1,6},1},{{1,8},-1},{{1,9},1},{{2,3},2},{{2,4},4},{{2,10},-4},{{3,9},2},{{4,5},-3},{{4,6},-3},{{4,7},-2},{{4,10},3},{{5,9},1},{{6,10},-4},{{7,8},-3},{{7,9},-4},{{7,10},3},{{9,10},3}}

In[]:=

JarnikPrimTree[EM6,6,ShowTreeFalse,TraceTrue,TreeFalse];

★

Selected Edge

∞

-3

∞

★

∞

-4

{6,10}-4

-4

∞

-3

∞

★

∞

★

{10,2}-4

★

-3

∞

★

∞

★

{6,4}-3

★

-3

★

-2

∞

★

{4,5}-3

-1

★

-2

∞

★

{4,7}-2

-1

★

-3

-4

★

{7,9}-4

-1

★

-3

★

{7,8}-3

-1

★

{5,1}-1

★

-2

★

{1,3}-2

In[]:=

BoruvkaKruskalTree[EM6,ShowTreeFalse,TraceTrue,TreeFalse];

{{{2,10},-4},{{6,10},-4},{{7,9},-4},{{4,5},-3},{{4,6},-3},{{7,8},-3},{{1,3},-2},{{4,7},-2},{{1,5},-1},{{1,8},-1},{{1,4},1},{{1,6},1},{{1,9},1},{{5,9},1},{{2,3},2},{{3,9},2},{{4,10},3},{{7,10},3},{{9,10},3},{{2,4},4}}

Selected edge	Forest components
{2,10}-4	{{2,10}}
{6,10}-4	{{2,6,10}}
{7,9}-4	{{2,6,10},{7,9}}
{4,5}-3	{{2,6,10},{7,9},{4,5}}
{4,6}-3	{{2,4,5,6,10},{7,9}}
{7,8}-3	{{2,4,5,6,10},{7,8,9}}
{1,3}-2	{{2,4,5,6,10},{7,8,9},{1,3}}
{4,7}-2	{{2,4,5,6,7,8,9,10},{1,3}}
{1,5}-1	{{1,2,3,4,5,6,7,8,9,10}}

Example 9

In[]:=

M7=

∞	3	∞	-2	7	2	∞	9	∞	∞
3	∞	-2	∞	∞	3	8	5	2	∞
∞	-2	∞	∞	∞	4	∞	-2	1	∞
-2	∞	∞	∞	9	1	2	∞	7	3
7	∞	∞	9	∞	∞	-2	∞	∞	-1
2	3	4	1	∞	∞	∞	6	∞	6
∞	8	∞	2	-2	∞	∞	∞	3	∞
9	5	-2	∞	∞	6	∞	∞	1	∞
∞	2	1	7	∞	∞	3	1	∞	9
∞	∞	∞	3	-1	6	∞	∞	9	∞

;

In[]:=

EM7=ToWeightedEdgeList[M7];gM7=ToEdgeWeightedGraph[M7];EM7

Out[]=

{{{1,2},3},{{1,4},-2},{{1,5},7},{{1,6},2},{{1,8},9},{{2,3},-2},{{2,6},3},{{2,7},8},{{2,8},5},{{2,9},2},{{3,6},4},{{3,8},-2},{{3,9},1},{{4,5},9},{{4,6},1},{{4,7},2},{{4,9},7},{{4,10},3},{{5,7},-2},{{5,10},-1},{{6,8},6},{{6,10},6},{{7,9},3},{{8,9},1},{{9,10},9}}

In[]:=

JarnikPrimTree[gM7,7,SelectionRuleRandomChoice,ShowTreeTrue,SortTrue,VertexCoordinatesEllipse[6,3]]

{{{1,4},-2},{{2,3},-2},{{3,8},-2},{{3,9},1},{{4,6},1},{{4,7},2},{{5,7},-2},{{5,10},-1},{{7,9},3}}

Total Weight-2

★

Selected Edge

∞

-2

∞

★

∞

{5,7}-2

∞

★

∞

★

∞

-1

{5,10}-1

∞

★

∞

★

{4,7}2

-2

∞

★

∞

★

{1,4}-2

★

∞

★

{4,6}1

★

{7,9}3

★

{3,9}1

★

-2

★

-2

★

{3,8}-2

★

-2

★

{2,3}-2

In[]:=

BoruvkaKruskalTree[gM7,SelectionRuleRandomChoice,ShowTreeTrue,SortTrue,VertexCoordinatesEllipse[6,3]];

{{{1,2},3},{{1,4},-2},{{2,3},-2},{{3,8},-2},{{4,6},1},{{4,7},2},{{5,7},-2},{{5,10},-1},{{8,9},1}}

Total Weight-2

{{{1,4},-2},{{2,3},-2},{{3,8},-2},{{5,7},-2},{{5,10},-1},{{3,9},1},{{4,6},1},{{8,9},1},{{1,6},2},{{2,9},2},{{4,7},2},{{1,2},3},{{2,6},3},{{4,10},3},{{7,9},3},{{3,6},4},{{2,8},5},{{6,8},6},{{6,10},6},{{1,5},7},{{4,9},7},{{2,7},8},{{1,8},9},{{4,5},9},{{9,10},9}}

Selected edge	Forest components
{3,8}-2	{{3,8}}
{1,4}-2	{{3,8},{1,4}}
{2,3}-2	{{2,3,8},{1,4}}
{5,7}-2	{{2,3,8},{1,4},{5,7}}
{5,10}-1	{{2,3,8},{1,4},{5,7,10}}
{4,6}1	{{2,3,8},{1,4,6},{5,7,10}}
{8,9}1	{{2,3,8,9},{1,4,6},{5,7,10}}
{4,7}2	{{2,3,8,9},{1,4,5,6,7,10}}
{1,2}3	{{1,2,3,4,5,6,7,8,9,10}}

Strong Components, Condensation and Tarjan’s algorithm

Options

Alternatives for optional arguments of Tarjan (default value = the first alternative): -- FontSize -> 10 | Any font size,-- ItemSize -> Automatic | {2, 2, 3 , 3, 3, 14, 14, 5, 12, 2},-- SelectionRule -> First | Last | RandomChoice,-- Sort  True | False,- Spacings -> { 0.5, {1, {0.5}}} | Automatic,-- Trace  True | Reduced | False,-- TableBreaks  False | integer | list of integers > 1

Alternatives for optional arguments of Condensation: -- AspectRatio -> Automatic | as for Graphics,-- GraphLayout  Automatic | as for Graph, -- ImagePadding  10,-- ImageSize -> Automatic | as for Graphics, -- Tarjan -> False | True,--VertexLabels -> “Name” | as for Graph,-- VertexSize -> Automatic | as for Graph,-- VertexStyle -> Automatic | as for Graph.

In[]:=

Options/@{Tarjan,Condensation}//Column[#,Center,Spacings1]&

Out[]=

{FontSize10,ItemSizeAutomatic,SelectionRuleFirst,SortFalse,Spacings{0.5,{1,{0.5}}},TraceTrue,TableBreaksFalse}

{AspectRatioAutomatic,GraphLayoutAutomatic,ImagePadding10,ImageSizeAutomatic,SortFalse,TarjanTrue,VertexSizeAutomatic,VertexStyleAutomatic}

Example 10

In[]:=

E9={{1,7},{1,10},{2,4},{3,5},{4,6},{5,4},{5,6},{5,7},{5,10},{6,2},{7,10},{8,1},{9,7},{9,8},{10,3}};ME9=ToWeightedAdjacencyMatrix[E9];gE9=ToGraph[E9,DirectedEdgesTrue,GraphLayoutAutomatic,VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE9],StrongComponents[gE9],StrongComponents[ME9],StrongComponents[E9]}//Column

Out[]=

{{2,4,6},{3,5,7,10},{1},{8},{9}}

{{1},{2,4,6},{3,5,7,10},{8},{9}}

In[]:=

Tarjan[gE9,1,SelectionRuleFirst,TraceFalse]

Out[]=

{{4,6,2},{7,10,3,5},{1},{8},{9}}

In[]:=

Tarjan[gE9,1,ItemSizeAutomatic,SelectionRuleFirst,TraceTrue]

{{4,6,2},{7,10,3,5},{1},{8},{9}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	1	2	1	1	{1,7}	{1,7}	17
2	7	1	2	2	{1,7,10}	{1,7,10}	710
3	10	1	3	3	{1,7,10,3}	{1,7,10,3}	103
4	3	1	4	4	{1,7,10,3,5}	{1,7,10,3,5}	35
5	5	4	5	5	{1,7,10,3,5,4}	{1,7,10,3,5,4}	54
6	4	1	6	6	{1,7,10,3,5,4,6}	{1,7,10,3,5,4,6}	46
7	6	1	7	7	{1,7,10,3,5,4,6,2}	{1,7,10,3,5,4,6,2}	62
8	2	1	8	6	{1,7,10,3,5,4,6,2}	{1,7,10,3,5,4,6,2}	24
8	6	0	7	6	{1,7,10,3,5,4,6}	{1,7,10,3,5,4,6,2}
8	4	0	6	6	{1,7,10,3,5,4}	{1,7,10,3,5,4,6,2}
8	4	0	6	6	{1,7,10,3,5}	{1,7,10,3,5}		{4,6,2}
8	5	2	5	2	{1,7,10,3,5}	{1,7,10,3,5}	57
8	5	1	5	2	{1,7,10,3,5}	{1,7,10,3,5}	510
8	3	0	4	2	{1,7,10,3}	{1,7,10,3,5}
8	10	0	3	2	{1,7,10}	{1,7,10,3,5}
8	7	0	2	2	{1,7}	{1,7,10,3,5}
8	7	0	2	2	{1}	{1}		{7,10,3,5}
8	1	0	1	1	{}	{}		{1}
8	8	0	8	8	{}	{}		{8}
8	9	0	8	8	{}	{}		{9}

In[]:=

Tarjan[E9,1,ItemSizeAutomatic,SelectionRuleLast,TraceTrue]

{{6,2,4},{10,3,5,7},{1},{8},{9}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	1	2	1	1	{1,10}	{1,10}	110
2	10	1	2	2	{1,10,3}	{1,10,3}	103
3	3	1	3	3	{1,10,3,5}	{1,10,3,5}	35
4	5	4	4	2	{1,10,3,5}	{1,10,3,5}	510
4	5	3	4	2	{1,10,3,5,7}	{1,10,3,5,7}	57
5	7	1	5	2	{1,10,3,5,7}	{1,10,3,5,7}	710
5	5	2	4	2	{1,10,3,5}	{1,10,3,5,7}
5	5	2	4	2	{1,10,3,5,6}	{1,10,3,5,7,6}	56
6	6	1	6	6	{1,10,3,5,6,2}	{1,10,3,5,7,6,2}	62
7	2	1	7	7	{1,10,3,5,6,2,4}	{1,10,3,5,7,6,2,4}	24
8	4	1	8	6	{1,10,3,5,6,2,4}	{1,10,3,5,7,6,2,4}	46
8	2	0	7	6	{1,10,3,5,6,2}	{1,10,3,5,7,6,2,4}
8	6	0	6	6	{1,10,3,5,6}	{1,10,3,5,7,6,2,4}
8	6	0	6	6	{1,10,3,5,7}	{1,10,3,5,7}		{6,2,4}
8	5	0	4	2	{1,10,3,5}	{1,10,3,5,7}
8	3	0	3	2	{1,10,3}	{1,10,3,5,7}
8	10	0	2	2	{1,10}	{1,10,3,5,7}
8	10	0	2	2	{1}	{1}		{10,3,5,7}
8	1	0	1	1	{}	{}		{1}
8	9	1	8	8	{9,8}	{9,8}	98
9	8	0	9	9	{9}	{9}		{8}
9	9	0	8	8	{}	{}		{9}

In[]:=

Tarjan[ME9,1,ItemSizeAutomatic,SelectionRuleRandomChoice,TraceTrue]

{{6,2,4},{7,10,3,5},{1},{8},{9}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	1	2	1	1	{1,7}	{1,7}	17
2	7	1	2	2	{1,7,10}	{1,7,10}	710
3	10	1	3	3	{1,7,10,3}	{1,7,10,3}	103
4	3	1	4	4	{1,7,10,3,5}	{1,7,10,3,5}	35
5	5	4	5	5	{1,7,10,3,5,6}	{1,7,10,3,5,6}	56
6	6	1	6	6	{1,7,10,3,5,6,2}	{1,7,10,3,5,6,2}	62
7	2	1	7	7	{1,7,10,3,5,6,2,4}	{1,7,10,3,5,6,2,4}	24
8	4	1	8	6	{1,7,10,3,5,6,2,4}	{1,7,10,3,5,6,2,4}	46
8	2	0	7	6	{1,7,10,3,5,6,2}	{1,7,10,3,5,6,2,4}
8	6	0	6	6	{1,7,10,3,5,6}	{1,7,10,3,5,6,2,4}
8	6	0	6	6	{1,7,10,3,5}	{1,7,10,3,5}		{6,2,4}
8	5	2	5	2	{1,7,10,3,5}	{1,7,10,3,5}	57
8	5	1	5	2	{1,7,10,3,5}	{1,7,10,3,5}	510
8	3	0	4	2	{1,7,10,3}	{1,7,10,3,5}
8	10	0	3	2	{1,7,10}	{1,7,10,3,5}
8	7	0	2	2	{1,7}	{1,7,10,3,5}
8	7	0	2	2	{1}	{1}		{7,10,3,5}
8	1	0	1	1	{}	{}		{1}
8	9	1	8	8	{9,8}	{9,8}	98
9	8	0	9	9	{9}	{9}		{8}
9	9	0	8	8	{}	{}		{9}

In[]:=

Condensation[E9,GraphLayout"SpringEmbedding",ImageSize{300,Automatic},VertexSize0.5Small,VertexStyleRed]

Out[]=

{1{4,6,2},2{7,10,3,5},3{1},4{8},5{9}}

Example 11

In[]:=

E10={12,21,31,48,49,59,52,510,51,610,69,64,74,82,87,98,105,106,104};gE10=ToGraph[E10,GraphLayoutAutomatic,VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE10],StrongComponents[E10]}//Column

Out[]=

{{1,2},{3},{4,7,8,9},{5,6,10}}

In[]:=

SeedRandom[20!];Tarjan[E10,2,SelectionRuleRandomChoice,SortTrue,TraceReduce]

{{3},{1,2},{5,6,10},{4,7,8,9}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	2	1	1	1	{2,1}	{2,1}	21
2	1	1	2	1	{2,1}	{2,1}	12
2	2	0	1	1	{}	{}		{2,1}
2	8	1	2	2	{8,7}	{8,7}	87
3	7	1	3	3	{8,7,4}	{8,7,4}	74
4	4	2	4	4	{8,7,4,9}	{8,7,4,9}	49
5	9	1	5	2	{8,7,4,9}	{8,7,4,9}	98
5	4	1	4	2	{8,7,4}	{8,7,4,9}	48
5	8	0	2	2	{}	{}		{8,7,4,9}
5	5	1	5	5	{5,10}	{5,10}	510
6	10	2	6	5	{5,10}	{5,10}	105
6	10	1	6	5	{5,10,6}	{5,10,6}	106
7	6	1	7	6	{5,10,6}	{5,10,6}	610
7	5	0	5	5	{}	{}		{5,10,6}
7	3	0	7	7	{}	{}		{3}

In[]:=

SeedRandom[20!];Tarjan[E10,2,SelectionRuleRandomChoice];

{{2,1},{8,7,4,9},{5,10,6},{3}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	2	1	1	1	{2,1}	{2,1}	21
2	1	1	2	1	{2,1}	{2,1}	12
2	2	0	1	1	{2}	{2,1}
2	2	0	1	1	{}	{}		{2,1}
2	8	1	2	2	{8,7}	{8,7}	87
3	7	1	3	3	{8,7,4}	{8,7,4}	74
4	4	2	4	4	{8,7,4,9}	{8,7,4,9}	49
5	9	1	5	2	{8,7,4,9}	{8,7,4,9}	98
5	4	1	4	2	{8,7,4}	{8,7,4,9}
5	4	1	4	2	{8,7,4}	{8,7,4,9}	48
5	7	0	3	2	{8,7}	{8,7,4,9}
5	8	0	2	2	{8}	{8,7,4,9}
5	8	0	2	2	{}	{}		{8,7,4,9}
5	5	1	5	5	{5,10}	{5,10}	510
6	10	2	6	5	{5,10}	{5,10}	105
6	10	1	6	5	{5,10,6}	{5,10,6}	106
7	6	1	7	6	{5,10,6}	{5,10,6}	610
7	10	0	6	5	{5,10}	{5,10,6}
7	5	0	5	5	{5}	{5,10,6}
7	5	0	5	5	{}	{}		{5,10,6}
7	3	0	7	7	{}	{}		{3}

In[]:=

Condensation[E10,AspectRatio1/3,ImageSize{300,Automatic},SortTrue,VertexSizeSmall,VertexStyleRed]

Out[]=

{1{3},2{1,2},3{5,6,10},4{4,7,8,9}}

Example 12

In[]:=

E11={110,16,26,36,410,43,52,59,58,56,68,78,71,82,95,106,107,104};gE11=ToGraph[E11];Graph[E11,VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE11],StrongComponents[gE11]}//Column

Out[]=

{{2,6,8},{3},{1,4,7,10},{5,9}}

{{1,4,7,10},{2,6,8},{3},{5,9}}

In[]:=

SeedRandom[20!];Tarjan[gE11,6,SelectionRuleRandomChoice]

{{6,8,2},{9,5},{3},{1,10,7,4}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	6	1	1	1	{6,8}	{6,8}	68
2	8	1	2	2	{6,8,2}	{6,8,2}	82
3	2	1	3	1	{6,8,2}	{6,8,2}	26
3	8	0	2	1	{6,8}	{6,8,2}
3	6	0	1	1	{6}	{6,8,2}
3	6	0	1	1	{}	{}		{6,8,2}
3	9	1	3	3	{9,5}	{9,5}	95
4	5	1	4	3	{9,5}	{9,5}	59
4	9	0	3	3	{9}	{9,5}
4	9	0	3	3	{}	{}		{9,5}
4	1	1	4	4	{1,10}	{1,10}	110
5	10	2	5	5	{1,10,7}	{1,10,7}	107
6	7	1	6	4	{1,10,7}	{1,10,7}	71
6	10	1	5	4	{1,10}	{1,10,7}
6	10	1	5	4	{1,10,4}	{1,10,7,4}	104
7	4	2	7	7	{1,10,4,3}	{1,10,7,4,3}	43
8	3	0	8	8	{1,10,7,4}	{1,10,7,4}		{3}
8	4	1	7	5	{1,10,7,4}	{1,10,7,4}	410
8	7	0	6	4	{1,10,7}	{1,10,7,4}
8	10	0	5	4	{1,10}	{1,10,7,4}
8	1	0	4	4	{1}	{1,10,7,4}
8	1	0	4	4	{}	{}		{1,10,7,4}

In[]:=

SeedRandom[20!];Tarjan[gE11,6,SelectionRuleRandomChoice,TraceReduce]

{{6,8,2},{9,5},{3},{1,10,7,4}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	6	1	1	1	{6,8}	{6,8}	68
2	8	1	2	2	{6,8,2}	{6,8,2}	82
3	2	1	3	1	{6,8,2}	{6,8,2}	26
3	6	0	1	1	{}	{}		{6,8,2}
3	9	1	3	3	{9,5}	{9,5}	95
4	5	1	4	3	{9,5}	{9,5}	59
4	9	0	3	3	{}	{}		{9,5}
4	1	1	4	4	{1,10}	{1,10}	110
5	10	2	5	5	{1,10,7}	{1,10,7}	107
6	7	1	6	4	{1,10,7}	{1,10,7}	71
6	10	1	5	4	{1,10,4}	{1,10,7,4}	104
7	4	2	7	7	{1,10,4,3}	{1,10,7,4,3}	43
8	3	0	8	8	{1,10,7,4}	{1,10,7,4}		{3}
8	4	1	7	5	{1,10,7,4}	{1,10,7,4}	410
8	1	0	4	4	{}	{}		{1,10,7,4}

In[]:=

Condensation[gE11,AspectRatio1/3,ImageSize{300,Automatic},VertexSizeSmall,VertexStyleRed,ImagePadding10]

Out[]=

{1{6,8,2},2{3},3{1,10,7,4},4{5,9}}

Example 13

In[]:=

E12={{1,5},{2,4},{3,8},{4,10},{4,7},{5,4},{5,3},{5,1},{6,2},{8,9},{8,2},{8,10},{8,3},{9,3},{9,7},{9,4},{10,6}};gE12=ToGraph[E12];Graph[E12,DirectedEdgesTrue,VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE12],StrongComponents[gE12]}//Column

Out[]=

{{7},{2,4,6,10},{3,8,9},{1,5}}

{{1,5},{2,4,6,10},{3,8,9},{7}}

In[]:=

Tarjan[gE12,2,SortTrue]

{{7},{1,5},{3,8,9},{2,4,6,10}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	2	1	1	1	{2,4}	{2,4}	24
2	4	2	2	2	{2,4,7}	{2,4,7}	47
3	7	0	3	3	{2,4}	{2,4}		{7}
3	4	1	2	2	{2,4,10}	{2,4,10}	410
4	10	1	4	4	{2,4,10,6}	{2,4,10,6}	106
5	6	1	5	1	{2,4,10,6}	{2,4,10,6}	62
5	10	0	4	1	{2,4,10}	{2,4,10,6}
5	4	0	2	1	{2,4}	{2,4,10,6}
5	2	0	1	1	{2}	{2,4,10,6}
5	2	0	1	1	{}	{}		{2,4,10,6}
5	1	1	5	5	{1,5}	{1,5}	15
6	5	2	6	5	{1,5}	{1,5}	51
6	5	1	6	5	{1,5,3}	{1,5,3}	53
7	3	1	7	7	{1,5,3,8}	{1,5,3,8}	38
8	8	2	8	7	{1,5,3,8}	{1,5,3,8}	83
8	8	1	8	7	{1,5,3,8,9}	{1,5,3,8,9}	89
9	9	1	9	7	{1,5,3,8,9}	{1,5,3,8,9}	93
9	8	0	8	7	{1,5,3,8}	{1,5,3,8,9}
9	3	0	7	7	{1,5,3}	{1,5,3,8,9}
9	3	0	7	7	{1,5}	{1,5}		{3,8,9}
9	1	0	5	5	{1}	{1,5}
9	1	0	5	5	{}	{}		{1,5}

In[]:=

Condensation[gE12,AspectRatio1/3,ImageSize{300,Automatic},VertexSizeSmall,VertexStyleRed]

Out[]=

{1{7},2{4,10,6,2},3{3,8,9},4{1,5}}

Example 14

In[]:=

E13={{1,2},{1,4},{2,5},{2,10},{3,1},{3,6},{3,9},{3,10},{3,11},{4,2},{4,5},{4,6},{4,7},{4,9},{5,1},{5,6},{5,10},{6,9},{7,6},{8,10},{8,12},{9,7},{9,10},{11,4},{11,7},{11,8},{11,9},{12,7},{12,9},{12,10},{12,11}};gE13=ToGraph[E13];Graph[E13,DirectedEdgesTrue,VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE13],StrongComponents[E13]}//Column

Out[]=

{{10},{6,7,9},{1,2,4,5},{8,11,12},{3}}

{{1,2,4,5},{3},{6,7,9},{8,11,12},{10}}

In[]:=

SeedRandom[20!];Tarjan[gE13,10,SelectionRuleRandomChoice,Trace->Reduce]

{{10},{9,7,6},{5,1,2,4},{12,11,8},{3}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	10	0	1	1	{}	{}		{10}
2	5	2	2	2	{5,1}	{5,1}	51
3	1	2	3	3	{5,1,2}	{5,1,2}	12
4	2	1	4	2	{5,1,2}	{5,1,2}	25
4	1	1	3	2	{5,1,4}	{5,1,2,4}	14
5	4	5	5	5	{5,1,4,9}	{5,1,2,4,9}	49
6	9	1	6	6	{5,1,4,9,7}	{5,1,2,4,9,7}	97
7	7	1	7	7	{5,1,4,9,7,6}	{5,1,2,4,9,7,6}	76
8	6	1	8	6	{5,1,4,9,7,6}	{5,1,2,4,9,7,6}	69
8	9	0	6	6	{5,1,2,4}	{5,1,2,4}		{9,7,6}
8	4	2	5	4	{5,1,2,4}	{5,1,2,4}	42
8	4	1	5	2	{5,1,2,4}	{5,1,2,4}	45
8	5	0	2	2	{}	{}		{5,1,2,4}
8	12	1	8	8	{12,11}	{12,11}	1211
9	11	1	9	9	{12,11,8}	{12,11,8}	118
10	8	1	10	8	{12,11,8}	{12,11,8}	812
10	12	0	8	8	{}	{}		{12,11,8}
10	3	0	10	10	{}	{}		{3}

In[]:=

SeedRandom[20!];Tarjan[gE13,10,SelectionRuleRandomChoice]

{{10},{9,7,6},{5,1,2,4},{12,11,8},{3}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	10	0	1	1	{}	{}		{10}
2	5	2	2	2	{5,1}	{5,1}	51
3	1	2	3	3	{5,1,2}	{5,1,2}	12
4	2	1	4	2	{5,1,2}	{5,1,2}	25
4	1	1	3	2	{5,1}	{5,1,2}
4	1	1	3	2	{5,1,4}	{5,1,2,4}	14
5	4	5	5	5	{5,1,4,9}	{5,1,2,4,9}	49
6	9	1	6	6	{5,1,4,9,7}	{5,1,2,4,9,7}	97
7	7	1	7	7	{5,1,4,9,7,6}	{5,1,2,4,9,7,6}	76
8	6	1	8	6	{5,1,4,9,7,6}	{5,1,2,4,9,7,6}	69
8	7	0	7	6	{5,1,4,9,7}	{5,1,2,4,9,7,6}
8	9	0	6	6	{5,1,4,9}	{5,1,2,4,9,7,6}
8	9	0	6	6	{5,1,2,4}	{5,1,2,4}		{9,7,6}
8	4	2	5	4	{5,1,2,4}	{5,1,2,4}	42
8	4	1	5	2	{5,1,2,4}	{5,1,2,4}	45
8	2	0	4	2	{5,1,2}	{5,1,2,4}
8	1	0	3	2	{5,1}	{5,1,2,4}
8	5	0	2	2	{5}	{5,1,2,4}
8	5	0	2	2	{}	{}		{5,1,2,4}
8	12	1	8	8	{12,11}	{12,11}	1211
9	11	1	9	9	{12,11,8}	{12,11,8}	118
10	8	1	10	8	{12,11,8}	{12,11,8}	812
10	11	0	9	8	{12,11}	{12,11,8}
10	12	0	8	8	{12}	{12,11,8}
10	12	0	8	8	{}	{}		{12,11,8}
10	3	0	10	10	{}	{}		{3}

In[]:=

Condensation[gE13,DirectedEdgesTrue,VertexStyleRed,ImagePadding10]

Out[]=

{1{10},2{6,9,7},3{1,2,5,4},4{11,8,12},5{3}}

Example 15

In[]:=

E14={42,39,18,51,13,67,46,62,48,45,410,910,29,59,710,93,210,74,103,53,79,69,23,15,110};gE14=Graph[E14,ImageSize{300,Automatic},VertexLabels->"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

{ConnectedComponents[gE14],StrongComponents[gE14]}//Column

Out[]=

{{3,9,10},{2},{8},{1,5},{4,6,7}}

{{4,6,7},{1,5},{2},{3,9,10},{8}}

In[]:=

Tarjan[gE14,4,Spacings{1,{1,0.5}},TableBreaks{14}]

{{9,10,3},{2},{8},{5,1},{4,6,7}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	4	5	1	1	{4,2}	{4,2}	42
2	2	3	2	2	{4,2,9}	{4,2,9}	29
3	9	2	3	3	{4,2,9,10}	{4,2,9,10}	910
4	10	1	4	4	{4,2,9,10,3}	{4,2,9,10,3}	103
5	3	1	5	3	{4,2,9,10,3}	{4,2,9,10,3}	39
5	10	0	4	3	{4,2,9,10}	{4,2,9,10,3}
5	9	1	3	3	{4,2,9}	{4,2,9,10,3}
5	9	1	3	3	{4,2,9}	{4,2,9,10,3}	93
5	9	0	3	3	{4,2}	{4,2}		{9,10,3}
5	2	0	2	2	{4}	{4}		{2}
5	4	3	1	1	{4,6}	{4,6}	46
6	6	1	6	6	{4,6,7}	{4,6,7}	67
7	7	1	7	1	{4,6,7}	{4,6,7}	74
7	6	0	6	1	{4,6}	{4,6,7}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
7	4	2	1	1	{4}	{4,6,7}
7	4	2	1	1	{4,8}	{4,6,7,8}	48
8	8	0	8	8	{4,6,7}	{4,6,7}		{8}
8	6	0	6	1	{4,6}	{4,6,7}
8	4	1	1	1	{4}	{4,6,7}
8	4	1	1	1	{4,5}	{4,6,7,5}	45
9	5	1	9	9	{4,5,1}	{4,6,7,5,1}	51
10	1	1	10	9	{4,5,1}	{4,6,7,5,1}	15
10	5	0	9	9	{4,5}	{4,6,7,5,1}
10	5	0	9	9	{4,6,7}	{4,6,7}		{5,1}
10	6	0	6	1	{4,6}	{4,6,7}
10	4	0	1	1	{4}	{4,6,7}
10	4	0	1	1	{}	{}		{4,6,7}

In[]:=

Tarjan[E14,4,SortFalse,Spacings{1,{1,0.5}},TableBreaks{14}]

{{9,10,3},{2},{8},{5,1},{4,6,7}}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
1	4	5	1	1	{4,2}	{4,2}	42
2	2	3	2	2	{4,2,9}	{4,2,9}	29
3	9	2	3	3	{4,2,9,10}	{4,2,9,10}	910
4	10	1	4	4	{4,2,9,10,3}	{4,2,9,10,3}	103
5	3	1	5	3	{4,2,9,10,3}	{4,2,9,10,3}	39
5	10	0	4	3	{4,2,9,10}	{4,2,9,10,3}
5	9	1	3	3	{4,2,9}	{4,2,9,10,3}
5	9	1	3	3	{4,2,9}	{4,2,9,10,3}	93
5	9	0	3	3	{4,2}	{4,2}		{9,10,3}
5	2	0	2	2	{4}	{4}		{2}
5	4	3	1	1	{4,6}	{4,6}	46
6	6	1	6	6	{4,6,7}	{4,6,7}	67
7	7	1	7	1	{4,6,7}	{4,6,7}	74
7	6	0	6	1	{4,6}	{4,6,7}

i	x	+ d (x)	P(x)	Z(x)	ST1	ST2	e	c
7	4	2	1	1	{4}	{4,6,7}
7	4	2	1	1	{4,8}	{4,6,7,8}	48
8	8	0	8	8	{4,6,7}	{4,6,7}		{8}
8	6	0	6	1	{4,6}	{4,6,7}
8	4	1	1	1	{4}	{4,6,7}
8	4	1	1	1	{4,5}	{4,6,7,5}	45
9	5	1	9	9	{4,5,1}	{4,6,7,5,1}	51
10	1	1	10	9	{4,5,1}	{4,6,7,5,1}	15
10	5	0	9	9	{4,5}	{4,6,7,5,1}
10	5	0	9	9	{4,6,7}	{4,6,7}		{5,1}
10	6	0	6	1	{4,6}	{4,6,7}
10	4	0	1	1	{4}	{4,6,7}
10	4	0	1	1	{}	{}		{4,6,7}

In[]:=

Condensation[E14,AspectRatio1/3,DirectedEdgesTrue,ImageSize{300,Automatic},SortTrue,VertexSizeSmall,VertexStyleRed,ImagePadding10]

Out[]=

{1{2},2{8},3{1,5},4{3,9,10},5{4,6,7}}

Topological Order, TopologicalOrderTest

Options

Alternatives for optional arguments of TopologicalOrder:
-- EdgeList → True | False,
-- FontSize -> 10 | Any font size,
-- Print -> False | True,
-- SelectionRule ->First | Last | RandomChoice,
-- Sort  False | True,
-- Spacings -> {1, 1},
-- TableBreaks -> False | integer | list of integers,
-- Trace -> True | False,
-- Vertices  True | False.

Alternatives for optional arguments of TopologicalOrderTest:
-- Trace -> True | False.

In[]:=

Options[TopologicalOrder]

Out[]=

{EdgeListTrue,FontSize10,Method1,PrintFalse,SelectionRuleFirst,SortFalse,Spacings{0.5,1},TableBreaksFalse,TraceFalse,VertexListTrue}

Example 16

In[]:=

V15=Range[12];E15={14,15,110,111,112,24,210,312,412,58,512,62,63,68,71,72,78,79,710,712,89,114,118,1110,1210};ME15=ToWeightedAdjacencyMatrix[E15];gE15=ToGraph[E15];ToGraph[E15,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,12],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE15,Method1,EdgeListTrue,Spacings{0.5,1},TraceTrue]

Out[]=

{{6,7},{1,2,3},{5,11},{4,8},{9,12},{10}}

{6{2,3,8},7{1,2,8,9,10,12},1{4,5,10,11,12},2{4,10},3{12},5{8,12},11{4,8,10},4{12},8{9},12{10}}

[x]

{7}

{6,7}

{6}

{1,2,11}

{1}

★

{5,6,7,11}

{7,8}

{1,2,7,11,12}

{1}

{1,3,4,5,7}

[{6,7}]

{6{2,3,8},7{1,2,8,9,10,12}}

[x]

★

{1,2,11}

{1}

★

{5,11}

{8}

{1,2,11,12}

{1}

{1,3,4,5}

[{1,2,3}]

{1{4,5,10,11,12},2{4,10},3{12}}

[x]

★

{11}

★

{5,11}

{8}

{11,12}

★

{4,5}

[{5,11}]

{5{8,12},11{4,8,10}}

[x]

★

{8}

{12}

★

{4}

[{4,8}]

{4{12},8{9}}

[x]

★

{12}

★

[{9,12}]

{12{10}}

[x]

★

In[]:=

TopologicalOrderTest[gE15,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

In[]:=

TopologicalOrder[gE15,Method2,EdgeListTrue,Spacings{0.5,1},TableBreaks8,TraceTrue]

Out[]=

{6,7,3,1,2,5,11,4,8,12,9,10}

{6{2,3,8},7{1,2,8,9,10,12},3{12},1{4,5,10,11,12},2{4,10},5{8,12},11{4,8,10},4{12},8{9},12{10}}

[x]

{7}

{6,7}

{6}

{1,2,11}

{1}

★

{5,6,7,11}

{7,8}

{1,2,7,11,12}

{1}

{1,3,4,5,7}

[6]

{6{2,3,8}}

[x]

{7}

★

{1,2,11}

{1}

★

{5,7,11}

{7,8}

{1,2,7,11,12}

{1}

{1,3,4,5,7}

[7]

{7{1,2,8,9,10,12}}

[x]

★

{1,2,11}

{1}

★

{5,11}

{8}

{1,2,11,12}

{1}

{1,3,4,5}

[3]

{3{12}}

[x]

★

{1,2,11}

{1}

★

{5,11}

{8}

{1,2,11,12}

{1}

{1,4,5}

[1]

{1{4,5,10,11,12}}

[x]

★

{2,11}

★

{5,11}

{8}

{2,11,12}

★

{4,5}

[2]

{2{4,10}}

[x]

★

{11}

★

{5,11}

{8}

{11,12}

★

{4,5}

[5]

{5{8,12}}

[x]

★

{11}

★

{11}

{8}

{11,12}

★

{4}

[11]

{11{4,8,10}}

[x]

★

{8}

{12}

★

{4}

[4]

{4{12}}

[x]

★

{8}

{12}

★

[8]

{8{9}}

[x]

★

{12}

★

[12]

{12{10}}

[x]

★

[9]

{9{}}

[x]

★

In[]:=

TopologicalOrderTest[gE15,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

In[]:=

TopologicalOrder[gE15,Method3,EdgeListTrue,TableBreaks{9,16},TraceTrue]

Out[]=

{6,7,3,1,2,5,11,4,8,12,9,10}

{6{2,3,8},7{1,2,8,9,10,12},3{12},1{4,5,10,11,12},2{4,10},5{8,12},11{4,8,10},4{12},8{9},12{10}}

x	1	2	3	4	5	6	7	8	9	10	11	12
d - [x]	1	2	1	3	1	0	0	4	2	5	1	5
E + [6]	{6{2,3,8}}
d - [x]	1	1	0	3	1	0	0	3	2	5	1	5
E + [7]	{7{1,2,8,9,10,12}}
d - [x]	0	0	0	3	1	0	0	2	1	4	1	4
E + [3]	{3{12}}
d - [x]	0	0	0	3	1	0	0	2	1	4	1	3
E + [1]	{1{4,5,10,11,12}}
d - [x]	0	0	0	2	0	0	0	2	1	3	0	2

x	1	2	3	4	5	6	7	8	9	10	11	12
E + [2]	{2{4,10}}
d - [x]	0	0	0	1	0	0	0	2	1	2	0	2
E + [5]	{5{8,12}}
d - [x]	0	0	0	1	0	0	0	1	1	2	0	1
E + [11]	{11{4,8,10}}
d - [x]	0	0	0	0	0	0	0	0	1	1	0	1
E + [4]	{4{12}}

x	1	2	3	4	5	6	7	8	9	10	11	12
d - [x]	0	0	0	0	0	0	0	0	1	1	0	0
E + [8]	{8{9}}
d - [x]	0	0	0	0	0	0	0	0	0	1	0	0
E + [12]	{12{10}}
d - [x]	0	0	0	0	0	0	0	0	0	0	0	0
E + [9]	{9{}}
d - [x]	0	0	0	0	0	0	0	0	0	0	0	0

In[]:=

TopologicalOrderTest[gE15,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

Example 17

In[]:=

V16=Range[12];E16={12,29,43,411,52,54,56,58,510,511,512,61,63,611,74,711,81,83,86,87,812,101,102,106,109,1011,1012,112,119,122};gE16=Graph[V16,E16,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,12],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE16,Method1,TraceTrue]

Out[]=

{{5},{8,10},{6,7,12},{1,4},{3,11},{2},{9}}

{5{2,4,6,8,10,11,12},8{1,3,6,7,12},10{1,2,6,9,11,12},6{1,3,11},7{4,11},12{2},1{2},4{3,11},11{2,9},2{9}}

[x]

{6,8,10}

{1,5,10,11,12}

{4,6,8}

{5,7}

★

{5,8,10}

{8}

{5}

{2,10,11}

{5}

{4,5,6,7,10}

{5,8,10}

[{5}]

{5{2,4,6,8,10,11,12}}

[x]

{6,8,10}

{1,10,11,12}

{4,6,8}

{7}

★

{8,10}

{8}

★

{2,10,11}

★

{4,6,7,10}

{8,10}

[{8,10}]

{8{1,3,6,7,12},10{1,2,6,9,11,12}}

[x]

{6}

{1,11,12}

{4,6}

{7}

★

{2,11}

★

{4,6,7}

★

[{6,7,12}]

{6{1,3,11},7{4,11},12{2}}

[x]

★

{1,11}

{4}

★

{2,11}

★

{4}

★

[{1,4}]

{1{2},4{3,11}}

[x]

★

{11}

★

{2,11}

★

[{3,11}]

{11{2,9}}

[x]

★

{2}

★

[{2}]

{2{9}}

[x]

★

In[]:=

TopologicalOrderTest[E16,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

Example 18

In[]:=

V17=Range[12];E17={12,17,110,27,31,412,52,58,511,62,64,65,68,87,812,93,94,96,97,98,910,912,107,111,112,114,117,118,1112,127};gE17=Graph[V17,E17,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,12],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE17,Method2,Spacings{0.3,1},TraceTrue]

Out[]=

{9,3,6,5,11,1,4,2,8,10,12,7}

{9{3,4,6,7,8,10,12},3{1},6{2,4,5,8},5{2,8,11},11{1,2,4,7,8,12},1{2,7,10},4{12},2{7},8{7,12},10{7},12{7}}

[x]

{3,11}

{1,5,6,11}

{9}

{6,9,11}

{6}

{9}

{1,2,8,9,10,11,12}

{5,6,9,11}

★

{1,9}

{5}

{4,8,9,11}

[9]

{9{3,4,6,7,8,10,12}}

[x]

{3,11}

{1,5,6,11}

★

{6,11}

{6}

★

{1,2,8,10,11,12}

{5,6,11}

★

{1}

{5}

{4,8,11}

[3]

{3{1}}

[x]

{11}

{1,5,6,11}

★

{6,11}

{6}

★

{1,2,8,10,11,12}

{5,6,11}

★

{1}

{5}

{4,8,11}

[6]

{6{2,4,5,8}}

[x]

{11}

{1,5,11}

★

{11}

★

{1,2,8,10,11,12}

{5,11}

★

{1}

{5}

{4,8,11}

[5]

{5{2,8,11}}

[x]

{11}

{1,11}

★

{11}

★

{1,2,8,10,11,12}

{11}

★

{1}

★

{4,8,11}

[11]

{11{1,2,4,7,8,12}}

[x]

★

{1}

★

{1,2,8,10,12}

★

{1}

★

{4,8}

[1]

{1{2,7,10}}

[x]

★

{2,8,10,12}

★

{4,8}

[4]

{4{12}}

[x]

★

{2,8,10,12}

★

{8}

[2]

{2{7}}

[x]

★

{8,10,12}

★

{8}

[8]

{8{7,12}}

[x]

★

{10,12}

★

[10]

{10{7}}

[x]

★

{12}

★

[12]

{12{7}}

[x]

★

In[]:=

TopologicalOrderTest[gE17,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

Example 19

In[]:=

V18=Range[12];E18={15,110,23,24,26,210,212,53,65,610,72,75,76,81,83,87,94,103,104,111,112,115,116,117,118,119,1110,123,124,125};gE18=Graph[V18,E18,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,12],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE18]

Out[]=

{{11},{8,9},{1,7},{2},{6,12},{5,10},{3,4}}

{11{1,2,5,6,7,8,9,10},8{1,3,7},9{4},1{5,10},7{2,5,6},2{3,4,6,10,12},6{5,10},12{3,4,5},5{3},10{3,4}}

In[]:=

TopologicalOrderTest[gE18,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

Example 20

In[]:=

V19=Range[13];E19={13,111,29,43,412,413,52,53,59,510,511,62,64,610,76,78,82,813,102,103,118,119,1110,129,139};gE19=Graph[V19,E19,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,13],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE19]

Out[]=

{{1,5,7},{6,11},{4,8,10},{2,3,12,13},{9}}

{1{3,11},5{2,3,9,10,11},7{6,8},6{2,4,10},11{8,9,10},4{3,12,13},8{2,13},10{2,3},2{9},12{9},13{9}}

In[]:=

TopologicalOrderTest[gE19,#]&/@{%[[1,1]],%[[1,2]]}

Out[]=

{True,True}

Example 21

In[]:=

V20=Range[12];E20={{{1,2},2},{{1,6},12},{{5,2},17},{{2,3},1},{{2,8},1},{{3,1},4},{{4,3},3},{{4,6},4},{{4,8},12},{{5,1},8},{{5,4},10},{{6,2},12},{{6,3},12},{{6,7},10},{{8,7},7},{{9,6},4},{{9,10},1},{{10,11},0},{{11,12},-1},{{12,1},3}};gE20=Graph[V20,First/@E20,AspectRatio0.5,DirectedEdgesTrue,GraphLayoutAutomatic,VertexCoordinatesEllipse[2,1,12],VertexLabels"Name",VertexStyleRed,ImagePadding10]

Out[]=

In[]:=

TopologicalOrder[gE20];

Topological order doesn't exist.

Graph isn't acyclic, it contains the folloving cycles:

{{1,2},{2,3},{3,1}}

{{1,6},{6,2},{2,3},{3,1}}

Shortest Paths: DijkstraPathsTree

Options

Alternatives for optional arguments :-- “ArrowSize” -> Automatic | 0.04 | as for Graph,-- DistanceTable → True | False,-- FontSize -> 10 | as for Grid,-- GraphLayout -> Automatic | any Graph layout, -- ImageSize -> Automatic | {450, 300} | as for Graph,-- ItemSize → Automatic | {6,4,2,3,3,5,8,2} | as for Grid,-- SelectionRule → First | Last | RandomChoice, -- ShowTree -> Tree | False,-- Sort →True | False,-- Spacings -> {1,1} | Automatic | as for Grid, -- TableBreaks → False | integer | list of positive integers,-- Trace -> All | Reduce | False,-- Tree -> True | False,-- TreeEdgeStyle → {Thickness[0.005], Red} | as for EdgeStyle,-- VertexCoordinates  Automatic | Ellipse[a, b],-- VertexLabelStyle  Directive[Bold, Blue, 12] | as for Graph,-- VertexSize -> Automatic | Tiny | Small | Medium | Large | number | {“Scaled”, number},-- VertexStyle  Blue | any color specification.

In[]:=

Options[DijkstraPathsTree]

Out[]=

ArrowSizeAutomatic,DijkstraFalse,DistanceTableTrue,FontSize10,GraphLayoutAutomatic,ImagePadding10,ImageSizeAutomatic,ItemSizeAutomatic,SelectionRuleFirst,ShowTreeTrue,Spacings{0.7,0.7},SortTrue,TableBreaksFalse,TraceTrue,TreeTrue,TreeEdgeStyleThickness[0.003],

,VertexCoordinatesAutomatic,VertexLabelsName,VertexSizeAutomatic,VertexStyle

,VertexLabelStyleDirectiveBold,

,12

Example 22

In[]:=

E13={{{1,2},2},{{1,6},12},{{5,2},17},{{2,3},1},{{2,8},1},{{3,1},-4},{{9,6},4},{{4,3},3},{{4,6},4},{{4,8},12},{{5,1},8},{{5,4},10},{{6,2},12},{{6,3},12},{{6,7},10},{{8,7},7}};ME13=ToWeightedAdjacencyMatrix[E13];gE13=ToEdgeWeightedGraph[E13];ME13//MatrixForm

Out[]//MatrixForm=

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	1	∞
-4	∞	0	∞	∞	∞	∞	∞	∞
∞	∞	3	0	∞	4	∞	12	∞
8	17	∞	10	0	∞	∞	∞	∞
∞	12	12	∞	∞	0	10	∞	∞
∞	∞	∞	∞	∞	∞	0	∞	∞
∞	∞	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	4	∞	∞	0

In[]:=

Transpose@Prepend[Sort[Flatten/@E13],{"x","y","w"}]//Grid[#,DividersAll]&

Out[]=

x	1	1	2	2	3	4	4	4	5	5	5	6	6	6	8	9
y	2	6	3	8	1	3	6	8	1	2	4	2	3	7	7	6
w	2	12	1	1	-4	3	4	12	8	17	10	12	12	10	7	4

In[]:=

DijkstraPathsTree[gE13,6,VertexCoordinatesEllipse[6,3],VertexSizeSmall]

Found cycle of negative totalWeight

{{31,-4},{12,2},{23,1}}

M	x→y	w	U(x)	U(y)	U(x)+w	FromWhere	y
{6}	62	12	0	∞	12	62	2
{6,2}	63	12	0	∞	12	63	3
{6,2,3}	67	10	0	∞	10	67	7
{2,3,7}	23	1	12	12	13
{2,3,7}	28	1	12	∞	13	28	8
{3,7,8}	31	-4	12	∞	8	31	1
{8,1}	87	7	13	10	20
{1}	12	2	8	12	10	12	2
{1,2}	16	12	8	0	20
{2}	23	1	10	12	11	23	3

Example 23

In[]:=

E14={{{1,2},2},{{1,6},12},{{5,2},10},{{2,3},1},{{8,2},1},{{4,3},-3},{{4,6},4},{{4,8},2},{{5,1},10},{{5,4},10},{{6,9},-5},{{6,2},12},{{3,9},5},{{6,7},10},{{7,9},1},{{8,7},7},{{9,8},-7}};ME14=ToWeightedAdjacencyMatrix[E14];gE14=ToEdgeWeightedGraph[E14];ME14//MatrixForm

Out[]//MatrixForm=

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	∞	∞
∞	∞	0	∞	∞	∞	∞	∞	5
∞	∞	-3	0	∞	4	∞	2	∞
10	10	∞	10	0	∞	∞	∞	∞
∞	12	∞	∞	∞	0	10	∞	-5
∞	∞	∞	∞	∞	∞	0	∞	1
∞	1	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	∞	∞	-7	0

In[]:=

gE14//EdgeList

Out[]=

{12,16,52,23,82,43,46,48,51,54,69,62,39,67,79,87,98}

In[]:=

Transpose@Prepend[Sort[Flatten/@E14],{"x","y","w"}]//Grid[#,DividersAll]&

Out[]=

∞	8	2	2	9	2
8	∞	-5	-1	∞	19
2	-5	∞	-5	3	14
2	-1	-5	∞	3	-2
9	∞	3	3	∞	2
2	19	14	-2	2	∞

∞	2	2	3	2	-4	2
2	∞	∞	2	∞	3	1
2	∞	∞	-3	4	1	∞
3	2	-3	∞	1	2	4
2	∞	4	1	∞	2	∞
-4	3	1	2	2	∞	1
2	1	∞	4	∞	1	∞

∞	1	-2	4	-1	2	3
1	∞	∞	-2	4	∞	-4
-2	∞	∞	1	3	2	-2
4	-2	1	∞	-3	-2	-1
-1	4	3	-3	∞	1	4
2	∞	2	-2	1	∞	-3
3	-4	-2	-1	4	-3	∞

∞	-1	∞	-2	4	3	1	∞
-1	∞	∞	∞	4	-1	3	-1
∞	∞	∞	-3	∞	3	2	∞
-2	∞	-3	∞	∞	∞	3	3
4	4	∞	∞	∞	-4	-1	2
3	-1	3	∞	-4	∞	4	4
1	3	2	3	-1	4	∞	-4
∞	-1	∞	3	2	4	-4	∞

∞	∞	-3	3	∞	∞	2	4
∞	∞	2	-3	2	4	∞	3
-3	2	∞	2	-2	-1	4	∞
3	-3	2	∞	∞	∞	∞	3
∞	2	-2	∞	∞	∞	-1	∞
∞	4	-1	∞	∞	∞	3	-2
2	∞	4	∞	-1	3	∞	∞
4	3	∞	3	∞	-2	∞	∞

∞	∞	-2	1	-1	1	∞	-1	1	∞
∞	∞	2	4	∞	∞	∞	∞	∞	-4
-2	2	∞	∞	∞	∞	∞	∞	2	∞
1	4	∞	∞	-3	-3	-2	∞	∞	3
-1	∞	∞	-3	∞	∞	∞	∞	1	∞
1	∞	∞	-3	∞	∞	∞	∞	∞	-4
∞	∞	∞	-2	∞	∞	∞	-3	-4	3
-1	∞	∞	∞	∞	∞	-3	∞	∞	∞
1	∞	2	∞	1	∞	-4	∞	∞	3
∞	-4	∞	3	∞	-4	3	∞	3	∞

∞	3	∞	-2	7	2	∞	9	∞	∞
3	∞	-2	∞	∞	3	8	5	2	∞
∞	-2	∞	∞	∞	4	∞	-2	1	∞
-2	∞	∞	∞	9	1	2	∞	7	3
7	∞	∞	9	∞	∞	-2	∞	∞	-1
2	3	4	1	∞	∞	∞	6	∞	6
∞	8	∞	2	-2	∞	∞	∞	3	∞
9	5	-2	∞	∞	6	∞	∞	1	∞
∞	2	1	7	∞	∞	3	1	∞	9
∞	∞	∞	3	-1	6	∞	∞	9	∞

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	1	∞
-4	∞	0	∞	∞	∞	∞	∞	∞
∞	∞	3	0	∞	4	∞	12	∞
8	17	∞	10	0	∞	∞	∞	∞
∞	12	12	∞	∞	0	10	∞	∞
∞	∞	∞	∞	∞	∞	0	∞	∞
∞	∞	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	4	∞	∞	0

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	∞	∞
∞	∞	0	∞	∞	∞	∞	∞	5
∞	∞	-3	0	∞	4	∞	2	∞
10	10	∞	10	0	∞	∞	∞	∞
∞	12	∞	∞	∞	0	10	∞	-5
∞	∞	∞	∞	∞	∞	0	∞	1
∞	1	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	∞	∞	-7	0

∞	8	2	2	9	2
8	∞	-5	-1	∞	19
2	-5	∞	-5	3	14
2	-1	-5	∞	3	-2
9	∞	3	3	∞	2
2	19	14	-2	2	∞

∞	2	2	3	2	-4	2
2	∞	∞	2	∞	3	1
2	∞	∞	-3	4	1	∞
3	2	-3	∞	1	2	4
2	∞	4	1	∞	2	∞
-4	3	1	2	2	∞	1
2	1	∞	4	∞	1	∞

∞	1	-2	4	-1	2	3
1	∞	∞	-2	4	∞	-4
-2	∞	∞	1	3	2	-2
4	-2	1	∞	-3	-2	-1
-1	4	3	-3	∞	1	4
2	∞	2	-2	1	∞	-3
3	-4	-2	-1	4	-3	∞

∞	-1	∞	-2	4	3	1	∞
-1	∞	∞	∞	4	-1	3	-1
∞	∞	∞	-3	∞	3	2	∞
-2	∞	-3	∞	∞	∞	3	3
4	4	∞	∞	∞	-4	-1	2
3	-1	3	∞	-4	∞	4	4
1	3	2	3	-1	4	∞	-4
∞	-1	∞	3	2	4	-4	∞

∞	∞	-3	3	∞	∞	2	4
∞	∞	2	-3	2	4	∞	3
-3	2	∞	2	-2	-1	4	∞
3	-3	2	∞	∞	∞	∞	3
∞	2	-2	∞	∞	∞	-1	∞
∞	4	-1	∞	∞	∞	3	-2
2	∞	4	∞	-1	3	∞	∞
4	3	∞	3	∞	-2	∞	∞

∞	∞	-2	1	-1	1	∞	-1	1	∞
∞	∞	2	4	∞	∞	∞	∞	∞	-4
-2	2	∞	∞	∞	∞	∞	∞	2	∞
1	4	∞	∞	-3	-3	-2	∞	∞	3
-1	∞	∞	-3	∞	∞	∞	∞	1	∞
1	∞	∞	-3	∞	∞	∞	∞	∞	-4
∞	∞	∞	-2	∞	∞	∞	-3	-4	3
-1	∞	∞	∞	∞	∞	-3	∞	∞	∞
1	∞	2	∞	1	∞	-4	∞	∞	3
∞	-4	∞	3	∞	-4	3	∞	3	∞

∞	3	∞	-2	7	2	∞	9	∞	∞
3	∞	-2	∞	∞	3	8	5	2	∞
∞	-2	∞	∞	∞	4	∞	-2	1	∞
-2	∞	∞	∞	9	1	2	∞	7	3
7	∞	∞	9	∞	∞	-2	∞	∞	-1
2	3	4	1	∞	∞	∞	6	∞	6
∞	8	∞	2	-2	∞	∞	∞	3	∞
9	5	-2	∞	∞	6	∞	∞	1	∞
∞	2	1	7	∞	∞	3	1	∞	9
∞	∞	∞	3	-1	6	∞	∞	9	∞

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	1	∞
-4	∞	0	∞	∞	∞	∞	∞	∞
∞	∞	3	0	∞	4	∞	12	∞
8	17	∞	10	0	∞	∞	∞	∞
∞	12	12	∞	∞	0	10	∞	∞
∞	∞	∞	∞	∞	∞	0	∞	∞
∞	∞	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	4	∞	∞	0

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	∞	∞
∞	∞	0	∞	∞	∞	∞	∞	5
∞	∞	-3	0	∞	4	∞	2	∞
10	10	∞	10	0	∞	∞	∞	∞
∞	12	∞	∞	∞	0	10	∞	-5
∞	∞	∞	∞	∞	∞	0	∞	1
∞	1	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	∞	∞	-7	0

Graph Algorithms

Axiliary Definitions

EdgeListQ[E] returns True if E may be considered as the EdgeList of a directed or undirected graph in the sense of Mathematica, and False in the opposite case.​EdgeListQ[E,∞] returns True if Graph[E] is undirected graph in the sense of Mathematica and False in the opposite case.

ToEdgeList

ToWeightedEdgeList

ToWeightedAdjacencyMatrix

ToGraph

ToEdgeWeightedGraph

Random EdgeLists, Matrices and Graphs

RandomEdgeList, RandomWeightedEdgeList

RandomWeightedAdjacencyMatrix

RandomAcyclicGraph

Components

Example 1

Example 2

Minimal Spanning Tree

Options

Example 3

Example 4

Example 5

Example 6

Example 7

Example 8

Example 9

Strong Components, Condensation and Tarjan’s algorithm

Options

Example 10

Example 11

Example 12

Example 13

Example 14

Example 15

Topological Order, TopologicalOrderTest

Options

Example 16

Example 17

Example 18

Example 19

Example 20

Example 21

Shortest Paths: DijkstraPathsTree

Options

Example 22

Example 23

EdgeListQ[E]
returns True if
E
may be considered as the EdgeList of a directed or undirected graph in the sense of Mathematica, and False in the opposite case.
EdgeListQ[E,∞]
returns True if
Graph[E]
is undirected graph in the sense of Mathematica and False in the opposite case.


ToEdgeList


ToWeightedEdgeList


ToWeightedAdjacencyMatrix


ToGraph


ToEdgeWeightedGraph


RandomEdgeList, RandomWeightedEdgeList


RandomWeightedAdjacencyMatrix


RandomAcyclicGraph


∞	8	2	2	9	2
8	∞	-5	-1	∞	19
2	-5	∞	-5	3	14
2	-1	-5	∞	3	-2
9	∞	3	3	∞	2
2	19	14	-2	2	∞

∞	2	2	3	2	-4	2
2	∞	∞	2	∞	3	1
2	∞	∞	-3	4	1	∞
3	2	-3	∞	1	2	4
2	∞	4	1	∞	2	∞
-4	3	1	2	2	∞	1
2	1	∞	4	∞	1	∞

∞	1	-2	4	-1	2	3
1	∞	∞	-2	4	∞	-4
-2	∞	∞	1	3	2	-2
4	-2	1	∞	-3	-2	-1
-1	4	3	-3	∞	1	4
2	∞	2	-2	1	∞	-3
3	-4	-2	-1	4	-3	∞

∞	-1	∞	-2	4	3	1	∞
-1	∞	∞	∞	4	-1	3	-1
∞	∞	∞	-3	∞	3	2	∞
-2	∞	-3	∞	∞	∞	3	3
4	4	∞	∞	∞	-4	-1	2
3	-1	3	∞	-4	∞	4	4
1	3	2	3	-1	4	∞	-4
∞	-1	∞	3	2	4	-4	∞

∞	∞	-3	3	∞	∞	2	4
∞	∞	2	-3	2	4	∞	3
-3	2	∞	2	-2	-1	4	∞
3	-3	2	∞	∞	∞	∞	3
∞	2	-2	∞	∞	∞	-1	∞
∞	4	-1	∞	∞	∞	3	-2
2	∞	4	∞	-1	3	∞	∞
4	3	∞	3	∞	-2	∞	∞

∞	∞	-2	1	-1	1	∞	-1	1	∞
∞	∞	2	4	∞	∞	∞	∞	∞	-4
-2	2	∞	∞	∞	∞	∞	∞	2	∞
1	4	∞	∞	-3	-3	-2	∞	∞	3
-1	∞	∞	-3	∞	∞	∞	∞	1	∞
1	∞	∞	-3	∞	∞	∞	∞	∞	-4
∞	∞	∞	-2	∞	∞	∞	-3	-4	3
-1	∞	∞	∞	∞	∞	-3	∞	∞	∞
1	∞	2	∞	1	∞	-4	∞	∞	3
∞	-4	∞	3	∞	-4	3	∞	3	∞

∞	3	∞	-2	7	2	∞	9	∞	∞
3	∞	-2	∞	∞	3	8	5	2	∞
∞	-2	∞	∞	∞	4	∞	-2	1	∞
-2	∞	∞	∞	9	1	2	∞	7	3
7	∞	∞	9	∞	∞	-2	∞	∞	-1
2	3	4	1	∞	∞	∞	6	∞	6
∞	8	∞	2	-2	∞	∞	∞	3	∞
9	5	-2	∞	∞	6	∞	∞	1	∞
∞	2	1	7	∞	∞	3	1	∞	9
∞	∞	∞	3	-1	6	∞	∞	9	∞

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	1	∞
-4	∞	0	∞	∞	∞	∞	∞	∞
∞	∞	3	0	∞	4	∞	12	∞
8	17	∞	10	0	∞	∞	∞	∞
∞	12	12	∞	∞	0	10	∞	∞
∞	∞	∞	∞	∞	∞	0	∞	∞
∞	∞	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	4	∞	∞	0

0	2	∞	∞	∞	12	∞	∞	∞
∞	0	1	∞	∞	∞	∞	∞	∞
∞	∞	0	∞	∞	∞	∞	∞	5
∞	∞	-3	0	∞	4	∞	2	∞
10	10	∞	10	0	∞	∞	∞	∞
∞	12	∞	∞	∞	0	10	∞	-5
∞	∞	∞	∞	∞	∞	0	∞	1
∞	1	∞	∞	∞	∞	7	0	∞
∞	∞	∞	∞	∞	∞	∞	-7	0