Graphs

Graphs rest at the core of much of computer science. Very often, graph modelling is key to solving algorithmic problems. As a Software Engineer, one needs to have a clear understanding of graphs and, most importantly, how to model real-world problems in terms of graphs. It is of paramount importance to be familiar with a wide range of graph problems; more so than understanding the nuances of how a given specific graph algorithm works. For instance, let's say that you work in a company that is generating tremendous amounts of data and you are considering the options for manipulating it and extracting from it business intelligence related to your application; one option you have is to use a Graph Database. If you go that path, the underlying implementation if the graph database you select will contain a wide range of graph algorithms, which will be used to answer the queries you make against the DB. Being aware how some of the nuances related to graph representations and algorithms will help you decide what is the best way to formulate questions and ask them to the graph DB being used.

Again, for an excellent coverage of graph algorithms check Prof. Skiena's book.

In this and some of our future posts, we will elaborate on graphs in general and some graph algorithmic approaches. The material has been collected and/or summarised from a variety of sources, such as the Internet, books, etc.


 Graphs come in all shapes and colours:

• Undirected vs. Directed
• Wighted vs. Unweighted
• Simple vs. Non-simple; a non-simple graph allows the existence of self loops and multi-edges (more than one edge between a pair of nodes).
• Sparse vs. Dense
• Cyclic vs. Acyclic
• Embedded vs. Topological; a graph is embedded if the vertices comprising the graph are associated with spatial positions. 
• Implicit vs. explicit; an implicit graph is built on-the-fly as it is used.

Graphs are typically implemented based on two different types of data structures: 

1. Adjacency lists: linked lists are used to keep track of the neighbours of each vertex.
2. Adjacency matrices: a two-dimensional matrix, M, is used to indicate if there is an edge between two vertices (M[i][j] = 1), or not (M[i][j] = 0)

Which implementation to use depends on the target problem that needs to be solved; in general, graphs are implemented using adjacency lists.

Below we show an example (simplified, no getters and setters) implementation of a Graph class using an adjacency lists. The following posts in this series will use this implementation. Note that we are using simple classes (i.e. List, not from a java library) because we want to practice the nuances of achieving a graph implementation; in a production-quality implementation we would use other implementations (i.e. ArrayList).

Adjacency-list-based Graph class

package com.medina.toolbox.graphs;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Graph {

 private List edges;
 private List degree;
 private int numVertices;
 private int numEdges;
 private boolean directed;
 
 public Graph(int size, boolean directed) {
  super();  
  edges = new ArrayList(size);
  for (int i = 0; i < size; i++) {
   edges.add(null);
  }
  degree = new ArrayList(size);
  for (int i = 0; i < size; i++) {
   degree.add(0);
  }
  this.directed = directed;
  this.numVertices = size;
  this.numEdges = 0;
 }

 public boolean isDirected() {
  return directed;
 }

 public void setDirected(boolean directed) {
  this.directed = directed;
 }
 
 public EdgeNode getEdges(int i) {
  if (i < edges.size()) {
   return edges.get(i);
  }
  return null;
 }
 
 public Integer getDegree(int v) {
  if (v < degree.size()) {
   return degree.get(v);
  }
  return -1;
 }
 

 public void incDegree(int x) {
  if (x < degree.size()) {
   degree.set(x, degree.get(x) + 1);
  }
 } 

 
 public void insertEdge(int x, int y, double weight, boolean directed) 
       throws IllegalArgumentException {
  
  if (x < 0 || x >= numVertices || y < 0 || y >= numVertices) {
   throw new IllegalArgumentException();
  }
  
  EdgeNode p = new EdgeNode();
  p.weight = 0.0;
  p.x = x;
  p.y = y;
  p.weight = weight;
  p.next = getEdges(x);
  this.edges.set(x, p);   // Insert at front of adjacency list of node x
  this.incDegree(x);
  
  /*
   * If graph is not directed, insert edge (y,x) Insert it with 
   * directed == true, to insert it only once and update the number of edges
   * only by one too
   */
  if (!directed) {
   insertEdge(y, x, weight, true);
  }else {
   this.numEdges += 1;
  }
  
 }
 
 public void printGraph() {
 
  EdgeNode p = null;
  
  for (int i = 0; i < numVertices; i++) {
   
   System.out.printf("%d: ", i);
   
   p = edges.get(i);
   while (p != null) {
    System.out.printf(" %d", p.y);
    p = p.next;
   }
   System.out.println("");
  }
 }
 
 public static Graph readFromFile(String fileName) throws IOException {
   
  FileInputStream fis = new FileInputStream(fileName);
  InputStreamReader isr = new InputStreamReader(fis);
  BufferedReader br = new BufferedReader(isr);
  
  String s = null;
  
  /* Read first graph definition info */
  s = br.readLine();
  String[] fields = s.split(" ");
  int size = Integer.valueOf(fields[0]);
  boolean directed = Boolean.valueOf(fields[1]);
  
  /* Create Graph */
  Graph g = new Graph(size, directed);
  
  /* Read adjacencies in */
  /* Each line must have the form:  */  
  s = br.readLine();
  while (s != null) {
   fields = s.split(" ");
   g.insertEdge(Integer.valueOf(fields[0]), 
                Integer.valueOf(fields[1]), 
                Double.valueOf(fields[2]), 
                directed);
   s = br.readLine();
  }
  br.close();
  
  return g;
 }
 
 public static void main(String[] args) {
  
  Graph g = null;
  try {
   g = Graph.readFromFile("data/MST01.txt");
   g.printGraph();
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
  
 }
}