Directed weighted Graph Data Structure in Java

Question

I am beginner in Java. I coded Directed weighted Graph data structure by myself without anyone's help i want to have some constructive feedback regarding my program design, weather my code is perfect or it needs some improvements, Here is my code :

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
/**
 * @author Rajat
 * Contains 3 classes
 * MapNode - contains info about individual vertex in graph, like nodes connecting to it, its name, edges.
 * MapEdge - class to represent edges between two nodes. it stores distance between two nodes.
 * Graph - Core Graph data structure functionality.
 */
class MapNode{
 private Set<MapEdge> edges;
 private String name;
 public MapNode(String name)
 {
 this.name = name;
 edges = new HashSet<MapEdge>(); 
 }
 void addEdge(MapEdge edge)
 {
 edges.add(edge);
 }
 String getName()
 {
 return new String(this.name);
 }
 Set<MapNode> getNeighbors()
 {
 Set<MapNode> neighbor = new HashSet<MapNode>();
 for(MapEdge edge : edges)
 {
 neighbor.add(edge.getDestination());
 }
 return neighbor;
 }
 Set<MapEdge> getEdges()
 {
 return new HashSet(this.edges);
 }
}
class MapEdge 
{
 private MapNode source, destination;
 private double distance;
 public MapEdge(MapNode source, MapNode destination, double distance) {
 this.source = source;
 this.destination= destination;
 this.distance= distance;
 }
 MapNode getSource()
 {
 return this.source;
 }
 MapNode getDestination()
 {
 return this.destination;
 }
 double getDistance()
 {
 return this.distance;
 }
}
public class Graph {
 private int numVertices;
 private Map<MapNode, HashSet<MapEdge>> vertices;
 Graph(){
 numVertices = 0;
 vertices = new HashMap<MapNode, HashSet<MapEdge>>();
 }
 void addEdge(MapNode source, MapNode destination, double distance)
 {
 if(vertices.containsKey(source))
 {
 MapEdge map_edge = new MapEdge(source, destination, distance);
 vertices.get(source).add(map_edge);
 source.addEdge(map_edge);
 }
 else
 {
 System.out.println("Source vertex not found..");
 }
 }
 void addVertex(MapNode V)
 {
 if(!vertices.containsKey(V))
 {
 vertices.put(V, new HashSet<MapEdge>());
 System.out.println("Vertex Added");
 ++numVertices;
 }
 else
 System.out.println("Vertex already added");
 }
 ArrayList<MapNode> getNeighbor(MapNode vertex)
 {
 return new ArrayList<MapNode>(vertex.getNeighbors());
 }
 // to get distance between verices directly connected to each other
 double getDistance(MapNode source, MapNode destination)
 {
 double distance = 0.0;
 for(MapEdge edge : vertices.get(source))
 {
 if(edge.getDestination() == destination)
 {
 distance = edge.getDistance();
 break;
 }
 }
 return distance;
 }
 // No of vertices in graph
 int numVertices()
 {
 return numVertices;
 }
 void bfs(MapNode source)
 {
 Queue<MapNode> queue = new LinkedList<MapNode>();
 HashSet<MapNode> visited = new HashSet<MapNode>();
 ArrayList<String> path = new ArrayList();
 queue.add(source);
 while(!queue.isEmpty())
 {
 MapNode node = queue.poll();
 visited.add(node);
 Set<MapNode> neighbor = node.getNeighbors();
 // System.out.print("Node " +node.getName()+ "\t ");
 for(MapNode V : neighbor){
 // System.out.print(V.getName()+" \t");
 if(!visited.contains(V))
 {
 queue.add(V);
 visited.add(V);
 path.add(V.getName());
 }
 }
 // System.out.println("");
 }
 System.out.println("BFS \t"+path.toString());
 }
 public static void main(String[] args) {
 Graph graph = new Graph();
 // creating vertex
 MapNode vellore = new MapNode("Vellore");
 MapNode chennai = new MapNode("Chennai");
 MapNode bangalore = new MapNode("Bangalore");
 MapNode mahabalipuram = new MapNode("Mahabalipuram");
 MapNode pondicherry = new MapNode("Pondicherry");
 MapNode yelagiri = new MapNode("Yelagiri");
 MapNode katpadi = new MapNode("Katpadi");
 MapNode kanchipuram = new MapNode("kanchipuram");
 // adding vertex to graph
 graph.addVertex(vellore);
 graph.addVertex(bangalore);
 graph.addVertex(chennai);
 graph.addVertex(mahabalipuram);
 graph.addVertex(pondicherry);
 graph.addVertex(yelagiri);
 graph.addVertex(katpadi);
 graph.addVertex(kanchipuram);
 // conneting edges
 graph.addEdge(chennai, mahabalipuram, 25);
 graph.addEdge(chennai, pondicherry, 300);
 graph.addEdge(pondicherry, mahabalipuram, 500);
 graph.addEdge(chennai, katpadi, 110);
 graph.addEdge(vellore,bangalore, 250);
 graph.addEdge(vellore, chennai, 120);
 graph.addEdge(katpadi, vellore, 15);
 graph.addEdge(bangalore, katpadi, 265);
 graph.addEdge(bangalore, kanchipuram,400 );
 System.out.println("Distance between Chennai to Mahabalipuram "+graph.getDistance(chennai, mahabalipuram));
 }
}

Answer 1

Naming; Domain Specific Language

Looking at the terms used in this program, we have:

• map node
• map edge
• vertex
• graph

With a bit of care on consistency and simplicity, you could rework these names to:

• graph
• node
• edge

The less terms, and no interchangeable terms, the easier to understand the design.

A minor thing, but I find it odd for an edge to have "distance". length seems more natural.

Immutable fields

Some of the fields in your design never change. It's good to make these final, to enforce that, and to avoid potential mistakes.

On a related note, this is a pointless operation:

String getName()
{
 return new String(this.name);
}

Strings are immutable in Java, so you can safely return this.name.

Return when you know the result

The distance variable is unnecessary here, and only complicates the implementation:

double getDistance(MapNode source, MapNode destination)
{
 double distance = 0.0;
 for(MapEdge edge : vertices.get(source))
 {
 if(edge.getDestination() == destination)
 {
 distance = edge.getDistance();
 break;
 }
 }
 return distance;
}

You can simply return the result immediately when you know it:

double getDistance(MapNode source, MapNode destination)
{
 for(MapEdge edge : vertices.get(source))
 {
 if(edge.getDestination() == destination)
 {
 return edge.getDistance();
 }
 }
 return 0.0;
}

Use interfaces in type declarations

Instead of this:

private Map<MapNode, HashSet<MapEdge>> vertices;

You would gain flexibility by using the interface type:

private Map<MapNode, Set<MapEdge>> vertices;

Use the diamond <> operator

Instead of this:

 vertices = new HashMap<MapNode, HashSet<MapEdge>>();

You would gain flexibility by using the diamond <> operator, supported as of Java 7:

 vertices = new HashMap<>();

Avoid printing

Avoid printing to standard output in methods that are not specifically designed for producing output. Reorganize to move printing functionality in methods designated just for that.

Formatting

The coding style doesn't follow the common conventions suggested by modern IDEs. I suggest to edit your program in IntelliJ or Eclipse and use the automatic reformatting feature. It's easier to read code when all developers follow the same conventions.