Java: ¿cómo representar gráficos?

Question

Estoy implementando algunos algoritmos para enseñarme acerca de los gráficos y cómo trabajar con ellos. ¿Cuál recomendarías es la mejor manera de hacerlo en Java? Estaba pensando algo así:

public class Vertex { 

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map. 

    //methods to manipulate outnodes 
} 

public class Graph { 
    private ArrayList<Vertex> nodes; 
    //algorithms on graphs 
} 

Pero básicamente lo inventé. ¿Hay una mejor manera?

Además, quiero que sea capaz de soportar las variaciones en los gráficos de vainilla como dígrafos, bordes ponderados, multigrafos, etc.

Answer 1

Si necesita bordes ponderados y multigrafos, es posible que desee añadir otra clase Edge .

También recomendaría utilizar genéricos para permitir especificar qué subclase de Vertex y Edge se utilizan actualmente. Por ejemplo:

public class Graph<V extends Vertex> { 
List<V> vertices; 
... 
} 

Cuando se trata de implementar algoritmos de grafos, también se podría definir interfaces de para sus clases gráfico en el que los algoritmos pueden funcionar, por lo que se puede jugar con diferentes implementaciones de la representación real gráfico . Por ejemplo, los gráficos simples que están bien conectados se puede aplicar mejor por un adjacency matrix, gráficos más dispersas podrían ser representados por adjacency lists - todo depende ...

BTW La construcción de estas estructuras de manera eficiente puede ser bastante difícil, Entonces, ¿podría darnos más detalles sobre el tipo de trabajo para el que desea usarlos? Para tareas más complejas, le sugiero que eche un vistazo a las diversas bibliotecas de gráficos de Java, para obtener algo de inspiración.

Answer 2

Eche un vistazo a la biblioteca de gráficos http://jung.sourceforge.net/doc/index.html. Aún puede practicar la implementación de sus propios algoritmos (tal vez la búsqueda de ancho primero o profundidad primero para comenzar), pero no necesita preocuparse por crear la estructura de gráfico.

Answer 3

Hace un tiempo tuve el mismo problema e hice mi propia implementación. Lo que sugiero es implementar otra clase: Edge. Entonces, un Vertex tendrá una Lista de bordes.

public class Edge { 
    private Node a, b; 
    private directionEnum direction;  // AB, BA or both 
    private int weight; 
    ... 
} 

Me funcionó. Pero tal vez es tan simple. Existe esta biblioteca que quizás pueda ayudarlo si nos fijamos en su código: http://jgrapht.sourceforge.net/

Answer 4

Recomendaría graphviz cuando llegue al punto en el que desea representar sus gráficos.

Y sus acompañantes: eche un vistazo a Laszlo Szathmary's GraphViz class, junto con notugly.xls.

Answer 5

Incluso en el momento de esta pregunta, hace más de 3 años, existía Sage (que es completamente gratuito) y era bastante bueno en la teoría de grafos. Pero, en 2012, se trata de la mejor herramienta de teoría de grafos que existe. Por lo tanto, Sage ya tiene una gran cantidad de material de teoría de gráficos integrado, incluidas otras cosas de código abierto y gratuito que están disponibles. Entonces, simplemente jugar con varias cosas para aprender más es fácil ya que no se requiere programación.

Y, si también está interesado en la parte de programación, primero Sage es de código abierto para que pueda ver cualquier código que ya exista.Y, en segundo lugar, puede volver a programar cualquier función que desee si realmente desea practicar, o puede ser el primero en programar algo que aún no existe. En el último caso, incluso puede enviar esa nueva funcionalidad y hacer que Sage sea mejor para todos los demás usuarios.

En este momento, esta respuesta puede no ser tan útil para el OP (ya que han pasado 3 años), pero es de esperar que sea útil para cualquier otra persona que vea esta pregunta en el futuro.

Answer 6

¿Por qué no mantener las cosas simples y usar un adjacency matrix o un adjacency list?

Answer 7

La implementación de la lista de adyacencia de Graph es adecuada para resolver la mayoría de los problemas relacionados con el gráfico.

La implementación de Java de la misma es here en mi blog.

Answer 8

class Graph<E> { 
    private List<Vertex<E>> vertices; 

    private static class Vertex<E> { 
     E elem; 
     List<Vertex<E>> neighbors; 
    } 
} 

Answer 9

class Vertex { 
    private String name; 
    private int score; // for path algos 
    private boolean visited; // for path algos 
    List<Edge> connections; 
} 

class Edge { 
    private String vertex1Name; // same as Vertex.name 
    private String vertex2Name; 
    private int length; 
} 

class Graph { 
    private List<Edge> edges; 
} 

Answer 10

Cada nodo es un nombre exclusivo y sabe quién está conectado. La Lista de conexiones permite que un Nodo se conecte a un número arbitrario de otros nodos.

public class Node { 
    public String name; 
    public List<Edge> connections; 
} 

Cada conexión está dirigida, tiene un principio y un fin, y está ponderada.

public class Edge { 
    public Node start; 
    public Node end; 
    public double weight; 
} 

Un gráfico es sólo su colección de nodos. En lugar de List<Node> considere Map<String, Node> para búsqueda rápida por nombre.

public class Graph { 
    List<Node> nodes; 
} 

Answer 11

Una simple representación escrita por Robert Sedgwick 'y 'Kevin Wayne' está disponible en http://algs4.cs.princeton.edu/41graph/Graph.java.html

Explicación copiado de la página anterior.

La clase gráfico representa un grafo no dirigido de vértices nombradas 0 a través de V - 1.

Es compatible con los siguientes dos operaciones principales: añadir un borde a la gráfica, iterar sobre todo de la vértices adyacentes a un vértice. También proporciona métodos para devolver el número de vértices V y el número de bordes E. Se permiten bordes paralelos y bucles automáticos. Por convención, una auto-loop v - v aparece en la lista de adyacencia v dos veces y dos contribuye al grado de v.

Esta implementación utiliza una representación de listas de adyacencia, que es una matriz indexada en vértices de objetos Bag. Todas las operaciones toman un tiempo constante (en el peor de los casos) excepto iterando sobre los vértices adyacentes a un vértice dado, lo que toma tiempo proporcional al número de dichos vértices.