Tuesday, December 15, 2015

Graph in Java

Hello all, today let's see something about the Graphs.

So technically speaking Graph is "A graph in this context is made up of vertices or nodes or points and edges or arcs or lines that connect them. A graph may be un-directed, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. "- Wiki

So now we can say that we understand what a graph is. Right?

Ok let me try to rephrase the things in a different way. Graph is a data structure with Vertices and Edges. Now vertices are the nodes and edges are the connectors between these nodes. A graph can be directed or non directed with weights on edges.

Why is graph theory so important?
    In real world, the graph theory is important in neural network, shortest path between 2 destinations and many more applications of graph are there.

Now coming to the Java, there are number of libraries available to use, but I have used JGraphT and found it pretty descent. The api is available here. You can incorporate it in your project via Maven or including it in the classpath after downloading the jar.

Let us take an example of Graph using JGraphT library.

Code can be found here.

Code snippet
import java.net.MalformedURLException;
import java.net.URL;

import org.jgrapht.DirectedGraph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class DemoGraph {

 public static void main(String[] args) {

  UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph();

  // note undirected edges are printed as: {<v1>,<v2>}
  System.out.println(stringGraph.toString());

  // create a graph based on URL objects
  DirectedGraph<URL, DefaultEdge> hrefGraph = createHrefGraph();
  
  DirectedGraph<Integer, DefaultEdge> ladder = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);

  Integer two = new Integer(2);
  Integer twentyOne = new Integer(21);
  
  ladder.addVertex(two);
  ladder.addVertex(twentyOne);
  
  ladder.addEdge(two, twentyOne);
  
  System.out.println(ladder.getEdgeTarget(ladder.edgesOf(two).iterator().next()));
  
  // note directed edges are printed as: (<v1>,<v2>)
  System.out.println(hrefGraph.toString());
 }

 /**
  * Creates a toy directed graph based on URL objects that represents link
  * structure.
  *
  * @return a graph based on URL objects.
  */
 private static DirectedGraph<URL, DefaultEdge> createHrefGraph() {
  DirectedGraph<URL, DefaultEdge> g = new DefaultDirectedGraph<URL, DefaultEdge>(DefaultEdge.class);

  try {
   URL amazon = new URL("http://www.amazon.com");
   URL yahoo = new URL("http://www.yahoo.com");
   URL ebay = new URL("http://www.ebay.com");

   // add the vertices
   g.addVertex(amazon);
   g.addVertex(yahoo);
   g.addVertex(ebay);

   // add edges to create linking structure
   g.addEdge(yahoo, amazon);
   g.addEdge(yahoo, ebay);
  } catch (MalformedURLException e) {
   e.printStackTrace();
  }

  return g;
 }

 /**
  * Create a toy graph based on String objects.
  *
  * @return a graph based on String objects.
  */
 private static UndirectedGraph<String, DefaultEdge> createStringGraph() {
  UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(
    DefaultEdge.class);

  String v1 = "v1";
  String v2 = "v2";
  String v3 = "v3";
  String v4 = "v4";

  // add the vertices
  g.addVertex(v1);
  g.addVertex(v2);
  g.addVertex(v3);
  g.addVertex(v4);

  // add edges to create a circuit
  g.addEdge(v1, v2);
  g.addEdge(v2, v3);
  g.addEdge(v3, v4);
  g.addEdge(v4, v1);

  return g;
 }

}

No comments:

Post a Comment