(* ::Package:: *)

(*(* :Context: Walks` *)*)
(**)
(*(* :Title: Walks *)*)
(**)
(*(* :Author: Luke Collins *)*)
(**)
(*(* :Version: Mathematica 13.0 *)*)
(**)
(*(* :Package Version: 1.2 *)*)
(**)
(*(* :Keywords: *)
(*    graph theory, graph products, walks, CDC, linear algebra *)
(**)*)
(**)
(*(* :History: *)
(* Version 1.2 by Luke Collins, August 2022 *)
(* Version 1.1 by Luke Collins, March 2022 *)
(* Version 1.0 by Luke Collins, September 2021 *)
(**)*)
(**)
(*(* :Copyright: Copyright 2022 - Luke Collins *)*)
(**)
(*(* :Summary: *)
(*This package implements various graph functions related to walk matrices. *)
(**)*)
(**)


BeginPackage["Walks`"];


(* Unprotects *)
Unprotect[{MainEigenvectors,MainEigenvalues,MainEigensystem,BoldEigenvalues,Eigenvalues,Eigenvectors,
Eigensystem,Det,Tr,NullSpace,Nullity,CharacteristicPolynomial,Inverse,Times,Plus,WalkMatrix,MainCharacteristicPolynomial,
CDC,AddLoops,WalkPartition,RyserSwitch,WalkColouringFunction,Colourful,ActualColours,ColourfulWalkMatrix,
KeepNonIsomorphic,IsomorphicCDCQ,LabelVertices,UnlabelVertices,IsolatedVertices,IsolatedLoopedVertices,RemoveIsolatedVertices,
RemoveIsolatedLoopedVertices,AddIsolatedVertex,AddIsolatedLoopedVertex,IsolatedVerticesQ,IsolatedLoopedVerticesQ,PartiteSets,
AppendixStyle,CartesianProduct,DirectProduct,StrongProduct,LexicographicProduct,DefaultGraphProduct,Plus,Times,Power,
SeidelSwitch,DescendantForm,SeidelMatrix,SeidelGraph,IdentifyVertices,AddPendents,AddDominatingVertex,FreshLabels,AntipodalVertices,
VertexDrag}];


MainEigenvectors::usage="\!\(MainEigenvectors[\*StyleBox[\"g\", \"TI\"]]\) gives a list of the main eigenvectors of the adjacency matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(MainEigenvectors[\*StyleBox[\"m\", \"TI\"]]\) gives a list of the main eigenvectors of the square matrix \!\(\*StyleBox[\"m\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) An eigenvector \!\(\*StyleBox[\"v\", \"TI\"]\) of a square matrix \!\(\*StyleBox[\"m\", \"TI\"]\) is said to be \!\(\*StyleBox[\"main\", FontSlant->Italic]\) if it is not orthogonal to the all ones vector \!\(\*StyleBox[\"j=(1,...,1)\", \"TI\"], i.e., if \!\(\*StyleBox[\"v.j\[NotEqual]0\", \"TI\"].\)\)";


MainEigenvalues::usage="\!\(MainEigenvalues[\*StyleBox[\"g\", \"TI\"]]\) gives a list of the main eigenvalues of the adjacency matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(MainEigenvalues[\*StyleBox[\"m\", \"TI\"]]\) gives a list of the main eigenvalues of the square matrix \!\(\*StyleBox[\"m\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) An eigenvalue \!\(\*StyleBox[\"\[Lambda]\", \"TI\"]\) of a square matrix \!\(\*StyleBox[\"m\", \"TI\"]\) is said to be \!\(\*StyleBox[\"main\", FontSlant->Italic]\) if its corresponding eigenvector \!\(\*StyleBox[\"v\", \"TI\"]\) is not orthogonal to the all ones vector \!\(\*StyleBox[\"j=(1,...,1)\", \"TI\"], i.e., if \!\(\*StyleBox[\"v.j\[NotEqual]0\", \"TI\"].\)\)";


MainEigensystem::usage="\!\(MainEigensystem[\*StyleBox[\"g\", \"TI\"]]\) gives a list \!\(\*StyleBox[\"{values, vectors}\", \"TI\"]\) of the main eigenvalues and eigenvectors of the adjacency matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(MainEigenvalues[\*StyleBox[\"m\", \"TI\"]]\) gives a list of the main eigenvalues and eigenvectors of the square matrix \!\(\*StyleBox[\"m\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) An eigenvalue \!\(\*StyleBox[\"\[Lambda]\", \"TI\"]\) of a square matrix \!\(\*StyleBox[\"m\", \"TI\"]\) is said to be \!\(\*StyleBox[\"main\", FontSlant->Italic]\) if its corresponding eigenvector \!\(\*StyleBox[\"v\", \"TI\"]\) is not orthogonal to the all ones vector \!\(\*StyleBox[\"j=(1,...,1)\", \"TI\"], i.e., if \!\(\*StyleBox[\"v.j\[NotEqual]0\", \"TI\"].\)\)";


BoldEigenvalues::usage="\!\(BoldEigenvalues[\*StyleBox[\"g\", \"TI\"]]\) gives a list of the eigenvalues of the graph object or square matrix \!\(\*StyleBox[\"g\", \"TI\"]\), with main eigenvalues shown in \!\(\*StyleBox[\"bold\", Bold]\).
Eigenvalues which are not easily expressed as radicals are rounded to two decimal places, for nice presentation.
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) An eigenvalue \!\(\*StyleBox[\"\[Lambda]\", \"TI\"]\) of a square matrix \!\(\*StyleBox[\"m\", \"TI\"]\) is said to be \!\(\*StyleBox[\"main\", FontSlant->Italic]\) if its corresponding eigenvector \!\(\*StyleBox[\"v\", \"TI\"]\) is not orthogonal to the all ones vector \!\(\*StyleBox[\"j=(1,...,1)\", \"TI\"], i.e., if \!\(\*StyleBox[\"v.j\[NotEqual]0\", \"TI\"].\)\)";


Nullity::usage="\!\(Nullity[\*StyleBox[\"g\", \"TI\"]]\) gives the dimension of the null space of the adjacency matrix of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(Nullity[\*StyleBox[\"m\", \"TI\"]]\) gives the dimension of the null space of the matrix \!\(\*StyleBox[\"m\", \"TI\"]\).";


WalkMatrix::usage="\!\(WalkMatrix[\*StyleBox[\"g\", \"TI\"]]\) gives the walk matrix corresponding to the graph object (or adjacency matrix) \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(WalkMatrix[\*StyleBox[\"g, k\", \"TI\"]]\) gives the \!\(\*StyleBox[\"k\", \"TI\"]\)-walk matrix corresponding to the graph object (or adjacency matrix) \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) The \!\(\*StyleBox[\"k\", \"TI\"]\)-walk matrix of a graph \!\(\*StyleBox[\"g\", \"TI\"]\) on \!\(\*StyleBox[\"n\", \"TI\"]\) vertices is the \!\(\*StyleBox[\"n\[Times]k\", \"TI\"]\) matrix \!\((\*SubscriptBox[StyleBox[\"w\", \"TI\"],StyleBox[\"ij\", \"TI\"]])\), where \!\(\*SubscriptBox[StyleBox[\"w\", \"TI\"],StyleBox[\"ij\", \"TI\"]]\) is the number of distinct walks of length \!\(\*StyleBox[\"j\", \"TI\"]\), starting from the \!\(\*StyleBox[\"i\", \"TI\"]\)th vertex. 
The walk matrix of \!\(\*StyleBox[\"g\", \"TI\"]\) is simply the \!\(\*StyleBox[\"k\", \"TI\"]\)-walk matrix where \!\(\*StyleBox[\"k\", \"TI\"]\) is as large as possible yet the columns are still linearly independent.";


MainCharacteristicPolynomial::usage="\!\(MainCharacteristicPolynomial[\*StyleBox[\"g, x\", \"TI\"]]\) gives a monic polynomial whose roots are precisely the main eigenvalues of the graph object (or adjacency matrix) \!\(\*StyleBox[\"g\", \"TI\"]\), each with multiplicity \!\(\*StyleBox[\"1\", \"T\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) An eigenvalue \!\(\*StyleBox[\"\[Lambda]\", \"TI\"]\) of a square matrix \!\(\*StyleBox[\"m\", \"TI\"]\) is said to be \!\(\*StyleBox[\"main\", FontSlant->Italic]\) if its corresponding eigenvector \!\(\*StyleBox[\"v\", \"TI\"]\) is not orthogonal to the all ones vector \!\(\*StyleBox[\"j=(1,...,1)\", \"TI\"], i.e., if \!\(\*StyleBox[\"v.j\[NotEqual]0\", \"TI\"].\)\)";


CDC::usage="\!\(CDC[\*StyleBox[\"g\", \"TI\"]]\) gives the canonical double covering of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) The canonical double cover of an \!\(\*StyleBox[\"n\", \"TI\"]\)-vertex graph \!\(\*StyleBox[\"g\", \"TI\"]\) on the vertex set \!\(\*StyleBox[\"{1,...,n}\", \"TI\"]\) is a \!\(\*StyleBox[\"2n\", \"TI\"]\)-vertex graph with vertices \!\(\*StyleBox[\"{1,...,n,1',...,n'}\", \"TI\"]\) with edges \!\(\*StyleBox[\"u\[UndirectedEdge]v'\", \"TI\"]\) for each edge \!\(\*StyleBox[\"u\[UndirectedEdge]v\", \"TI\"]\) in the original graph \!\(\*StyleBox[\"g\", \"TI\"]\).";


AddLoops::usage="\!\(AddLoops[\*StyleBox[\"g\", \"TI\"]]\) adds a loop at each vertex of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(AddLoops[\*StyleBox[\"g,vertices\", \"TI\"]]\) adds a loop at each vertex specified in list of \!\(\*StyleBox[\"vertices\", \"TI\"]\) to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


WalkPartition::usage="\!\(WalkPartition[\*StyleBox[\"g\", \"TI\"]]\) partitions the vertex set of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), so that vertices in the same set have the same number of walks (of any length).";


WalkDimension::usage="\!\(WalkDimension[\*StyleBox[\"g\", \"TI\"]]\) returns the dimension of the main eigenspace associated with the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).\nThis is the same as the number of columns of the walk matrix \!\(WalkMatrix[\*StyleBox[\"g\", \"TI\"]]\)."


RyserSwitch::usage="\!\(RyserSwitch[\*StyleBox[\"g,u,v,x,y\", \"TI\"]]\) performs a Ryser switch on the edges \!\(\*StyleBox[\"u\[UndirectedEdge]v\", \"TI\"]\), \!\(\*StyleBox[\"x\[UndirectedEdge]y\", \"TI\"]\) in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) Given a graph \!\(\*StyleBox[\"g\", \"TI\"]\) and four vertices \!\(\*StyleBox[\"u\", \"TI\"]\), \!\(\*StyleBox[\"v\", \"TI\"]\), \!\(\*StyleBox[\"x\", \"TI\"]\), \!\(\*StyleBox[\"y\", \"TI\"]\) such that:
   (i) all of \!\(\*StyleBox[\"u\", \"TI\"]\), \!\(\*StyleBox[\"v\", \"TI\"]\), \!\(\*StyleBox[\"x\", \"TI\"]\), \!\(\*StyleBox[\"y\", \"TI\"]\) are distinct,
   (ii) \!\(\*StyleBox[\"u\[UndirectedEdge]v\", \"TI\"]\), \!\(\*StyleBox[\"x\[UndirectedEdge]y\", \"TI\"]\) are edges in \!\(\*StyleBox[\"g\", \"TI\"]\),
   (iii) \!\(\*StyleBox[\"u\[UndirectedEdge]x\", \"TI\"]\), \!\(\*StyleBox[\"v\[UndirectedEdge]y\", \"TI\"]\) are not edges in \!\(\*StyleBox[\"g\", \"TI\"]\),
the Ryser switch on \!\(\*StyleBox[\"u\[UndirectedEdge]v\", \"TI\"]\), \!\(\*StyleBox[\"x\[UndirectedEdge]y\", \"TI\"]\) in \!\(\*StyleBox[\"g\", \"TI\"]\) replaces the edges \!\(\*StyleBox[\"u\[UndirectedEdge]v\", \"TI\"]\) and \!\(\*StyleBox[\"x\[UndirectedEdge]y\", \"TI\"]\) with the edges \!\(\*StyleBox[\"u\[UndirectedEdge]x\", \"TI\"]\) and \!\(\*StyleBox[\"v\[UndirectedEdge]y\", \"TI\"]\).";


WalkColouringFunction::usage="\!\(WalkColouringFunction[\*StyleBox[\"g\", \"TI\"]]\) associates a colour (natural number) with each vertex of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), so that vertices receiving the same colour have the same number of walks (of any length).";


Colourful::usage="\!\(Colourful[\*StyleBox[\"g\", \"TI\"]]\) colours each vertex of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), so that vertices receiving the same colour have the same number of walks (of any length).
\!\(Colourful[\*StyleBox[\"g,\[Chi]\", \"TI\"]]\) colours each vertex of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), according to the colouring association \!\(\*StyleBox[\"\[Chi]:V(g)\[RightArrow]\[DoubleStruckCapitalN]\", \"TI\"]\)  (or \!\(\*StyleBox[\"\[Chi]:V(g)\[RightArrow]RGB\", \"TI\"]\)).
\!\((\*StyleBox[\"Warning: If \[GreaterEqual]10 colours are required, the extra colours will be randomly generated and might result in similar looking colours for differently coloured vertices. In that case, run the command multiple times to be safe.\",FontSize->Small])\)";


ActualColours::usage="\!\(ActualColours[\*StyleBox[\"\[Chi]\", \"TI\"]]\) changes the colouring association \!\(\*StyleBox[\"\[Chi]:A\[RightArrow]\[DoubleStruckCapitalN]\", \"TI\"]\) into a function which returns actual colour objects.
\!\((\*StyleBox[\"Warning: If \[GreaterEqual]10 colours are required, the extra colours will be randomly generated and might result in similar looking colours for differently coloured vertices. In that case, run the command multiple times to be safe.\",FontSize->Small])\)";


ColourfulWalkMatrix::usage="\!\(ColourfulWalkMatrix[\*StyleBox[\"g\", \"TI\"]]\) gives the walk matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with coloured rows, where identical rows receive the same colour.
\!\(ColourfulWalkMatrix[\*StyleBox[\"g, k\", \"TI\"]]\) gives the \!\(\*StyleBox[\"k\", \"TI\"]\)-walk matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with coloured rows, where identical rows receive the same colour.
\!\(ColourfulWalkMatrix[\*StyleBox[\"g, k, \[Chi]\", \"TI\"]]\) gives the \!\(\*StyleBox[\"k\", \"TI\"]\)-walk matrix corresponding to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), colouring the rows according to the colouring function colouring association \!\(\*StyleBox[\"\[Chi]:V(g)\[RightArrow]\[DoubleStruckCapitalN]\", \"TI\"]\)  (or \!\(\*StyleBox[\"\[Chi]:V(g)\[RightArrow]RGB\", \"TI\"]\)).
\!\((\*StyleBox[\"Warning: If \[GreaterEqual]10 colours are required, the extra colours will be randomly generated and might result in similar looking colours for differently coloured rows. In that case, run the command multiple times to be safe.\",FontSize->Small])\)";


KeepNonIsomorphic::usage="\!\(KeepNonIsomorphic[\*StyleBox[\"list\", \"TI\"]]\) removes any graphs which are isomorphic, keeping only one representative in the list.";


IsomorphicCDCQ::usage="\!\(IsomorphicCDCQ[\*StyleBox[\"\!\(\*SubscriptBox[\(g\), \(1\)]\),\!\(\*SubscriptBox[\(g\), \(2\)]\)\", \"TI\"]]\) yields True if the graphs \!\(\*StyleBox[\"\!\(\*SubscriptBox[\(g\), \(1\)]\)\", \"TI\"]\) and \!\(\*StyleBox[\"\!\(\*SubscriptBox[\(g\), \(2\)]\)\", \"TI\"]\) have isomorphic CDCs, and False otherwise.";


LabelVertices::usage="\!\(LabelVertices[\*StyleBox[\"g\", \"TI\"]]\) displays the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with labeled vertices.";


UnlabelVertices::usage="\!\(UnlabelVertices[\*StyleBox[\"g\", \"TI\"]]\) returns the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) without any vertex labels."


IsolatedVertices::usage="\!\(IsolatedVertices[\*StyleBox[\"g\", \"TI\"]]\) returns the list of isolated vertices in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\)."


IsolatedLoopedVertices::usage="\!\(IsolatedLoopedVertices[\*StyleBox[\"g\", \"TI\"]]\) returns the list of isolated looped vertices in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\)."


RemoveIsolatedVertices::usage="\!\(RemoveIsolatedVertices[\*StyleBox[\"g\", \"TI\"]]\) returns the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with any isolated vertices removed."


RemoveIsolatedLoopedVertices::usage="\!\(RemoveIsolatedLoopedVertices[\*StyleBox[\"g\", \"TI\"]]\) returns the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with any isolated looped vertices removed."


AddIsolatedVertex::usage="\!\(AddIsolatedVertex[\*StyleBox[\"g\", \"TI\"]]\) adds an isolated vertex to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(AddIsolatedVertex[\*StyleBox[\"g,n\", \"TI\"]]\) adds \!\(\*StyleBox[\"n\", \"TI\"]\) isolated vertices to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


AddIsolatedLoopedVertex::usage="\!\(AddIsolatedLoopedVertex[\*StyleBox[\"g\", \"TI\"]]\) adds an isolated looped vertex to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(AddIsolatedLoopedVertex[\*StyleBox[\"g,n\", \"TI\"]]\) adds \!\(\*StyleBox[\"n\", \"TI\"]\) isolated looped vertices to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


IsolatedVerticesQ::usage="\!\(IsolatedVerticesQ[\*StyleBox[\"g\", \"TI\"]]\) yields True if the graph \!\(\*StyleBox[\"g\", \"TI\"]\) contains any isolated vertices, and False otherwise.";


IsolatedLoopedVerticesQ::usage="\!\(IsolatedVerticesQ[\*StyleBox[\"g\", \"TI\"]]\) yields True if the graph \!\(\*StyleBox[\"g\", \"TI\"]\) contains any isolated looped vertices, and False otherwise.";


PartiteSets::usage="\!\(PartiteSets[\*StyleBox[\"g\", \"TI\"]]\) returns a list containing the partite sets of the bipartite graph \!\(\*StyleBox[\"g\", \"TI\"]\).\n(Note that the parite sets are not uniquely determined if \!\(\*StyleBox[\"g\", \"TI\"]\) is disconnected.)"


AppendixStyle::usage="Graph style for dissertation appendix, optional argument is vertex size."


CartesianProduct::usage="\!\(Cartesian[\*StyleBox[\"g,h\", \"TI\"]]\) gives the Cartesian product \!\(\*RowBox[{StyleBox[\"g\", \"TI\"], \"\[EmptySquare]\", StyleBox[\"h\", \"TI\"]}]\) of the graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\).";
DirectProduct::usage="\!\(DirectProduct[\*StyleBox[\"g,h\", \"TI\"]]\) gives the direct product \!\(\*RowBox[{StyleBox[\"g\", \"TI\"], \"\[Times]\", StyleBox[\"h\", \"TI\"]}]\) of the graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\).";
StrongProduct::usage="\!\(StrongProduct[\*StyleBox[\"g,h\", \"TI\"]]\) gives the strong product \!\(\*RowBox[{StyleBox[\"g\", \"TI\"],OverlayBox[List[\"\\\"\\[EmptySquare]\\\"\", \"\\\"\\\\!\\\\(\\\\*AdjustmentBox[\\\\\\\"\\[Times]\\\\\\\",BoxBaselineShift->-0.15]\\\\)\\\"\"]],StyleBox[\"h\", \"TI\"]}]\) of the graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\).";
LexicographicProduct::usage="\!\(LexicographicProduct[\*StyleBox[\"g,h\", \"TI\"]]\) gives the lexicographic product \!\(\*RowBox[{StyleBox[\"g\", \"TI\"], \"\[EmptySmallCircle]\", StyleBox[\"h\", \"TI\"]}]\) of the graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\).";
DefaultGraphProduct::usage="DefaultGraphProduct[] displays on screen the definition of juxtaposition for graph objects, i.e., the meaning of the product \!\(\*StyleBox[\"g h\", \"TI\"]\) for graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\) (and by extension, other algebraic expressions such as \!\(\*RowBox[{SuperscriptBox[StyleBox[\"g\", \"TI\"],2], \"+\", 1}]\)).\nDefaultGraphProduct[\!\(\*StyleBox[\"\\\"\!\(\*StyleBox[\\\"product\\\", \\\"TI\\\"]\)\\\"\",ShowStringCharacters->True]\)] sets the meaning of the product \!\(\*StyleBox[\"g h\", \"TI\"]\) for graph objects \!\(\*StyleBox[\"g\", \"TI\"]\) and \!\(\*StyleBox[\"h\", \"TI\"]\) to the specified product.\n(Options for \!\(\*StyleBox[\"\\\"\!\(\*StyleBox[\\\"product\\\", \\\"TI\\\"]\)\\\"\",ShowStringCharacters->True]\) include \"Cartesian\", \"Direct\" and \"Strong\").";


SeidelSwitch::usage="\!\(SeidelSwitch[\*StyleBox[\"g,U\", \"TI\"]]\) performs a Seidel switch on the graph \!\(\*StyleBox[\"g\", \"TI\"]\) with respect to the subset \!\(\*StyleBox[\"U\", \"TI\"]\) of the vertex set.
\!\(\*StyleBox[\"Note: \", FontWeight->Bold]\) Given a graph \!\(\*StyleBox[\"g\", \"TI\"]\) and a subset \!\(\*StyleBox[\"U\", \"TI\"]\) of \!\(\*StyleBox[\"V(G)\", \"TI\"]\), the Seidel switch on \!\(\*StyleBox[\"U\", \"TI\"]\) interchanges all edges between \!\(\*StyleBox[\"U\", \"TI\"]\) and \!\(\*StyleBox[\"V(G)\\\\U\", \"TI\"]\) with the non-edges between \!\(\*StyleBox[\"U\", \"TI\"]\) and \!\(\*StyleBox[\"V(G)\\\\U\", \"TI\"]\).";


DescendantForm::usage="\!\(DescendantForm[\*StyleBox[\"g\", \"TI\"]]\) gives a Seidel equivalent form of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), having an isolated vertex.
\!\(DescendantForm[\*StyleBox[\"g, v\", \"TI\"]]\) gives a Seidel equivalent form of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) with vertex \!\(\*StyleBox[\"v\", \"TI\"]\) being isolated.";


SeidelMatrix::usage="\!\(SeidelMatrix[\*StyleBox[\"g\", \"TI\"]]\) gives the Seidel matrix of the simple graph object \!\(\*StyleBox[\"g\", \"TI\"]\), i.e., its \!\(\*StyleBox[\"(0,1,-1)\", \"TI\"]\)-adjacency matrix.";


SeidelGraph::usage="\!\(SeidelGraph[\*StyleBox[\"s\", \"TI\"]]\) gives the graph object corresponding to the Seidel matrix \!\(\*StyleBox[\"m\", \"TI\"]\).";


IdentifyVertices::usage="\!\(IdentifyVertices[\*StyleBox[\"g, {\!\(\*SubscriptBox[\(v\), \(1\)]\),\!\(\*SubscriptBox[\(v\), \(2\)]\)}\", \"TI\"]]\) identifies the vertices \!\(\*SubscriptBox[\(v\), \(1\)]\) and \!\(\*SubscriptBox[\(v\), \(2\)]\) as equivalent in the the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(Identify[\*StyleBox[\"g, {\!\(\*SubscriptBox[\(v\), \(1\)]\),...},  {\!\(\*SubscriptBox[\(v\), \(2\)]\),...}, ...\", \"TI\"]]\) identifies all the vertices in the first list as equivalent to each other, those in the second list, and so on, in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


AddPendents::usage="\!\(AddPendents[\*StyleBox[\"g\", \"TI\"]]\) adds a pendent edge at each vertex of the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(AddPendents[\*StyleBox[\"g,vertices\", \"TI\"]]\) adds a pendent edge at each vertex specified in list of \!\(\*StyleBox[\"vertices\", \"TI\"]\) to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


AddDominatingVertex::usage="\!\(AddDominatingVertex[\*StyleBox[\"g\", \"TI\"]]\) adds a dominating vertex to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).
\!\(AddDominatingVertex[\*StyleBox[\"g,n\", \"TI\"]]\) adds \!\(\*StyleBox[\"n\", \"TI\"]\) dominating vertices to the graph object \!\(\*StyleBox[\"g\", \"TI\"]\).";


FreshLabels::usage="\!\(FreshLabels[\*StyleBox[\"g\", \"TI\"]]\) relabels the vertices in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) using 1, 2,....";


AntipodalVertices::usage="\!\(AntipodalVertices[\*StyleBox[\"g\", \"TI\"]]\) returns a list of all the pairs of vertices in the graph object \!\(\*StyleBox[\"g\", \"TI\"]\) which are antipodal, i.e., as far from each other as possible.";


VertexDrag::usage="\!\(VertexDrag[\*StyleBox[\"g\", \"TI\"]]\) returns the graph object \!\(\*StyleBox[\"g\", \"TI\"]\), with vertices which can be clicked and dragged.";


Begin["`Private`"]


maineigensystem[g_Graph]:=Select[((Plus@@#&)@*(Sum[Transpose[{v}] . {v},{v,#}]&)@*Orthogonalize)/@Map[#[[2]]&,GroupBy[Transpose@Eigensystem[g],First],{2}],Plus@@#!=0&];


MainEigenvectors[g_Graph] :=Values[maineigensystem[g]];
MainEigenvectors[l_List]:=MainEigenvectors[AdjacencyGraph[l]];


MainEigenvalues[g_Graph]:=Module[{A=AdjacencyMatrix[g],eigs,vecs,i,main={}},
					{eigs,vecs}=Eigensystem[A];
					For[i=1,i<=Length[eigs],i++,
						If[Plus@@vecs[[i]]!=0,AppendTo[main,eigs[[i]]]]];
					main];
MainEigenvalues[l_List]:=MainEigenvalues[AdjacencyGraph[l]];


BoldEigenvalues[g_Graph]:=Module[{main=MainEigenvalues[g]},If[Head[#[[1]]]===Root,DecimalForm[N[#],{Infinity,2}],#]&/@((If[MemberQ[main,#],Style[#,Bold],Style[#]]&)/@Eigenvalues[g])];
BoldEigenvalues[l_List]:=BoldEigenvalues[AdjacencyGraph[l]];


MainEigensystem[g_Graph]:={Keys[#],Values[#]}&@maineigensystem[g]; 
MainEigensystem[l_List]:=MainEigensystem[AdjacencyGraph[l]];


WalkMatrix[X_, k_] := Module[{A=If[GraphQ[X], AdjacencyMatrix[X], X]},
						Transpose @ Prepend[Table[MatrixPower[A,i] . Table[1,{j, Length[A]}],{i,k-1}],Table[1,{j, Length[A]}]]
					  ];	  
WalkMatrix[X_] := Module[{k=1},
					While[Nullity[WalkMatrix[X,k]]==0,k++];
					WalkMatrix[X,k-1]
				 ];


MainCharacteristicPolynomial[g_, var_] := Simplify[Expand[Product[(var-i),{i,MainEigenvalues[g]}]]];


Eigenvalues[g_Graph,o___] := Eigenvalues[Normal[AdjacencyMatrix[g]],o];
Eigenvectors[g_Graph,o___] := Eigenvectors[Normal[AdjacencyMatrix[g]],o];
Eigensystem[g_Graph,o___] := Eigensystem[Normal[AdjacencyMatrix[g]],o];
Det[g_Graph,o___] := Det[Normal[AdjacencyMatrix[g]],o];
Tr[g_Graph,o___] := Tr[Normal[AdjacencyMatrix[g]],o];
NullSpace[g_Graph,o___] := NullSpace[Normal[AdjacencyMatrix[g]],o];
Nullity[X_] := Length[NullSpace[X]];
CharacteristicPolynomial[g_Graph,var_] := CharacteristicPolynomial[Normal[AdjacencyMatrix[g]],var];
Inverse[g_Graph,o___] := Inverse[Normal[AdjacencyMatrix[g]],o];


CDC[g_Graph]:=DirectProduct[g,CompleteGraph[2]];
(*Module[{A=If[GraphQ[X], AdjacencyMatrix[X], X]},
			AdjacencyGraph[Join[Transpose[Join[Table[0,{i,Length[A]},{i,Length[A]}],
			Transpose[A]]],Transpose[Join[Transpose[A],Table[0,{i,Length[A]},{i,Length[A]}]]]],
			VertexLabels->Table[\[Piecewise]	i->i	i<=Length[A]
i->ToString[i-Length[A]]<>"'"	True

,{i,2Length[A]}]]
		];*)


AddLoops::error="`2` is not a subset of the vertices of `1`";
AddLoops[g_Graph,l_List]:=Module[{newG=g,i=1},
If[SubsetQ[VertexList[g],l],
Do[newG=EdgeAdd[newG,v\[UndirectedEdge]v],{v,l}];newG,Message[AddLoops::error,g,l]]];
AddLoops[g_Graph]:=AddLoops[g,VertexList[g]];


WalkPartition[g_Graph]:=GatherBy[VertexList[g],WalkMatrix[g][[#]]&];


WalkDimension[X_]:=Module[{k=1},
					While[Nullity[WalkMatrix[X,k]]==0,k++];
					k-1];


RyserSwitch::rysererror="It is not possible to perform Ryser switching in the graph `1` on edges `2` and `3`.";
RyserSwitch[g_Graph,u_,v_,x_,y_]:=
	If[UnsameQ[u,v,x,y]&&
	EdgeCount[g,u\[UndirectedEdge]v]==EdgeCount[g,x\[UndirectedEdge]y]==1&&
	EdgeCount[g,u\[UndirectedEdge]x]==EdgeCount[g,v\[UndirectedEdge]y]==0,
	EdgeAdd[EdgeDelete[g,{u\[UndirectedEdge]v,x\[UndirectedEdge]y}],{u<->x,v<->y}],
	Message[RyserSwitch::rysererror,g,u\[UndirectedEdge]v,x\[UndirectedEdge]y]];


WalkColouringFunction::invalidType="Expected graph object, instead found `1`.";
WalkColouringFunction[g_Graph]:=Association[#[[1]]->#[[2]]&/@Sort[Flatten[MapIndexed[Function[{x,y},{#,y[[1]]}&/@x],
GatherBy[VertexList[g],WalkMatrix[g][[Position[VertexList[g],#][[1,1]]]]&]],1]]];
WalkColouringFunction[l_List]:=WalkColouringFunction/@l;
WalkColouringFunction[default_]:=Message[WalkColouringFunction::invalidType,default];


ActualColours[\[Chi]_Association]:=Module[{colours={Red,Blue,Green,Yellow,Orange,
	Purple,Cyan,Magenta,White,Black}},
(Association[Table[j->\!\(\*
TagBox[GridBox[{
{"\[Piecewise]", GridBox[{
{
RowBox[{
RowBox[{"colours", "[", 
RowBox[{"[", "j", "]"}], "]"}], " "}], 
RowBox[{"j", "<=", "10"}]},
{
RowBox[{"RandomColor", "[", "]"}], "True"}
},
AllowedDimensions->{2, Automatic},
Editable->True,
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.84]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}},
Selectable->True]}
},
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.35]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}],
"Piecewise",
DeleteWithContents->True,
Editable->False,
SelectWithContents->True,
Selectable->False,
StripWrapperBoxes->True]\),{j,Max[\[Chi]]}]]/@\[Chi])//Simplify];


Colourful::invalidType="Expected graph object, instead found `1`.";
Colourful[g_Graph,\[Chi]Arg_Association:(Association[]),o___]:=Module[{colours={Red,Blue,Green,Yellow,Orange,
	Purple,Cyan,Magenta,White,Black},\[Chi],colourFunction},
	If[\[Chi]Arg==Association[],\[Chi]=WalkColouringFunction[g],\[Chi]=\[Chi]Arg];
	If[Head[\[Chi][First[VertexList[g]]]]==Integer,colourFunction=(Association[Table[j->\!\(\*
TagBox[GridBox[{
{"\[Piecewise]", GridBox[{
{
RowBox[{
RowBox[{"colours", "[", 
RowBox[{"[", "j", "]"}], "]"}], " "}], 
RowBox[{"j", "<=", "10"}]},
{
RowBox[{"RandomColor", "[", "]"}], "True"}
},
AllowedDimensions->{2, Automatic},
Editable->True,
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.84]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}},
Selectable->True]}
},
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.35]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}],
"Piecewise",
DeleteWithContents->True,
Editable->False,
SelectWithContents->True,
Selectable->False,
StripWrapperBoxes->True]\),{j,Max[\[Chi]/@VertexList[g]]}]]@*\[Chi]),colourFunction=\[Chi]];
    Graph[g,VertexStyle->Table[v->colourFunction[v],{v,VertexList[g]}],o]];
Colourful[l_List,\[Chi]Arg_Association:(Association[]),o___]:=Colourful[#,\[Chi]Arg,o]&/@l;
Colourful[default_,o___]:=Message[Colourful::invalidType,default];


ColourfulWalkMatrix[g_Graph,k_Integer:-1,\[Chi]Arg_Association:(Association[])]:=Module[{colours={Red,Blue,Green,Yellow,Orange,
	Purple,Cyan,Magenta,White,Black},\[Chi],w=If[k==-1,WalkMatrix[g],WalkMatrix[g,k]],colourFunction},
	If[\[Chi]Arg==Association[],\[Chi]=WalkColouringFunction[g],\[Chi]=\[Chi]Arg];
If[Head[\[Chi][[First[VertexList[g]]]]]==Integer,colourFunction=(Association[Table[j->\!\(\*
TagBox[GridBox[{
{"\[Piecewise]", GridBox[{
{
RowBox[{
RowBox[{"colours", "[", 
RowBox[{"[", "j", "]"}], "]"}], " "}], 
RowBox[{"j", "<=", "10"}]},
{
RowBox[{"RandomColor", "[", "]"}], "True"}
},
AllowedDimensions->{2, Automatic},
Editable->True,
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.84]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}},
Selectable->True]}
},
GridBoxAlignment->{"Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}},
GridBoxItemSize->{"Columns" -> {{Automatic}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {Offset[0.27999999999999997`], {Offset[0.35]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {Offset[0.2], {Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}],
"Piecewise",
DeleteWithContents->True,
Editable->False,
SelectWithContents->True,
Selectable->False,
StripWrapperBoxes->True]\),{j,Max[\[Chi]/@VertexList[g]]}]]@*\[Chi]),colourFunction=\[Chi]];    
Table[Style[#,colourFunction[i]]&/@w[[i]],{i,Length[w]}]];


KeepNonIsomorphic[l_]:=DeleteDuplicates[l,IsomorphicGraphQ];


IsomorphicCDCQ[g1_Graph,g2_Graph]:=VertexCount[g1]==VertexCount[g2]&&
	If[SimpleGraphQ[g1]&&SimpleGraphQ[g2],EdgeCount[g1]==EdgeCount[g2]&&
	Sort[VertexDegree[g1]]==Sort[VertexDegree[g2]],True]&&
	IsomorphicGraphQ[CDC[g1],CDC[g2]];


LabelVertices::invalidType="Expected graph object, instead found `1`.";
LabelVertices[g_Graph]:=Graph[g,VertexLabels->"Name"];
LabelVertices[l_List]:=LabelVertices/@l;
LabelVertices[default_]:=Message[LabelVertices::invalidType,default];


UnlabelVertices::invalidType="Expected graph object, instead found `1`.";
UnlabelVertices[g_Graph]:=Graph[g,VertexLabels->{_->""}];
UnlabelVertices[l_List]:=UnlabelVertices/@l;
UnlabelVertices[default_]:=Message[UnlabelVertices::invalidType,default];


IsolatedVertices[g_Graph]:=Select[Flatten[Select[Length[#]==1&][ConnectedComponents[g]],1],!EdgeQ[g,#\[UndirectedEdge]#]&];


IsolatedLoopedVertices[g_Graph]:=Select[Flatten[Select[Length[#]==1&][ConnectedComponents[g]],1],EdgeQ[g,#\[UndirectedEdge]#]&];


RemoveIsolatedVertices[g_Graph]:=VertexDelete[g,IsolatedVertices[g]];


RemoveIsolatedLoopedVertices[g_Graph]:=VertexDelete[g,IsolatedLoopedVertices[g]];


AddIsolatedVertex::cannotdelete="There aren't enough isolated vertices (`1` required) to delete from the graph `2`.";
AddIsolatedVertex[g_Graph,n_Integer:1]:=Module[{newG=g,i=1},Do[While[MemberQ[VertexList[newG],i],i++];newG=VertexAdd[newG,i],n];If[n<0,If[Length[IsolatedVertices[newG]]>=-n,newG=VertexDelete[newG,Sort[IsolatedVertices[newG]][[;;-n]]],Message[AddIsolatedVertex::cannotdelete,-n,g]]];newG];


AddIsolatedLoopedVertex::cannotdelete="There aren't enough looped isolated vertices (`1` required) to delete from the graph `2`.";
AddIsolatedLoopedVertex[g_Graph,n_Integer:1]:=Module[{newG=g,i=1},Do[While[MemberQ[VertexList[newG],i],i++];newG=EdgeAdd[VertexAdd[newG,i],i\[UndirectedEdge]i],n];If[n<0,If[Length[IsolatedLoopedVertices[newG]]>=-n,newG=VertexDelete[newG,Sort[IsolatedLoopedVertices[newG]][[;;-n]]],Message[AddIsolatedLoopedVertex::cannotdelete,-n,g]]];newG];


IsolatedVerticesQ[g_Graph]:=Length[IsolatedVertices[g]]>0;


IsolatedLoopedVerticesQ[g_Graph]:=Length[IsolatedLoopedVertices[g]]>0;


PartiteSets::bipartiteError="The graph `1` is not bipartite.";
PartiteSets[g_Graph]:=Module[{a,b},
	If[BipartiteGraphQ[g],
	a=Sort[First[(VertexList[#][[(Position[Sum[MatrixPower[AdjacencyMatrix[#],2n],{n,1,VertexCount[#]/2}][[1]]//Normal,0]//Flatten)]]&)[Subgraph[g,#]]&/@ConnectedComponents[g]]];
	b=Complement[VertexList[g],a];
	Return[{a,b}],
	Message[PartiteSets::bipartiteError,g];
]];


AppendixStyle[n_:0.3]:={GraphStyle->"BasicBlack",BaseStyle->EdgeForm[{Thick,Black}],EdgeStyle->{_\[UndirectedEdge]_->{Thick,Opacity[1]}},VertexSize->n};


CartesianProduct[g_Graph,h_Graph]:=Graph[Tuples[{VertexList[g],VertexList[h]}],Union[Sort/@Flatten[Union[Table[{u,f[[1]]}\[UndirectedEdge]{u,f[[2]]},{f,EdgeList[h]},{u,VertexList[g]}],Table[{e[[1]],v}\[UndirectedEdge]{e[[2]],v},{e,EdgeList[g]},{v,VertexList[h]}]]]]];
DirectProduct[g_Graph,h_Graph]:=Graph[Tuples[{VertexList[g],VertexList[h]}],Union[Sort/@Flatten[Table[{{e[[1]],f[[1]]}\[UndirectedEdge]{e[[2]],f[[2]]},{e[[1]],f[[2]]}\[UndirectedEdge]{e[[2]],f[[1]]}},{e,EdgeList[g]},{f,EdgeList[h]}]]]];
StrongProduct[g_Graph,h_Graph]:=Graph[Tuples[{VertexList[g],VertexList[h]}],Union[Sort/@Flatten[Union[Table[{u,f[[1]]}\[UndirectedEdge]{u,f[[2]]},{f,EdgeList[h]},{u,VertexList[g]}],Table[{e[[1]],v}\[UndirectedEdge]{e[[2]],v},{e,EdgeList[g]},{v,VertexList[h]}],Table[{{e[[1]],f[[1]]}\[UndirectedEdge]{e[[2]],f[[2]]},{e[[1]],f[[2]]}\[UndirectedEdge]{e[[2]],f[[1]]}},{e,EdgeList[g]},{f,EdgeList[h]}]]]]];
LexicographicProduct[g_Graph,h_Graph]:=Graph[Tuples[{VertexList[g],VertexList[h]}],Union[Sort/@Flatten[Union[Table[{e[[1]],u}\[UndirectedEdge]{e[[2]],v},{u,VertexList[h]},{v,VertexList[h]},{e,EdgeList[g]}],Table[{w,f[[1]]}\[UndirectedEdge]{w,f[[2]]},{w,VertexList[g]},{e,EdgeList[g]},{f,EdgeList[h]}]]]]];


graphProductSymbols=<|"Cartesian"->"\[EmptySquare]","Direct"->"\[Times]","Strong"->Overlay[{"\[EmptySquare]","\!\(\*AdjustmentBox[\"\[Times]\",BoxBaselineShift->-0.15]\)"}]|>;
graphProductNames=<|CartesianProduct->"Cartesian",DirectProduct->"Direct",StrongProduct->"Strong"|>;
graphProducts=<|"Cartesian"->CartesianProduct,"Direct"->DirectProduct,"Strong"->StrongProduct|>;


defaultGraphProduct=CartesianProduct;

DefaultGraphSum=If[IntersectingQ[VertexList[#1],VertexList[#2]],GraphDisjointUnion,GraphUnion][#1,#2]&;

DefaultGraphProduct::buqq="`1` is not a valid option for graph product.";
DefaultGraphProduct[s_String:0]:=If[s==0,
Echo[Row[{"\!\(\*StyleBox[\"Currently, \", \"Text\"]\)","\!\(\*StyleBox[\"g\", \"TI\"]\)",Spacer[1.5],"\!\(\*StyleBox[\"h\", \"TI\"]\) \!\(\*StyleBox[\"denotes the \", \"Text\"]\)",DisplayForm[StyleBox[graphProductNames[defaultGraphProduct]<>" product","Text",FontWeight->Bold]]," \!\(\*StyleBox[\"g\", \"TI\"]\)",Spacer[2.5],graphProductSymbols[graphProductNames[defaultGraphProduct]],Spacer[2.5],"\!\(\*StyleBox[\"h\", \"TI\"]\)."}]];
,If[KeyExistsQ[graphProducts,s],defaultGraphProduct=graphProducts[s];
Echo[Row[{DisplayForm[StyleBox["The default graph product was successfully set to the ","Text"]], DisplayForm[StyleBox[s<>" product","Text",FontWeight->Bold]]," \!\(\*StyleBox[\"g\", \"TI\"]\)",Spacer[2.5],graphProductSymbols[graphProductNames[defaultGraphProduct]],Spacer[2.5],"\!\(\*StyleBox[\"h\", \"TI\"]\)."}]];,Message[DefaultGraphProduct::buqq,s]]];

GraphMinus[g_Graph,h_Graph]:=Module[{hparts=ConnectedGraphComponents[h],gparts=ConnectedGraphComponents[g],i,j,left,right},
For[i=1,i<=Length[hparts],i++,
For[j=1,j<=Length[gparts],j++,
If[IsomorphicGraphQ[hparts[[i]],gparts[[j]]],hparts[[i]]=Null;gparts[[j]]=Null]]];
Piecewise[{{GraphUnion@@DeleteCases[gparts,Null],Union[hparts]==={Null}||Union[hparts]==={}},{-GraphUnion@@DeleteCases[hparts,Null],Union[gparts]==={Null}||Union[gparts]==={}}},Defer[#1-#2]&@@{(GraphUnion@@DeleteCases[gparts,Null]),(GraphUnion@@DeleteCases[hparts,Null])}]];

(* Monoidal graph sum *)
Plus[g_Graph,h_Graph]:=DefaultGraphSum[g,h];

(* Graph + integer *)
Plus[n_Integer/;n>=0,g_Graph]:=If[defaultGraphProduct===DirectProduct,AddIsolatedLoopedVertex,AddIsolatedVertex][g,n];
Plus[n_Integer/;n<0,g_Graph]:=GraphMinus[g,If[defaultGraphProduct===DirectProduct,AddIsolatedLoopedVertex,AddIsolatedVertex][Graph[{}],-n]]
Plus[n_Integer,Times[-1,h_Graph]]:=-(h-n);
Plus[n_Integer,Defer[Plus[g_Graph,Times[-1,h_Graph]]]]:=(g+n)-h;

(* Graph sum to deal with negatives *)
Plus[g_Graph,Times[-1,h_Graph]]:=GraphMinus[g,h];
Plus[Times[-1,g_Graph],Times[-1,h_Graph]]:=-(g+h);
Plus[g_Graph,Defer[Plus[h_Graph,Times[-1,k_Graph]]]]:=GraphMinus[g+h,k];
Plus[Times[-1,g_Graph],Defer[Plus[h_Graph,Times[-1,k_Graph]]]]:=GraphMinus[h,g+k];
Plus[Defer[Plus[g_Graph,Times[-1,h_Graph]]],Defer[Plus[k_Graph,Times[-1,l_Graph]]]]:=GraphMinus[g+k,h+l];

(* Monoidal graph times *)
Times::graphtimeserror="Cannot multiply the graph `1` by the integer `2`.";
Times[g_Graph,h_Graph]:=defaultGraphProduct[g,h];
Times[n_Integer/;n>=0,g_Graph]:=If[n==0,Graph[{},{}],If[n>1,DefaultGraphSum[g,Times[n-1,g]],Message[Times::graphtimeserror,g,n]]];

(* Times to deal with negative integers *)
Times[n_Integer/;n<-1,g_Graph]:=-((-n)g);
Times[n_Integer/;n>=0,Defer[Plus[g_Graph,Times[-1,h_Graph]]]]:=GraphMinus[n g,n h];
Times[n_Integer/;n<0,Defer[Plus[g_Graph,Times[-1,h_Graph]]]]:=GraphMinus[-n h,-n g];

(* Times to deal with negatives *)
Times[g_Graph,Times[-1,h_Graph]]:=-(g h);
Times[Times[-1,g_Graph],Times[-1,h_Graph]]:=g h;
Times[g_Graph,Defer[Plus[h_Graph,Times[-1,k_Graph]]]]:=(g h)-(g k);
Times[Times[-1,g_Graph],Defer[Plus[h_Graph,Times[-1,k_Graph]]]]:=(g k)-(g h);
Times[Defer[Plus[g_Graph,Times[-1,h_Graph]]],Defer[Plus[k_Graph,Times[-1,l_Graph]]]]:=g k+h l-g l-h k;

(* Monoidal graph power *)
Power::graphpowererror="Cannot raise the graph `1` to the the integer power `2`.";
Power[g_Graph,n_Integer]:=Piecewise[{{If[defaultGraphProduct===DirectProduct,Graph[{1},{1\[UndirectedEdge]1}],CompleteGraph[1]],n==0},{g,n==1},{defaultGraphProduct[g, Power[g,n-1]],n>=1}},Message[Power::graphpowererror,g,n]];
Power[Defer[Plus[g_Graph,Times[-1,h_Graph]]],n_Integer]:=Sum[(-1)^k Binomial[n,k]g^(n-k) h^k,{k,0,n}]


SeidelSwitch::wrongVertices="`1` is not a subset of the vertex set `3` of `2`.";
SeidelSwitch[g_Graph,U_List]:=Module[{E=EdgeList[g],betweenEdges,possibleEdges},If[SubsetQ[VertexList[g],U],
betweenEdges=Sort/@Select[EdgeList[g],Xor[MemberQ[U,#[[1]]],MemberQ[U,#[[2]]]]&];
possibleEdges=(Sort[#[[1]]\[UndirectedEdge]#[[2]]]&)/@Tuples[{U,Complement[VertexList[g],U]}];
EdgeAdd[EdgeDelete[g,betweenEdges],Complement[possibleEdges,betweenEdges]],Message[SeidelSwitch::wrongVertices,U,g,VertexList[g]]]];


DescendantForm::emptyGraph="The empty graph doesn't have a descendant form.";
DescendantForm::badVertex="`1` is not a vertex of `2`.";
DescendantForm[g_Graph]:=If[Length[VertexList[g]]>0,SeidelSwitch[g,AdjacencyList[g,VertexList[g][[1]]]],Message[DescendantForm::emptyGraph]];
DescendantForm[g_Graph,v_]:=If[MemberQ[VertexList[g],v],SeidelSwitch[g,AdjacencyList[g,v]],Message[DescendantForm::badVertex,v,g]];


SeidelMatrix[g_Graph]:=AdjacencyMatrix[GraphComplement[g]]-AdjacencyMatrix[g];
SeidelGraph[s_]:=AdjacencyGraph[(Table[Boole[i!=j],{i,Length[s]},{j,Length[s]}]-s)/2];


IdentifyVertices::argumentError="`2` is not a valid list of vertices in the graph `1`";
IdentifyVertices[g_Graph,o___List]:=Module[{newG=g,verts={o},rep,rem,newV,newE},
If[And@@(SubsetQ[VertexList[g],#]&/@{o}),
Do[rep=First[l];
rem=Rest[l];
newG=EdgeAdd[newG,Select[Union[Map[Replace[#->rep&/@rem],EdgeList[newG,(a_\[UndirectedEdge]b_)/;MemberQ[rem,a|b]],2]],!EdgeQ[newG,#]&]];
newG=VertexDelete[newG,rem],{l,verts}];newG,Message[IdentifyVertices::argumentError,g,o]]];


AddPendents::error="`2` is not a subset of the vertices of `1`";
AddPendents[g_Graph,l_List]:=Module[{newG=g,i=1},
If[SubsetQ[VertexList[g],l],
Do[While[MemberQ[VertexList[newG],i],i++];newG=EdgeAdd[VertexAdd[newG,i],i\[UndirectedEdge]v],{v,l}];newG,Message[AddPendents::error,g,l]]];
AddPendents[g_Graph]:=AddPendents[g,VertexList[g]];


AddDominatingVertex[g_Graph,n_Integer:1]:=GraphComplement[AddIsolatedVertex[GraphComplement[g],n]];


FreshLabels[g_Graph]:=LabelVertices[VertexReplace[g,Table[VertexList[g][[i]]->i,{i,VertexCount[g]}]]];


AntipodalVertices[g_Graph]:=Select[Subsets[VertexList[g],{2}],GraphDistance[g,#[[1]],#[[2]]]==GraphDiameter[g]&];


VertexDrag[g_Graph]:=DynamicModule[{pts=GraphEmbedding[g]},LocatorPane[Dynamic[pts],Dynamic[Graph[g,VertexCoordinates->pts]],Appearance->None]];


SetAttributes[{MainEigenvectors,MainEigenvalues,MainEigensystem,BoldEigenvalues,Eigenvalues,Eigenvectors,
Eigensystem,Det,Tr,NullSpace,Nullity,CharacteristicPolynomial,Inverse,Times,Plus,WalkMatrix,MainCharacteristicPolynomial,
CDC,AddLoops,WalkPartition,RyserSwitch,WalkColouringFunction,Colourful,ActualColours,ColourfulWalkMatrix,
KeepNonIsomorphic,IsomorphicCDCQ,LabelVertices,UnlabelVertices,IsolatedVertices,IsolatedLoopedVertices,RemoveIsolatedVertices,
RemoveIsolatedLoopedVertices,AddIsolatedVertex,AddIsolatedLoopedVertex,IsolatedVerticesQ,IsolatedLoopedVerticesQ,PartiteSets,
AppendixStyle,CartesianProduct,DirectProduct,StrongProduct,LexicographicProduct,DefaultGraphProduct,Plus,Times,Power,
SeidelSwitch,DescendantForm,SeidelMatrix,SeidelGraph,IdentifyVertices,AddPendents,AddDominatingVertex,FreshLabels,
AntipodalVertices,VertexDrag},{Protected,ReadProtected}];


End[ ]


EndPackage[ ]
