Clique Hierarchy: private API
PortfolioOptimisers.clique3 — Function
clique3(A::MatNum)List the 3-cliques of a Maximal Planar Graph (MPG).
The function finds every 3-clique, a triangle, of the graph that A holds. It returns the candidate edges, the third vertices that close a triangle on each candidate edge, and the list of the distinct 3-cliques.
Algorithm
- Remove the diagonal of
Aand reduce it to a binary matrix. - Form
A2 = A * A, whose entry counts the paths of length two between a pair. - Keep the upper triangle of the entries where
A2andAare both non-zero, which givesP. A stored entry ofPis an edge whose two ends share at least one neighbour. - Read the row and the column index of each stored entry of
Pinto the two columns ofE, one row for each candidate edge. - For each candidate edge, intersect the neighbourhoods of its two ends, which gives
K3[n], the third vertices that close a triangle on the edge. - Sort each triple
(E[n, 1], E[n, 2], K3[n][m])and keep it when it is new. The function finds a triangle from each of its three edges, and it stores the triangle once. - Sort the triples, and write them as the rows of
clique.
Arguments
A:N × Nadjacency matrix of a Maximal Planar Graph (MPG). A non-zero entry is an edge.
Returns
K3::Vector{Vector{Int}}:K3[n]holds the vertices that close a triangle on the candidate edge of rownofE.E::Matrix{Int}:Ne×2matrix of the candidate edges, one edge for each row, with the smaller vertex in the first column.clique::Matrix{Int}:Nc×3matrix. Each row lists the three vertices of one 3-clique of the MPG in ascending order, and the rows are in lexicographic order.
Related
PortfolioOptimisers.FindDisjoint — Function
FindDisjoint(Adj::MatNum, Cliq::VecNum)Split the vertices of a graph into a 3-clique and the sides that the clique separates.
The function cuts the three vertices of Cliq out of the graph. It then labels each vertex as a vertex of the clique, a vertex that IndxNot[1] can reach, or a vertex that IndxNot[1] cannot reach.
Algorithm
- Copy
AdjintoTemp, and collect inIndxNotevery vertex that is not one of the three ofCliq. - Set the rows and the columns of
TempatCliqto zero. This cuts the clique out of the graph, and it separates the sides that the clique joins. - Run
breadthfromIndxNot[1], which givesd, and mark with-1each vertex at an infinite distance. - Write
1intoTat every vertex marked-1, and2at every other vertex, so2is the side that holdsIndxNot[1]. - Write
0intoTat the three vertices ofCliq.
Arguments
Adj:N × Nadjacency matrix of the MPG. A non-zero entry is an edge.Cliq:3×1vector of the vertices of a 3-clique.
Returns
T::Vector{Int}:N × 1vector of the side of each vertex.0for a vertex of the clique.1for a vertex thatIndxNot[1]cannot reach in the graph without the clique.2for a vertex thatIndxNot[1]can reach,IndxNot[1]included.
IndxNot::Vector{Int}:(N - 3)×1vector of every vertex that is not a vertex ofCliq, in ascending order.
Related
PortfolioOptimisers.BuildHierarchy — Function
BuildHierarchy(M::MatNum)Find the parent of each 3-clique of a Maximal Planar Graph (MPG).
The function builds the parent vector Pred from the matrix M. Column n of M marks the vertices of 3-clique n and of its interior. The parent of a 3-clique is the 3-clique with the fewest marked vertices whose marks hold every mark of it. CliqHierarchyTree2s calls this function, and it builds the clique hierarchy from Pred.
Algorithm
- For each 3-clique
n, readChildren, the vertices that columnnofMmarks. - Sum the rows of
MoverChildren, and take asParentsevery clique whose sum equalslength(Children). The column of such a clique marks every vertex that columnnmarks, so the clique is a superset of cliquen. Dropnfrom that list. - Set
Pred[n] = 0whenParentsis empty, which makes cliquena root candidate. - Otherwise set
Pred[n]to the parent with the fewest marked vertices, the smallest superset. - When two parents have the same smallest count, return an empty vector. The empty vector tells the caller that the function built no hierarchy, and the loop stops at that point.
Arguments
M:N × Ncbinary matrix.M[i, n] = 1when vertexiis a vertex of 3-cliquenor of its interior. Step 3 ofCliqHierarchyTree2sstates which side of the graph is the interior.
Returns
Pred::Vector{Int}:Nc×1vector of the parent of each 3-clique, an index into the columns ofM.Pred[n] = 0marks a root candidate. The vector is empty when step 5 of the algorithm returns.
Related
PortfolioOptimisers.AdjCliq — Function
AdjCliq(A::MatNum, CliqList::MatNum,
CliqRoot::VecNum)Find the pairs of root candidates of a Maximal Planar Graph (MPG) that share an edge.
The function computes the adjacency matrix of the root candidates, which are 3-cliques. Two root candidates are adjacent when they share exactly two vertices. The EqualRoot method of CliqueRoot calls it to join the root candidates to each other.
The function reads only the size of A, and no edge of the MPG changes the result. The result loses nothing by that. Every row of CliqList is a 3-clique of the MPG, so two rows that share two vertices both hold the edge between those two vertices. Thus the count of the shared vertices is the test for adjacency in the graph.
Algorithm
- Clear
Indicator, then mark in it the three vertices of root candidaten. - Read
Indicatorback at the three vertex columns of every root candidate, which givesIndi. - Take the root candidates whose row of
Indisums to2, and set their entries of columnCliqRoot[n]ofAdjto one. - Repeat from step 1 for the next candidate. The test of step 3 is symmetric, so
Adjneeds no symmetrisation.
Arguments
A:N × Nadjacency matrix of the MPG. The function reads onlysize(A, 1), which sets the length ofIndicator.CliqList:Nc×3matrix. Each row lists the three vertices of a 3-clique of the MPG.CliqRoot: Vector of the indices of the root candidates, which index the rows ofCliqList.
Returns
Adj::SparseMatrixCSC{Int, Int}:Nc×Ncsymmetric adjacency matrix of the cliques.Adj[i, j]is one when cliquesiandjare both root candidates and share exactly two vertices. Every other entry is zero, so a clique that is not a root candidate carries an empty row and an empty column.
Related
PortfolioOptimisers.CliqueRoot — Function
CliqueRoot(::UniqueRoot, Root::VecNum, Pred::VecNum, Nc::Integer, args...)Build the adjacency matrix of the clique hierarchy of a Maximal Planar Graph (MPG) with one root.
When the hierarchy has more than one root candidate, this method adds a synthetic root clique and makes it the parent of every root candidate. CliqHierarchyTree2s calls it when its root is UniqueRoot.
Algorithm
- When more than one root candidate exists, append a synthetic clique to
Predand set the parent of every root candidate to it. The method changesPredin place, so the vector of the caller gets that entry. - Allocate
HoverNc + 1rows and columns, which is the room the synthetic clique of step 1 needs. - Write
H[n, Pred[n]] = 1for every clique that has a parent. - Symmetrise
H.
Arguments
::UniqueRoot: Root selection method that makes one root.Root: Vector of the indices of the root candidates, which index the entries ofPred.Pred:Nc×1vector of the parent of each 3-clique, fromBuildHierarchy.Nc: Number of 3-cliques.args...: Positional arguments, which this method ignores.CliqHierarchyTree2spasses the adjacency matrix and the clique list here. TheEqualRootmethod reads them, and this method does not.
Returns
H::SparseMatrixCSC{Int, Int}:(Nc + 1)×(Nc + 1)symmetric adjacency matrix of the hierarchy tree of the 3-cliques. Row and columnNc + 1hold the synthetic root. They are empty when the hierarchy has one root candidate.
Related
CliqueRoot(::EqualRoot, Root::VecNum, Pred::VecNum, Nc::Integer,
A::MatNum, CliqList::MatNum)Build the adjacency matrix of the clique hierarchy of a Maximal Planar Graph (MPG), with the root candidates joined to each other.
This method adds no root clique. It joins two root candidates when they share two vertices, so the hierarchy keeps every root candidate. CliqHierarchyTree2s calls it when its root is EqualRoot.
Algorithm
- When more than one root candidate exists, build the adjacency
Adjof the candidates withAdjCliq. One candidate has no other candidate to join, soAdjis a zero matrix in that case, and step 4 adds nothing. - Allocate
HoverNcrows and columns. This method adds no synthetic clique, so it needs no extra row. - Write
H[n, Pred[n]] = 1for every clique that has a parent. - Return a
0 × 0matrix whenPredis empty. Otherwise symmetriseHand addAdjto it, which joins the root candidates to each other.
Arguments
::EqualRoot: Root selection method that joins the root candidates to each other.Root: Vector of the indices of the root candidates, which index the entries ofPred.Pred:Nc×1vector of the parent of each 3-clique, fromBuildHierarchy.Nc: Number of 3-cliques.A:N × Nadjacency matrix of the MPG. The method passes it toAdjCliq, which reads only its size.CliqList:Nc×3matrix. Each row lists the three vertices of a 3-clique of the MPG.
Returns
H::SparseMatrixCSC{Int, Int}:Nc×Ncsymmetric adjacency matrix of the hierarchy of the 3-cliques, or a0 × 0matrix whenPredis empty.
Related
PortfolioOptimisers.CliqHierarchyTree2s — Function
CliqHierarchyTree2s(Apm::MatNum, root::DBHTRootMethod = UniqueRoot())Build the clique hierarchy and the bubble tree of a Maximal Planar Graph (MPG), as the Direct Bubble Hierarchical Tree (DBHT) method needs them.
The function builds the hierarchy of the 3-cliques and the tree of the bubbles from the adjacency matrix of a planar graph. The root argument selects the rule for the root of the clique hierarchy.
root is a positional argument, and every caller passes it as one.
Algorithm
- Reduce
Apmto the binary adjacencyA, and list every 3-clique of it withclique3, which givesCliqList. - For each 3-clique, cut it out of the graph with
FindDisjoint, which splits the vertices into the cliqueindx0, the sideindx1that the cut separated, and the sideindx2that stayed connected. - Take the smaller of the two sides, together with the clique, as the separated set
indx_s. A tie takesindx1, the side that the cut separated. The smaller side is the interior of the clique in [126], Definition 2.2, and that definition does not decide a tie. Recordlength(indx_s) - 3inSb[n], and mark the vertices ofindx_sin columnnofM. - Build the parent vector
PredfromMwithBuildHierarchy, and read the root candidatesRootoff it. - Build the clique hierarchy
HwithCliqueRoot, through the branchrootselects. - When
His non-empty, build the bubble hierarchyH2and the bubble membershipMbwithBubbleHierarchy, reduceH2to binary, and trimMbto the rows ofCliqList. - Return
0 × 0matrices forH2andMbwhenHis empty.
Arguments
Apm:N × Nadjacency matrix of the MPG. A non-zero entry is an edge. The function reads only the sparsity pattern, so a weighted matrix and its binary form give the same result.root: Root selection method for the clique hierarchy.
Returns
H::SparseMatrixCSC{Int, Int}: Symmetric adjacency matrix of the hierarchy of the 3-cliques. TheCliqueRootmethod thatrootselects sets its size.H2::SparseMatrixCSC:Nb×Nbsymmetric adjacency matrix of the bubble tree withBoolentries, whereNbis the number of bubbles. It is a0 × 0matrix ofIntwhenHis empty.Mb::AbstractMatrix{Int}:Nc×Nbdense bubble membership matrix of the 3-cliques.Mb[n, bi] = 1means that 3-cliquenbelongs to bubblebi. It is a0 × 0sparse matrix whenHis empty.CliqList::Matrix{Int}:Nc×3list of the 3-cliques. Each row holds the three vertices of one 3-clique.Sb::Vector{Int}:Nc×1vector of the number of vertices in the interior of each 3-clique. An entry is positive exactly when its 3-clique separates the graph.
Related
References
- [126] W.-M. Song, T. Di Matteo and T. Aste. Nested hierarchies in planar graphs. Discrete Applied Mathematics 159, 2135–2146 (2011). Definition 2.2 for the interior, Definition 3.2 and Corollary 3.6 for
H, and Definitions 4.3 and 5.1 for the bubbles andH2.
References
- [126]
- W.-M. Song, T. D. Matteo and T. Aste. Nested hierarchies in planar graphs. Discrete Applied Mathematics 159, 2135–2146 (2011).