API de recherche de graphe et de graphe Java

Question

Je suis dans une position où je dois modéliser un ensemble de JavaBeans dans une structure graphique, où chaque bean est un noeud/vertex sur le graphe, et ils sont "connectés"/liés à un autre via et bord. Donc, tout comme on utilise un List<?> ou ArrayList<?> pour représenter une séquence d'éléments, j'ai besoin d'une API (de préférence générique) pour représenter les nœuds dans un graphique. Cette API doit me permettre de construire le graphe, ajouter/enlever des noeuds du graphe comme j'aime, etc.

Aussi, je dois pouvoir rechercher le graphique entier en lui passant une valeur de données arbitraire, et il retournera le noeud/sommet qui contient ces données.

La seule chose que je peux trouver est le Java TreeSet intégré, mais je n'ai pas besoin d'un arbre dirigé qui coule d'un seul noeud racine. J'ai besoin d'une API graphique vraie (au sens mathématique).

Une telle solution existe-t-elle ou suis-je coincé en train d'écrire mon propre à partir de zéro (uggghhh). Merci d'avance!

Answer 1

Si je comprends bien vous avez besoin d'une représentation d'un « nœud » objet:

1) vous permet de stocker des valeurs, de sorte que vous pouvez rechercher plus tard pour le noeud droit

2) Utilisez un structure de données prédéfinie pour contenir les informations du graphique.

3) Autoriser l'utilisation par les algorithmes de recherche.

Il y a une solution triviale qui accomplit les trois exigences:

public class Node { 

    // Add as many fields as you need to contain the node info 
    private String mName; 
    private int mArbitraryValue; 

    // Store the adjacent nodes in a list 
    private List<Node> mAdjacencyList; 

    //Define your constructors 
    public Node(String name, int arbitraryValue, List<Node> adjacencyList) { 
     mName = name; 
     mArbitraryValue = arbitraryValue; 
     mAdjacencyList = adjacencyList; 
    } 

    /* Add your methods here depending on the functionality that 
     you want to implement 
    */ 

    public String getName() { 
     return mName; 
    } 

    public int getArbitraryValue() { 
     return mArbitraryValue; 
    } 

    public List<Node> getNeighbors() { 
     return Collections.unmodifiableList(mAdjacencyList); 
    } 

    // Add setters if you want these values to be able to change 

    public boolean addNeighbor(Node n) { 
     return !mAdjacencyList.contains((Node) n) && mAdjacencyList.add(n); 
    } 

    public boolean removeNeighbor(Node n) { 
     return mAdjacencyList.remove((Node) n); 
    } 
} 

Je ne recommande pas que vous mettre en œuvre la liste de contiguïté en utilisant un HashMap si vos objets peuvent être modifiés, car il peut causer l'ensemble de break (les appels à contains() peuvent renvoyer false même si l'objet est présent). Maintenant, vos algorithmes de recherche peuvent accéder aux variables membres du nœud pour vérifier si elles sont terminées.