jme

Class JMEMath.TeoriaGrafos

java.lang.Object

jme.JMEMath.TeoriaGrafos

Enclosing class:

JMEMath

public static class JMEMath.TeoriaGrafos
extends java.lang.Object

TEORÍA DE GRAFOS

Since:

0.6.2.0

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	JMEMath.TeoriaGrafos.Grafo Estructura de datos para grafo/digrafo/multigrafo/pseudografo y ponderados
static interface	JMEMath.TeoriaGrafos.PredicadoNodo

Constructor Summary

Constructors

Constructor and Description
TeoriaGrafos()

Method Summary

Modifier and Type	Method and Description
static java.lang.Object	caminoDesdeMatrizCaminosYDistancias(double[][] matDist, int[][] matCam, int inicio, int fin) Camino entre dos nodos a partir de la matriz de caminos y la de distancias o costes
static JMEMath.TeoriaGrafos.Grafo	completo(int orden, boolean dirigido, java.lang.String prefijo) Crea un grafo completo Korden
static JMEMath.TeoriaGrafos.Grafo	havelHakimi(int[] sucesion) Comprueba si una sucesión es gráfica y devuelve el grafo asociado a ella por el algoritmo de Havel-Hakimi.
static double[][]	listaAdyacenciasAMatrizAdyacencia(int[][] lst) Lista de adyacencias a matriz de adyacencia
static int[][]	matrizAdyacenciaAListaAdyacencias(double[][] ady) Matriz de adyacencia a lista de adyacencia para grafo/multigrafo/pseudografo dirigidos o no dirigidos
static double[][]	matrizAdyacenciaAMatrizIncidencia(double[][] ady, boolean dirigido, boolean ponderado) Convertir matriz de adyacencia de grafo/multigrafo/pseudografo en matriz de incidencia.
static double[][]	matrizAdyacenciaDesdePares(int[][] aristas, int nodos, boolean dirigido) Crea una matriz de adyacencias para grafos/multigrafos/pseudografos dirigidos o no dirigidos a partir de pares de nodos (aristas), también llamada lista de incidencia.
static double[][]	matrizIncidenciaAMatrizAdyacencia(double[][] inc, boolean dirigido, boolean ponderado) Convertir matriz de incidencia de un grafo/digrafo/multigrafo/pseudografo en matriz de adyacencia
static java.math.BigInteger	numGrafos(int numNodos) Número de posibles grafos simples sin bucles
static int[][]	paresDesdeMatrizAdyacencia(double[][] ady, boolean dirigido) Crea una matriz de pares ordenados de nodos (también llamada lista de incidencia) para grafos/multigrafos/pseudografos dirigidos o no dirigidos a partir de la matriz de adyacencia.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TeoriaGrafos

public TeoriaGrafos()

Method Detail

havelHakimi

public static JMEMath.TeoriaGrafos.Grafo havelHakimi(int[] sucesion)

Comprueba si una sucesión es gráfica y devuelve el grafo asociado a ella por el algoritmo de Havel-Hakimi. Si no es gráfica devuelve null

Parameters:

sucesion - sucesión de enteros no negativos

Returns:

el grafo obtenido por Havel-Hakimi o null si no es sucesión gráfica

Throws:

JMEInterruptedException - si el hilo se interrumpe

numGrafos

public static java.math.BigInteger numGrafos(int numNodos)

Número de posibles grafos simples sin bucles

Parameters:

numNodos - nº de nodos [1,65536]

Returns:

2^{C(numNodos,2)}

Throws:

java.lang.IllegalArgumentException - 'numNodos' fuera de [1,65536]

matrizAdyacenciaDesdePares

public static double[][] matrizAdyacenciaDesdePares(int[][] aristas,
                                                    int nodos,
                                                    boolean dirigido)

Crea una matriz de adyacencias para grafos/multigrafos/pseudografos dirigidos o no dirigidos a partir de pares de nodos (aristas), también llamada lista de incidencia. No válido para grafos ponderados

Parameters:

aristas - pares de nodos

nodos - nº de nodos totales

dirigido - true para grafo dirigido. Si es false, se creará una matriz simétrica (nodo <a,b>=<b,a>)

Returns:

matriz de adyacencia del grafo

Throws:

java.lang.ArrayIndexOutOfBoundsException - lista de nodos mal definida o nº de nodos demasiado pequeño

paresDesdeMatrizAdyacencia

public static int[][] paresDesdeMatrizAdyacencia(double[][] ady,
                                                 boolean dirigido)

Crea una matriz de pares ordenados de nodos (también llamada lista de incidencia) para grafos/multigrafos/pseudografos dirigidos o no dirigidos a partir de la matriz de adyacencia. Los pares se ordenarán en orden de índices

Parameters:

ady - matriz de adyacencia

dirigido - true para grafos dirigidos, false para no dirigidos (la matriz debe ser simétrica, o el resultado será inesperado)

Returns:

matriz Nx2 de pares ordenados

Throws:

JMEInterruptedException - si el hilo se interrumpe

java.lang.ArrayIndexOutOfBoundsException - matriz mal formada

matrizAdyacenciaAMatrizIncidencia

public static double[][] matrizAdyacenciaAMatrizIncidencia(double[][] ady,
                                                           boolean dirigido,
                                                           boolean ponderado)

Convertir matriz de adyacencia de grafo/multigrafo/pseudografo en matriz de incidencia. Los grafos ponderados deben ser estrictamente positivos

Parameters:

ady - matriz de adyacencia con posibles bucles y lados paralelos

dirigido - flag dirigido

ponderado - flag ponderado

Returns:

matriz de incidencia (la matriz de incidencia no es única, las columnas pueden variar de orden)

Throws:

java.lang.ArrayIndexOutOfBoundsException - matriz mal formada

JMEInterruptedException - si el hilo se interrumpe

matrizIncidenciaAMatrizAdyacencia

public static double[][] matrizIncidenciaAMatrizAdyacencia(double[][] inc,
                                                           boolean dirigido,
                                                           boolean ponderado)

Convertir matriz de incidencia de un grafo/digrafo/multigrafo/pseudografo en matriz de adyacencia

Parameters:

inc - matriz de incidencia (filas vértices y columnas aristas)

dirigido - flag dirigido

ponderado - flag ponderado

Returns:

matriz de adyacencia

Throws:

java.lang.ArrayIndexOutOfBoundsException - matriz malformada (columna nula)

JMEInterruptedException - si el hilo se interrumpe

matrizAdyacenciaAListaAdyacencias

public static int[][] matrizAdyacenciaAListaAdyacencias(double[][] ady)

Matriz de adyacencia a lista de adyacencia para grafo/multigrafo/pseudografo dirigidos o no dirigidos

Parameters:

ady - matriz de adyacencia

Returns:

lista de adyacencias

Throws:

java.lang.ArrayIndexOutOfBoundsException - matriz mal formada

JMEInterruptedException - si el hilo se interrumpe

listaAdyacenciasAMatrizAdyacencia

public static double[][] listaAdyacenciasAMatrizAdyacencia(int[][] lst)

Lista de adyacencias a matriz de adyacencia

Parameters:

lst - lista de adyacencias

Returns:

matriz de adyacencia

Throws:

JMEInterruptedException - si el hilo se interrumpe

caminoDesdeMatrizCaminosYDistancias

public static java.lang.Object caminoDesdeMatrizCaminosYDistancias(double[][] matDist,
                                                                   int[][] matCam,
                                                                   int inicio,
                                                                   int fin)

Camino entre dos nodos a partir de la matriz de caminos y la de distancias o costes

Parameters:

matDist - matriz de distancias o costes

matCam - matriz de caminos

inicio - nodo de inicio

fin - nodo final

Returns:

• array de nodos del camino
• Infinity si no hay camino
• -Infinity si hay un ciclo negativo en el camino

completo

public static JMEMath.TeoriaGrafos.Grafo completo(int orden,
                                                  boolean dirigido,
                                                  java.lang.String prefijo)

Crea un grafo completo Korden

Parameters:

orden - nº de nodos

dirigido - true para digrafo completo

prefijo - prefijo de las etiquetas

Returns:

Korden