Création d'un graphe

Signaler
Messages postés
175
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
8 avril 2021
-
Messages postés
175
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
8 avril 2021
-
Bonjour, j'essaie actuellement de créer un graphe. Mon graphe est composé d'une ArrayList, qui contient elle-même des LinkedList d'arêtes (classe Edge). Une arrête est caractérisée par un sommet u (origine), sommet v (destination) et un poids.

A la création du graphe, je peux indiquer la concentration d'arêtes que je souhaite avec le paramètre théta (la valeur 100 correspondant à 100% de ses arêtes).

Cependant, je bute jugement sur l'ajout des arêtes. Si mon graphe a 4 sommets, et que je souhaite qu'il ait ses 6 arêtes maximum, je n'en obtiens pas toujours 6...

Le code est quasi correct, il y a juste les getters que je n'ai pas fait vérifier, ainsi que l'étape d'ajout des arêtes à la création du graphe, justement...

J'ai débogué, apparemment c'est cette ligne qui me pose problème (dans le constructeur du graphe):
int nbEdges = vertices.get(u).size();

mais je ne vois pas pourquoi, sauriez-vous m'indiquer où est l'erreur ?

Main
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        Graph graph = new Graph(4,100);
        System.out.println("nb of vertices:" + graph.getNbVertices());
        System.out.println("nb of edges:" + graph.getNbEdges());

        graph.getEdgesAt(0);
        graph.getEdgesAt(1);
        graph.getEdgesAt(2);

    }
}


Graph

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class Graph {

    private ArrayList<LinkedList<Edge>> vertices;
    private int nbEdges;

    public Graph(int nbVertices, int theta){ // note: theta, the concentration of edges, in %

        // step: calcul of wanted edges
        int totalEdges = (nbVertices*(nbVertices-1))/2; // ex: 4 vertices => 6 edges
        int wantedEdges = totalEdges*theta/100; // ex: 6 edges * 50% = 3 edges
        if (wantedEdges<1){ //ex: 6 edges * 10% = 0,6 => 0 edge
            wantedEdges = wantedEdges+1; //at least one edge
        }
        this.nbEdges = wantedEdges;

        // step: creation of vertices
        vertices = new ArrayList<>(nbVertices);
        for (int i = 0; i < nbVertices; i++) {
            LinkedList<Edge> vertex = new LinkedList<>();
            vertices.add(vertex);
        }

        // step: creation of edges
        int createdEdges = 0;
        Random random = new Random();
        while (createdEdges<wantedEdges){
            int u = random.nextInt(nbVertices);
            int v = random.nextInt(nbVertices);

            // step: check if edge doesn't already exist in LL at index u of AL
            int nbEdges = vertices.get(u).size();
            for (int i = 0; i < nbEdges; i++) {
                if (vertices.get(u).get(i).getv() == v){
                    continue; // note: because edge already exists
                }
            }

            // step: adding edge to LL
            Edge edge = new Edge(u,v);
            vertices.get(u).add(edge);

            createdEdges++;
        }

    }

    /**
    * getters
    */
    public int getNbVertices(){
        return this.vertices.size();
    }

    public int getNbEdges(){
        return this.nbEdges;
    }


    public void getEdgesAt(int vertex){ // note: vertex = index in AL
        for (int i = 0; i < this.vertices.get(vertex).size(); i++) {
            this.vertices.get(vertex).get(i).getEdge();
        }
    }

}


Edge

import java.util.Random;

public class Edge {

    private int u; // original vertex
    private int v; // next vertex
    private int weight;

    public Edge(int u, int v){
        this.u = u;
        this.v = v;

        Random random = new Random();
        int weight = random.nextInt(100);
        this.weight = weight;
    }


    /**
     * getters
     */
    public int getu(){
        return this.u;
    }

    public int getv(){
        return this.v;
    }

    public int getWeight(){
        return this.weight;
    }

    public void getEdge(){
        System.out.println("u: "+this.getu()+" | v: "+this.getv()+" | weight: "+this.getWeight());
    }

}

3 réponses

Messages postés
16301
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
7 avril 2021
2 817
Bonjour,

Ta structure de données est incorrecte :
public class Graph {
    private ArrayList<LinkedList<Edge>> vertices;
    private int nbEdges;
}
Je ne sais pas pourquoi tu as pensé à une liste imbriquée, mais c'est faux.

Remarque : en Java on utilisera plutôt ArrayList pour manipuler une List, l'utilisation de LinkedList est assez rare, elle est davantage liée aux Queue qu'aux List.

Si on reprends la définition d'un graphe (Larousse)
"Graphe simple ou non orienté, couple d'ensembles (X, C) où X est un ensemble d'éléments appelés sommets et C un ensemble d'éléments appelés arêtes."
La structure de données correspondante serait donc :
public class Graph {
    private Set<Node> nodes;
    private Set<Edge> edges;
}

Remarque : je t'encourage à te créer une classe Node, ce qui modifiera un peu ta classe Edge :
public class Edge {
    private Node u;
    private Node v;
    private int weight;
}
Messages postés
175
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
8 avril 2021
1
Bonjour,
Mon graphe doit être orienté.
Et on me demande d'implémenter les graphes de cette manière: un tableau ou une liste contenant une linkedlist, contenant elle-même les sommets. En gros, dans l'idée, comme ça:
Messages postés
16301
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
7 avril 2021
2 817
Bonjour,

Cette représentation d'un graphe est incorrecte.

D'une part, elle permet d'avoir plusieurs représentations différentes d'un même graphe, ce qui va complexifier tes méthodes de manipulation car tu vas devoir gérer toutes les manières dont le graphe pourrait être représenté.
Exemple avec ce graphe que tu pourrais représenter avec 0 → 1 → 2 ou en deux lignes avec 0 → 1 et 1 → 2

D'autre part, elle ne permet pas de représenter certains graphes, ce qui est beaucoup plus gênant.
Exemple avec ce graphe dont tu pourras représenter soit 0 → 1, soit 0 → 2 mais pas les deux en même temps...
Messages postés
175
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
8 avril 2021
1
Je vois. Mais le truc c'est que ce n'est pas moi qui ai choisi cette implémentation: je suis forcée de la suivre...