Search for subgraphs homeomorphic to K3, 3, and K5 Java
The Pontryagin - Kuratovsky theorem. A graph is planar if and only if it does not contain subgraphs that are homeomorphic to K5 or K3, 3
Homeomorphism in this context denotes an equivalence relation.
The task is to implement a program that will check the graph for planarity by referring to this theorem (not the Gamma algorithm). The question is: is there an algorithm for iterating through subgraphs in a graph and how to check them for homeomorphism with K5 and K3,3.
public Vertex[] getCycleLen5() {
Vertex[] adjList = graph.getAdjList();
boolean[][] aMatrix = createAdjMatrix(adjList);
//Const for max len of cycles;
final int n = 5;
Vertex[]subGraph = new Vertex[n];
for (int i = 0 ; i < n ; i++)
subGraph[i] = new Vertex();
for (int a = 0 ; a < graph.getVertices() ; a++)
for (int b = a + 1 ; b < graph.getVertices() ; b++) {
if (!aMatrix[a][b]) continue;
for (int c = b + 1; c < graph.getVertices() ; c++) {
if (!aMatrix[b][c]) continue;
for (int d = c + 1; d < graph.getVertices() ; d++) {
if (!aMatrix[c][d]) continue;
for (int e = d + 1; e < graph.getVertices() ; e++)
if (aMatrix[d][e] && aMatrix[e][a]) {
subGraph[0] = adjList[a];
subGraph[1] = adjList[b];
subGraph[2] = adjList[c];
subGraph[3] = adjList[d];
subGraph[4] = adjList[e];
}
}
}
}
return subGraph;
}
1 answers
OK, since the search for cycles in the graph does not cause problems and is satisfied with the answer to C# (see the comments to the question), then I will give a simple solution head-on. LiNQ is not used to simplify porting to Java, although it would be more compact with it.
We define a simple vertex class of a non-directed graph (the required minimum):
class Vertex
{
public List<Vertex> Adges = new List<Vertex>();
public bool HasAdgeToVertex(Vertex vertex)
{
foreach(var adge in Adges)
{
if (adge == vertex) return true;
}
return false;
}
}
Now we need two functions to check that the vertices of the found cycle are the graph K5 or K3, 3
Checking for K5:
bool IsK5graph(Vertex[] subgraph)
{
bool result = false;
int n = 5;
if (subgraph.Length == n)
{
result = true;
for (var i = 0; i < n - 1; i++)
{
for (var j = i + 1; j < n; j++)
{
result &= subgraph[i].HasAdgeToVertex(subgraph[j]);
}
}
}
return result;
}
Just checking it out that for a given set of vertices, there are all 10 necessary edges.
Similarly for K3, 3, but taking into account its features, we will slightly change the internal check cycle:
bool IsK33graph(Vertex[] subgraph)
{
bool result = false;
int n = 6;
if (subgraph.Length == n)
{
result = true;
for (var i = 0; i < n - 1; i++)
{
for (var j = i + 1; j < n; j += 2)
{
result &= subgraph[i].HasAdgeToVertex(subgraph[j]);
}
}
}
return result;
}
Both checks are performed in N iterations, where N is the number of edges of the graph K5 and K3, 3, respectively. Given small N, optimizing the validation by reducing the number of iterations and complicating the validation code may not have any or even a negative effect on the overall graph validation time. But you can optimize the check the presence of an edge at a vertex, for example, by replacing the List for storing adjacent vertices with a HashSet if the source graph does not contain parallel edges.
If you set the edges through the adjacency matrix, then the matrix for K5, will look like this, for an undirected graph:
1 2 3 4 5
---------
1 | 0 1 1 1 1 |
2 | 1 0 1 1 1 |
3 | 1 1 0 1 1 |
4 | 1 1 1 0 1 |
5 | 1 1 1 1 0 |
Then the solution can be reduced to constructing an adjacency matrix for the vertices of the found cycle and checking that it does not coincide with the given one. To speed up the process, you can combine the construction and verification of matrices adjacency to match. If the main graph is defined through the adjacency matrix, then this option may be convenient.
For K3, 3, the matrix is:
1 2 3 4 5 6
-----------
1 | 0 1 0 1 0 1 |
2 | 1 0 1 0 1 0 |
3 | 0 1 0 1 0 1 |
4 | 1 0 1 0 1 0 |
5 | 0 1 0 1 0 1 |
6 | 1 0 1 0 1 0 |