Grafo - Planaridade

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package péquége;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author mathias
 */
public class Planar {
    Grafo grafo;

    public Planar(Grafo grafo){
        this.grafo = grafo;
    }

    public boolean isPlanar(){
        if(grafo.getNumVertices() > 2 && isCircular(grafo.getMatrizAdjacencia())){
            if (grafo.getNumArestas() <= 3 * grafo.getNumVertices() - 6) {
                return true;
            }
        }else if (grafo.getNumVertices() < 3){
            return true;
        }else if(grafo.getNumArestas() <= 2 * grafo.getNumVertices() - 4){
            return true;
        }
        return false;
    }

    public boolean isCircular(int[][] matriz){
        for (int i = 0; i < matriz.length; i++) {
            List<Integer> adjacencias = new ArrayList<>();
            for (int j = 0; j < matriz.length; j++) {
                if (matriz[i][j] > 0) {
                    adjacencias.add(j);
                }
            }
            if (adjacencias.size() > 1) {
                while(!adjacencias.isEmpty()){
                    for (int k = 1; k < adjacencias.size(); k++) {
                        if (matriz[adjacencias.get(0)][adjacencias.get(k)] > 0) {
                            return true;
                        }
                    }
                    adjacencias.remove(0);
                }
            }
        }
        return false;
    }
}