CODEWITHSUNDEEP
javagraph
Spencer Melo
Spencer Melo

Reputation: 410

How to represent an undirected weighted graph in java

I'm doing some study about graphs, as it's not exactly my field of study, I'm really struggling to represent an undirected weighted graph, but I think I'm following the wrong idea, follow some code:

public class Vertex { // Nothing really new here...
    private String label;

    public Vertex(String pageObject) {
        this.label = pageObject;
    }
    // blabla.
}

Here I think is where I start doing things wrong:

public class Edge {
    private String source; //Source? if it's bidirectional It's not supposed to have a source, or am I wrong? Like it's source looking from the starting point?
    private int weight;
    private String destination; //Same thing here.

    public Edge(String source, int weight, String destination) {
        this.source = source;
        this.weight = weight;
        this.destination = destination;
    }
}

And here, I'm really lost:

public class Graph { // Really struggling to represent it here.
    private Map<Vertex, List<Edge>> adjVertices;
}
// I think the wrong idea about the graph above may lead to results like this below, and it seems wrong, like Earth being the key, and also the source...
// Just an example:
{  
   "Earth":{  
      "source":"Earth",
      "weight":150,
      "destination":"Jupiter"
   }
}

Almost every example is related to directed graphs, so I need some light on how to correct or do it from zero.

Upvotes: 3

Views: 8876

Answers (1)

c0der
c0der

Reputation: 18792

There are many different way to represent vertices, edges and a graph. Here is an over-simplified one:

Define a directional Edge :

class Edge {

    private Vertex to; 
    private int weight;

    public Edge(Vertex to, int weight) {
        super();
        this.to = to;
        this.weight = weight;
    }

    Vertex getTo() {
        return to;
    }

    int getWeight() {
        return weight;
    }   

    //todo override hashCode()
}

Define a Vertex so that each vertex has a collection of Edges to its neighbors: 

class Vertex { 

    private String label;
    private Set<Edge> edges; //collection of edges to neighbors 

    public Vertex(String pageObject) {
        this.label = pageObject;
        edges = new HashSet<>();
    }

    String getLabel() {
        return label;
    }

    boolean addEdge(Edge edge){
        return edges.add(edge);
    }

    List<Edge> getEdges() {
        return new ArrayList<>(edges);
    }

    //todo override hashCode()
}

Define a Graph which has a collection of Vertex objects: 

class Graph{

    private Set<Vertex> vertices; //collection of all verices 

    public Graph() {
        vertices = new HashSet<>();
    } 

    List<Vertex> getVertices() {
        return new ArrayList<>(vertices);
    }   

    boolean addVertex(Vertex vertex){
        return vertices.add(vertex);
    }
}

Construct a graph: 

public static void main(String[] args) {

    Graph graph = new Graph();

    //construct vertices 
    Vertex v1 = new Vertex("1"); 
    Vertex v2 = new Vertex("2"); 
    Vertex v3 = new Vertex("3");
    Vertex v4 = new Vertex("4");
    Vertex v5 = new Vertex("5");

    //to make the graph un directed use the same weight 
    //both ways 
    v1.addEdge(new Edge(v2, 1)); //connect v1 v2 
    v2.addEdge(new Edge(v1, 1));   

    v2.addEdge(new Edge(v3, 2)); //connect v2 v3
    v3.addEdge(new Edge(v2, 2));

    v2.addEdge(new Edge(v4, 3)); //connect v2 v4
    v4.addEdge(new Edge(v2, 3));

    v4.addEdge(new Edge(v5, 1)); //connect v4 v5
    v5.addEdge(new Edge(v4, 1));

     graph.addVertex(v1); graph.addVertex(v2); graph.addVertex(v3);
     graph.addVertex(v4); graph.addVertex(v5);  
}

Upvotes: 4

Related Questions