Wednesday, August 27, 2014

Cycle detection in undirected graph

Cycle detection in a graph is one of the applications of depth-first traversal algorithm. Cycle detection in a directed and undirected graph are two different problems (and both can be solved by tweaking DFS). Cycle in a directed graph can be detected through topological sort, which I have already covered here. In this post, I will be covering cycle detection in an undirected graph using DFS traversal.

Tree edge vs Back edge

If you traversing an undirected graph using DFS, each edge can be classified either as tree edge or back edge. This classification helps in identifying if a cycle exists in the graph. 

If an undirected graph is implemented though Adjacency List, then edge between vertex u and v i.e. E(u,v) will have two entries.  Recall that, method, addEdge(..) is called twice during construction of graph, ref (check out the main method).
graph.addEdge(u,v);   //edge from u to v
graph.addEdge(v,u)   // edge from v to u


So this means, there are two options to process edge E(u,v) ( as E(u,v) and E(v,u) both mean the same edge); first time when you are exploring vertex u and second time when you exploring vertex v. Edge can be classified as tree edge or back edge when the edge is explored for the first time (i.e. either you start with u or v) . When you encounter edge from vertex u and vertex v is untraversed or undiscovered then edge, E(u,v) becomes tree edge. Discovery of back edge is bit tricky, though. From below example take the case of an edge between 5 and 2 i.e. E(5,2).  So when you start exploring this edge from vertex 5, vertex 2 is already explored and it's not the parent of vertex 5. So edge, E(5,2) becomes a tree edge as shown in below diagram.
Algorithm Design Manual
Edge classification: referred from 'Algorithm Design Manual' book

Back edges, help in finding cycle in undirected graph. If there are no back edges, then all edges are tree edge and hence no cycle exists in the graph. But presence of any back-edge confirms the presence of cycle. 

Implementation 

I have tweaked DFS implementation to return back edges. Below is code with the main method as a test method. Method, traverse(..) processes adjacent nodes/vertices from a source vertex to confirm if it's back-edge.

package graph.algo;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * Detect loop in an undirected graph using DFS
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class DetectCycle<V> {
 private Graph<V> graph; // graph on which dfs will be performed
 private Deque<V> stack; // Deque used to implement stack
 private Set<V> visited; // stores set of visited nodes

 public DetectCycle(Graph<V> graph) {
  this.graph = graph;
  stack = new ArrayDeque<>();
  visited = new LinkedHashSet<>(); // to maintain the insertion order
 }

 /**
  * Iterative/stack based DFS implementation
  * 
  * @param source
  */
 public Map<V, List<V>> traverse(V source) {
  Objects.requireNonNull(source);
  if (this.graph == null || this.graph.isEmpty()) {
   throw new IllegalStateException(
     "Valid graph object is required !!!");
  }

  // map back edges..source to destination
  Map<V, List<V>> backEdges = new LinkedHashMap<>();

  stack.push(source);
  this.markAsVisited(source);
  boolean pop = false;
  V stackTopVertex;
  V parent = null;
  //System.out.print("  " + source);
  List<V> targetVerticesOfEdge = null;

  while (!stack.isEmpty()) {

   if (pop == true)
    stackTopVertex = stack.pop();
   else
    stackTopVertex = stack.peek();

   List<V> neighbors = graph.getAdjacentVertices(stackTopVertex);

   /**
    * process neighboring vertex for back edge before continuing with
    * DFS
    */
   source = stackTopVertex;
   for (V dest : neighbors) {
    if ((pop != true) && (parent != null) && (dest != parent)
      && (visited.contains(dest))) {
     System.out.println("\n (Back Edge :" + source + " , "
       + dest + " )");
     if (backEdges.containsKey(source)) {
      targetVerticesOfEdge = backEdges.get(source);
      targetVerticesOfEdge.add(dest);
     } else {
      targetVerticesOfEdge = new ArrayList<>();
      targetVerticesOfEdge.add(dest);
      backEdges.put(source, targetVerticesOfEdge);
     }
    }
   }

   parent = stackTopVertex;

   if (!neighbors.isEmpty()
     && hasUnvisitedNeighbor(neighbors, visited)) {
    for (V a : neighbors) {
     if (!this.isVertexVisited(a)) {
      //System.out.print("  " + a);
      visited.add(a);
      stack.push(a);
      // break from loop if an unvisited neighbor is found
      break;
     }
    }
   } else {
    // if all neighbors are visited
    pop = true;
   }
  }

  return backEdges;
 }

 /**
  * checks if any of the neighbor is unvisited
  * 
  * @param neighbors
  * @param visited
  * @return
  */
 private boolean hasUnvisitedNeighbor(List<V> neighbors, Set<V> visited) {
  for (V i : neighbors) {
   if (!visited.contains(i))
    return true;
  }
  return false;
 }

 private boolean isVertexVisited(V v) {
  return this.visited.contains(v);
 }

 private void markAsVisited(V v) {
  this.visited.add(v);
 }

 // test method
 public static void main(String[] args) {

  Graph<Integer> graph = new Graph<>();
  graph.addEdge(1, 2);
  graph.addEdge(1, 5);
  graph.addEdge(1, 6);
  graph.addEdge(2, 3);
  graph.addEdge(2, 5);
  graph.addEdge(3, 4);
  graph.addEdge(5, 4);

  // for undirected graph
  graph.addEdge(2, 1);
  graph.addEdge(5, 1);
  graph.addEdge(6, 1);
  graph.addEdge(3, 2);
  graph.addEdge(5, 2);
  graph.addEdge(4, 3);
  graph.addEdge(4, 5);

  DetectCycle<Integer> dfs = new DetectCycle<>(graph);

  Map<Integer, List<Integer>> backedges = dfs.traverse(1);
  System.out.println("\n\n Back Edges Are --" + backedges);

 }

}

Output:

 (Back Edge: 5, 1 )


 (Back Edge: 5, 2 )



 Back Edges Are --{5=[1, 2]}


--
keep coding !!!

Sunday, August 24, 2014

Topological Sort

Topological sorting is one of the most important operations on Directed Acyclic Graphs (DAGs).  It orders vertices of the graph linearly such that for every directed edge uv, vertex u comes before vertex v. Topological sorting of a graph is not possible if the graph is cyclic.
Suppose you have a set of precedence constraint task to be performed, where certain tasks have to be performed before other tasks. These precedence constraint tasks form DAGs, so topological sort can be used to linearly order these tasks in such a way that all dependencies are taken care.

Algorithm

Topological sort can be performed efficiently using depth-first search. A directed graph is a DAG if and only if no back edges are encountered. Labeling the vertices in the reverse order that they are marked processed generates a topological sort for DAG. 

There is another technique for topological sorting, known as source removal technique. Implementation of this approach is simpler but it modifies the graph object. It removes the vertex and the corresponding edge which doesn't have any incoming edge. So after this, the new graph will be a reduced sub-graph of the original graph. Keep doing the same until the graph is not empty or you find a cycle in the graph. Below diagram shows in steps. 


Note that in the first step, we could have removed B first and then A. So the order would have been B, A, C, D, E. So clearly more than one sort is possible for the same DAG.

Implementation 

Below is Java implementation of source removal technique. Adjacency list graph is referenced from here.

package graph.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Topological sort for Directed Acyclic Graphs using source removal technique
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class TopologicalSort<V> {

 /**
  * Sort method which takes graph object as input and returns sorted list of
  * vertices
  * 
  * @param graph
  * @return
  */
 public List<V> sort(Graph<V> graph) {
  List<V> sortedVertices = new ArrayList<>();

  while (!graph.isEmpty()) {
   Set<V> vertices = getVerticesWithoutIncomingEdges(graph);
   if (!vertices.isEmpty()) {
    sortedVertices.addAll(vertices);
    for (V v : vertices) {
     graph.removeVertex(v);
    }
   } else {
    System.out.println(" Graph is NOT ADG");
    return Collections.emptyList();
   }
  }

  return sortedVertices;
 }

 /**
  * Returns set of vertices which doesn't have any incoming edge So there are
  * only outgoing connections/relationship
  * 
  * 
  * @param graph
  * @return
  */
 private Set<V> getVerticesWithoutIncomingEdges(Graph<V> graph) {
  if (graph.isEmpty() || graph == null) {
   return Collections.emptySet();
  }
  Set<V> response = new HashSet<>();
  Set<V> totalVertices = new HashSet<>();

  totalVertices.addAll(graph.getAllVertices());
  response.addAll(graph.getAllVertices());

  for (V v : totalVertices) {
   response.removeAll(graph.getAdjacentVertices(v));
  }
  return response;
 }

 /**
  * Test method
  * 
  * @param args
  */
 public static void main(String[] args) {
  TopologicalSort<Character> ts = new TopologicalSort<>();
  Graph<Character> g = new Graph<>();
  g.addEdge('A', 'C');
  g.addEdge('B', 'C');
  g.addEdge('C', 'D');
  g.addEdge('C', 'E');
  g.addEdge('D', 'E');

  System.out.println(g.toString());
  List<Character> sortedVertices = ts.sort(g);
  System.out.println(" sorted vertices -->" + sortedVertices);
 }

}

Output:
Set of Edges :
A ------->C
B ------->C
C ------->D
C ------->E
D ------->E
& Set of vertices :[A, B, C, D, E]

 sorted vertices -->[A, B, C, D, E]

--
keep coding !!!

Thursday, August 21, 2014

Dijkstra Algorithm

Dijkstra's algorithm finds the shortest distance from vertex s to t in a Graph.  In fact, it finds the shortest path from the source, s, to all other vertices/nodes of the graph. Due to this, it is also referred to as a single-source shortest path. It's a greedy algorithm and does NOT work on graphs with negative weight/cost edges.


Algorithm


The input for Dijkstra's algorithm is a graph object and the source or initial vertex. Shortest distance to all other vertices from this initial vertex will get computed after the completion of the algorithm. Below are the steps:
  • Initialize a distance map which stores the distance of each vertex from the source. This will help in identifying the next vertex with the highest priority. The vertex with minimum weight will be processed next. In the beginning, the source will have distance as 0 and rest all vertices will be given a large number.
  • Queue stores vertices which need to be processed yet. It provides the next vertex with minimum weight. It can be implemented using the priority queue. Vertex with minimum weight will have the highest priority.
  • Parent is used to mapping each node to its parent. This will be helpful to find the path from source to a given destination vertex/node.
  • Visited set stores already visited vertices. This helps in considering only unvisited neighbors for expanding algorithm. 
  • Each cycle of the while loop calculates the shortest distance to one node from the initial source node. 
    • From a given vertex, u, it identifies unvisited adjacent vertices. And then for all adjacent vertices weights are relaxed.
    • Relaxation process(i.e. relax method) updates the cost of all the vertices, v, connected to vertex, u. It checks if the current estimated cost of v can be improved by going through u. 
    • After each while loop, one vertex with minimum weight is removed from the queue and its distance and parent gets updated. 
  • Finally, the method returns an MST tree list. 


Implementation


Below is Java implementation of Dijkstra's algorithm. Wikipedia has a beautiful animation showing the progress of the algorithm.

package graph.algo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * Single Source Shortest Path Dijkstra Algorithm
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Dijkstra<V> {
 private Map<V, Integer> distance;
 private Map<V, V> parent;
 private Graph<V> graph;
 private Set<V> queue;

 public Dijkstra(Graph<V> graph) {
  // distance of each vertex from source
  this.distance = new LinkedHashMap<V, Integer>();

  // stores parent of each vertex
  this.parent = new LinkedHashMap<>();

  // input graph
  this.graph = graph;

  // used as input for providing next vertex
  // with minimum weight
  this.queue = new HashSet<V>();
 }

 /**
  * Initialize supporting data structure
  * 
  * @param source
  */
 private void initialize(V source) {
  Iterator<V> itr = graph.getAllVertices().iterator();
  while (itr.hasNext()) {
   distance.put(itr.next(), Integer.MAX_VALUE);
  }
  distance.put(source, 0);

  queue.addAll(distance.keySet());
 }

 /**
  * Dijkstra algorithm Takes input source vertex to start
  * 
  * @param source
  */
 public List<V> getShortestPath(V source) {
  Objects.requireNonNull(source);
  if (this.graph == null || this.graph.isEmpty()) {
   throw new IllegalStateException(
     "Valid graph object is required !!!");
  }

  List<V> traversedOrder = new ArrayList<>();

  this.initialize(source);
  Set<V> visited = new HashSet<>(); // set of vertices whose path have
           // already been found

  int wtuv = 0;

  while (!queue.isEmpty()) {

   // extract vertex with minimum weight
   V u = this.extractMinFromQueue();
   visited.add(u);

   traversedOrder.add(u);

   List<V> neighbors = this.graph.getAdjacentVertices(u);
   neighbors.removeAll(visited); // consider only unvisited nodes

   if (!neighbors.isEmpty()) {
    for (V v : neighbors) {
     wtuv = this.graph.getWeight(u, v);
     relax(u, v, wtuv);
    }
   }
  }
  return traversedOrder;
 }

 /**
  * Updates distance of node v from source node u
  * 
  * @param u
  *            source vertex
  * @param v
  *            target vertex
  * @param wtuv
  */
 private void relax(V u, V v, long wtuv) {
  if (distance.get(v) > distance.get(u) + wtuv) {
   distance.put(v, distance.get(u) + (int) wtuv);
   parent.put(v, u);
   // System.out.println(" u,v --"+ u + " , "+ v + " distance --> "+
   // distance);
  }
 }

 /**
  * Extract next vertex with smallest weight /highest priority removes the
  * node (optional) Can be implemented through priority queue
  * 
  * @return V vertex
  */
 private V extractMinFromQueue() {
  int weight = Integer.MAX_VALUE;
  V minVertex = null;
  for (V v : this.queue) {
   if (distance.get(v) < weight) {
    minVertex = v;
    weight = distance.get(v);
   }
  }
  if (minVertex != null)
   this.queue.remove(minVertex);
  return minVertex;
 }

 /**
  * Test method
  * 
  * @param args
  */
 public static void main(String[] args) {
  Graph<Integer> graph = new Graph<Integer>();

  graph.addEdge(1, 2, 5);
  graph.addEdge(2, 1, 5);

  graph.addEdge(1, 3, 12);
  graph.addEdge(3, 1, 12);

  graph.addEdge(2, 3, 6);
  graph.addEdge(3, 2, 6);

  graph.addEdge(2, 4, 13);
  graph.addEdge(4, 2, 13);

  graph.addEdge(3, 4, 5);
  graph.addEdge(4, 3, 5);

  Dijkstra<Integer> d = new Dijkstra<>(graph);

  System.out.println(graph.toString());
  List<Integer> path = d.getShortestPath(1);
  System.out.println(" Path or traversed vertices --" + path);
  System.out.println(" Distance Map for each vertex --" + d.distance);
  System.out.println(" Vertex and it's parent vertex Map --" + d.parent);

 }

}

Output:
Set of Edges :
1 -- (5)--->2
1 -- (12)--->3
2 -- (5)--->1
2 -- (6)--->3
2 -- (13)--->4
3 -- (12)--->1
3 -- (6)--->2
3 -- (5)--->4
4 -- (13)--->2
4 -- (5)--->3
& Set of vertices :[1, 2, 3, 4]
 Path or traversed vertices --[1, 2, 3, 4]
 Distance Map for each vertex --{1=0, 2=5, 3=11, 4=16}
 Vertex and it's parent vertex Map --{2=1, 3=2, 4=3}

Important Points

  1. Time complexity of algorithm is O(n^2); where n is number of vertices.
  2. All pair shortest path can be calculated by calling Dijkastra algorithm from each of the n possible vertices. 
  3. It works correctly only on graphs without negative-cost edges. 
  4. This algorithm generates shortest path tree with source as tree root. 
  5. If you want to find the shortest distance only to a target vertex/node; break loop once the target node is processed. 

References

Monday, August 18, 2014

Graph.java

Check here, for Graph basics. Below is adjacency list based graph implementation in Java.

package graph.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;

/**
 * Graph object which maps source and destination vertex. It's adjacency list
 * implementation. It maps vertex to node. Node encapsulates a vertex and the
 * weight.
 * 
 * It is represented as : vertexSource ---------> Node
 * 
 * So in above relationship- the weight is put in Node class. It is implicitly
 * same as putting weight on the edge. And to allow more than one Node
 * connection; map stores the list of Nodes.
 * 
 * Set<V> vertices : for fast retrieval instead of traversing the graph and
 * getting the list of vertices.
 * 
 * Can be used to model : 1) Directed graph 2) Undirected graph : make sure to
 * call addEdge(src,dest, wt) and addEdge(dest, src, wt) 3) Weighted and
 * Unweighted : make weight as 0/default value for Unweighted graph
 * 
 * Required Java Version = 7
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Graph<V> {
 private Map<V, List<Node<V>>> adjacencyList;
 private Set<V> vertices;
 private static final int DEFAULT_WEIGHT = Integer.MAX_VALUE;

 public Graph() {
  this.adjacencyList = new HashMap<>();
  vertices = new HashSet<>();
 }

 /**
  * Node class to represent nodes in the graph. The weight attribute allows
  * you to represent weighted graph.
  * 
  * @param <V>
  */
 private static class Node<V> {
  private V name; // Vertex name
  private int weight;

  public Node(V name, int weight) {
   this.name = name;
   this.weight = weight;
  }

  public V getName() {
   return name;
  }

  public int getWeight() {
   return weight;
  }

  @Override
  public int hashCode() {
   return this.getName().hashCode();
  }

  @Override
  public String toString() {
   return "(" + this.weight + ")" + this.name;
  }
 }

 /**
  * Getter method for graph object
  * 
  * @return Map<V, List<Node<V>>>
  */
 public Map<V, List<Node<V>>> getGraph() {
  return this.adjacencyList;
 }

 /**
  * Checks if graph is empty ? Even if there is a single vertex; it won't be
  * considered as empty.
  * 
  * @return
  */
 public boolean isEmpty() {
  return this.vertices.isEmpty();
 }

 /**
  * Add a new neighbor node or adjacent node for the given source vertex.
  * Vertex to node connection forms Edge.
  * 
  * @param src
  * @param destNode
  */
 private void addEdge(V src, Node<V> destNode) {
  List<Node<V>> adjacentVertices = adjacencyList.get(src);
  if (adjacentVertices == null || adjacentVertices.isEmpty()) {
   adjacentVertices = new ArrayList<Node<V>>();
   adjacentVertices.add(destNode);
  } else {
   adjacentVertices.add(destNode);
  }
  adjacencyList.put(src, adjacentVertices);
 }

 /**
  * Add an edge between src and destination vertices
  * 
  * @param src
  * @param dest
  * @param weight
  */
 public void addEdge(V src, V dest, int weight) {
  Objects.requireNonNull(src);
  Objects.requireNonNull(dest);

  this.addEdge(src, new Node<>(dest, weight));

  // update vertices set
  this.vertices.add(src);
  this.vertices.add(dest);
 }

 /**
  * Add an edge between src and destination vertices overloaded method to
  * create Unweighted graph
  * 
  * @param src
  * @param dest
  * @param weight
  */
 public void addEdge(V src, V dest) {
  Objects.requireNonNull(src);
  Objects.requireNonNull(dest);

  this.addEdge(src, new Node<>(dest, DEFAULT_WEIGHT));

  // update vertices set
  this.vertices.add(src);
  this.vertices.add(dest);
 }

 /**
  * Takes two vertices and checks if there is a path between v1 and v2.
  * Doesn't take vice-versa.
  * 
  * @param source
  * @param destination
  * @return
  */
 public boolean hasRelationship(V source, V destination) {
  if (source == null && destination == null)
   return true;
  if (source != null && destination == null)
   return true;
  if (source == null && destination != null)
   return false;

  List<Node<V>> nodes = null;

  if (adjacencyList.containsKey(source)) {
   nodes = adjacencyList.get(source);
   if (nodes != null && !nodes.isEmpty()) {
    for (Node<V> neighbors : nodes) {
     if (neighbors.getName().equals(destination))
      return true;
    }
   }
  }
  return false;
 }

 /**
  * get weight of the edge
  * 
  * @param src
  * @param dest
  * @return weight
  */
 public int getWeight(V src, V dest) {
  int weight = DEFAULT_WEIGHT;
  if (this.hasRelationship(src, dest)) {
   List<Node<V>> adjacentNodes = this.adjacencyList.get(src);
   for (Node<V> node : adjacentNodes) {
    if (node.getName().equals(dest)) {
     weight = node.getWeight();
    }
   }
  }
  return weight;
 }

 /**
  * Get adjacent vertices of the given vertex. This method returns all edges
  * starting from the given vertex. You can call this method iteratively on
  * all vertices to get all edges.
  * 
  * @param vertex
  *            source vertex
  * @return List<V> list of adjacent vertices
  */
 public List<V> getAdjacentVertices(V vertex) {
  List<Node<V>> adjacentNodes = this.adjacencyList.get(vertex);
  List<V> neighborVertex = new ArrayList<>();

  if ((adjacentNodes != null) && !adjacentNodes.isEmpty()) {
   for (Node<V> v : adjacentNodes) {
    neighborVertex.add(v.getName());
   }
  }
  return neighborVertex;
 }

 /**
  * Returns the unmodifiable collection of all vertices of the graph
  * 
  * @return Set<V>
  */
 public Set<V> getAllVertices() {
  return Collections.unmodifiableSet(this.vertices);
 }

 /**
  * Remove vertex and it's relationship from the graph. Also remove vertex
  * from the vertices set
  * 
  * 
  * 1---->2---->3 removeVertex(2) will leave graph as 1 3 It will remove 2 as
  * well as it's relationship
  * 
  * @param vertex
  */
 public boolean removeVertex(V vertex) {
  Objects.requireNonNull(vertex);

  if (!this.vertices.contains(vertex))
   return false;

  Iterator<Entry<V, List<Node<V>>>> itr = this.adjacencyList.entrySet()
    .iterator();

  while (itr.hasNext()) {
   Entry<V, List<Node<V>>> e = itr.next();
   List<Node<V>> vs = e.getValue();
   // remove vertex if it's found as a key in map
   if (vertex.equals(e.getKey())) {
    itr.remove();
   }

   Iterator<Node<V>> listIterator = vs.iterator();
   while (listIterator.hasNext()) {
    Node<V> ver = listIterator.next();
    // remove vertex if it's found as a value in mapped list
    if (vertex.equals(ver.getName())) {
     listIterator.remove();
    }
   }
  }

  // remove vertex from vertices collection
  Iterator<V> itrVertices = this.vertices.iterator();
  while (itrVertices.hasNext()) {
   if (vertex.equals(itrVertices.next())) {
    itrVertices.remove();
    break;
   }
  }
  return true;
 }

 /**
  * Returns graph as a string returns set of edges and vertices
  */
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append("Set of Edges :\n");
  for (V v : this.adjacencyList.keySet()) {
   List<Node<V>> neighbour = this.adjacencyList.get(v);
   for (Node<V> vertex : neighbour) {
    if (vertex.getWeight() != DEFAULT_WEIGHT) {
     sb.append(v + " -- (" + vertex.getWeight() + ")--->"
       + vertex.getName() + "\n");
    } else {
     sb.append(v + " ------->" + vertex.getName() + "\n");
    }

   }
  }
  sb.append("& Set of vertices :" + this.getAllVertices());
  return sb.toString();
 }

 /**
  * Method to unit test
  */
 public static void main(String[] args) {
  Graph<String> graph = new Graph<String>();
  graph.addEdge("BLR", "SFO", 100);
  graph.addEdge("BLR", "HK", 50);
  graph.addEdge("BLR", "LA", 70);
  graph.addEdge("LA", "SFO", 20);
  graph.addEdge("HK", "LA", 60);

  System.out.println(graph.toString());

  System.out.println("\n Path between BLR and LA exists ? :"
    + graph.hasRelationship("BLR", ""));

  System.out.println(" Remove vertex BLR ? " + graph.removeVertex("LA"));
  System.out.println(graph.toString());
 }
}


Output:
Set of Edges :
HK -- (60)--->LA
LA -- (20)--->SFO
BLR -- (100)--->SFO
BLR -- (50)--->HK
BLR -- (70)--->LA
& Set of vertices :[HK, LA, BLR, SFO]

 Path between BLR and LA exists ? :false
 Remove vertex BLR ? true
Set of Edges :
BLR -- (100)--->SFO
BLR -- (50)--->HK

& Set of vertices :[HK, BLR, SFO]