[Java] Struttura dati grafi, esistono già?

[guylmaster]

Qualcuno sa dirmi se come struttura dati in Java esiste già il Grafo e non vedo ricrearmelo tutto da zero?

Perché fino ad ora ho utilizzato più che altro liste o dizionari, ma di grafi è la prima volta che devo utilizzarli in java e volevo capire se potevo evitare di dovermeli creare da zero.

Vi ringrazio in anticipo,
Guylmaster.

[ndakota]

Ci stavo pensando proprio in questi giorni che mi sembra assurdo non siano previsti nella libreria standard. In ogni caso, non devi riscriverteli da zero, ci sono soluzioni di terze parti molto valide.

http://www.jgrapht.org/

[banryu79]

JGrapht - per le strutture dati e gli algoritmi
JGraph - per la GUI
(JGrapht supporta l'interoperabilità con JGraph; JGraph può anche essere usata da sola).

[guylmaster]

Rieccomi, ho un piccolo problemino: Di base nei vari demo gli si passa come archi un oggetto defaultedge che non permette di etichettare gli archi.

Io ho bisogno di fare archi etichettati con stringhe, come faccio a creare un tipo mio di arco o a trovarne uno già fatto che permetta di etichettare gli archi?

[banryu79]

Originariamente inviato da guylmaster

Rieccomi, ho un piccolo problemino: Di base nei vari demo gli si passa come archi un oggetto defaultedge che non permette di etichettare gli archi.

Io ho bisogno di fare archi etichettati con stringhe, come faccio a creare un tipo mio di arco o a trovarne uno già fatto che permetta di etichettare gli archi?

Devi aver mancato questo esempio:
http://sourceforge.net/apps/mediawik...t:LabeledEdges
In pratica definisci una tua classe che estende DefaultEdge e implementi quello che ti pare.

[guylmaster]

Originariamente inviato da banryu79

Devi aver mancato questo esempio:
http://sourceforge.net/apps/mediawik...t:LabeledEdges
In partica definisci una tua classe che estende DefaultEdge e implementi quello che ti pare.

Ho provato a ricopiare nel package grapht esatto esatto quell'esempio, non da errori e viene eseguito però non stampa nulla, invece dovrebbe stampare le liste di amici e nemici. Cosa mi sfugge?

[banryu79]

Originariamente inviato da guylmaster

Ho provato a ricopiare nel package grapht esatto esatto quell'esempio, non da errori e viene eseguito però non stampa nulla, invece dovrebbe stampare le liste di amici e nemici. Cosa mi sfugge?

Umm... sì, l'esempio online contiene una piccola "svista", eccone una versione funzionante (correzioni evidenziate):

package jgrapht;

import java.util.ArrayList;
import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.ClassBasedEdgeFactory;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DirectedMultigraph;

public class LabeledEdges {
    private static final String friend = "friend";
    private static final String enemy = "enemy";

    public static void main(String[] args) {
        DirectedGraph<String, RelationshipEdge> graph =
            new DirectedMultigraph<String, RelationshipEdge>(
                    new ClassBasedEdgeFactory<String, RelationshipEdge>(RelationshipEdge.class));

        ArrayList<String> people = new ArrayList<String>();
        people.add("John");
        people.add("James");
        people.add("Sarah");
        people.add("Jessica");

        // John is everyone's friend
        for (String person : people) {
            graph.addVertex(person);
            graph.addEdge(people.get(0), person, new RelationshipEdge<String>(people.get(0), person, friend));
        }

        // Apparently James doesn't really like John
        graph.addEdge("James", "John", new RelationshipEdge<String>("James", "John", enemy));

        // Jessica is Sarah and James's friend
        graph.addEdge("Jessica", "Sarah", new RelationshipEdge<String>("Jessica", "Sarah", friend));
        graph.addEdge("Jessica", "James", new RelationshipEdge<String>("Jessica", "James", friend));

        // But Sarah doesn't really like James
        graph.addEdge("Sarah", "James", new RelationshipEdge<String>("Sarah", "James", enemy));

        for (RelationshipEdge edge : graph.edgeSet()) {
            if (edge.hasLabel(enemy)) {
                System.out.printf("%s is an enemy of %s\n", edge.getV1(), edge.getV2());
            } else if (edge.hasLabel(friend)) {
                System.out.printf("%s is a friend of %s\n", edge.getV1(), edge.getV2());
            }
        }
    }

    public static class RelationshipEdge<V> extends DefaultEdge {
        private V v1;
        private V v2;
        private String label;

        public RelationshipEdge(V v1, V v2, String label) {
            this.v1 = v1;
            this.v2 = v2;
            this.label = label;
        }

        public V getV1() {
            return v1;
        }

        public V getV2() {
            return v2;
        }

        public boolean hasLabel(String label) {
            return this.label.equals(label);
        }

        @Override
        public String toString() {
            return label;
        }
    }
}

Dovrebbe produrre in output:

run:
John is a friend of John
John is a friend of James
John is a friend of Sarah
John is a friend of Jessica
James is an enemy of John
Jessica is a friend of Sarah
Jessica is a friend of James
Sarah is an enemy of James
BUILD SUCCESSFUL (total time: 0 seconds)