Page 1 of 1

Graph Data Structure Tutorial Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 11334
  • View blog
  • Posts: 42,746
  • Joined: 27-December 08

Posted 16 June 2015 - 09:08 AM

This tutorial will discuss implementing a graph data structure in Java. Formally, a graph is an object consisting of a vertex set and an edge set. We denote it G(V, E). For the sake of this tutorial, we restrict attention to an undirected, simple graph. In this graph, we have edges that relate two vertices. There is at most one edge per pair of vertices. So the edge set is: E = { (i, j) : i, j \in V, i != j }.

This definition of a graph is not very intuitive. So let's look at an example.
Attached Image

The labeled points are the vertices of the graph, and the lines between them represent edges. So for example, the points 1 and 2 are vertices, while the line {1, 2} is an edge. An edge represents a relation between two vertices. If two vertices have an edge between them, we refer to these vertices as adjacent. The edge is said to be incident to the vertices it touches.

Graph theory provides a simple way to model a number of problems, such as storing hazardous chemicals, path finding, transportation of goods, and spanning trees. The graph data structure discussed in this tutorial works particularly well for algorithmic purposes, such as with path-finding and spanning tree algorithms.


Let's begin with the Vertex class. A Vertex is a a node in the graph, as described above. The vertex's neighbors are described with an ArrayList<Edge>. The purpose of using the incidence neighborhood (Edges) rather than the adjacency neighborhood (Vertices) was because path-finding and spanning tree algorithms need the edges to function. Note that this implementation does not allow for multiple Edge objects between the same pair of Vertex objects.

import java.util.ArrayList;

/**
 * This class models a vertex in a graph. For ease of 
 * the reader, a label for this vertex is required. 
 * Note that the Graph object only accepts one Vertex per label,
 * so uniqueness of labels is important. This vertex's neighborhood
 * is described by the Edges incident to it. 
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Vertex {

    private ArrayList<Edge> neighborhood;
    private String label;
    
    /**
     * 
     * @param label The unique label associated with this Vertex
     */
    public Vertex(String label){
        this.label = label;
        this.neighborhood = new ArrayList<Edge>();
    }
    
    
    /**
     * This method adds an Edge to the incidence neighborhood of this graph iff
     * the edge is not already present. 
     * 
     * @param edge The edge to add
     */
    public void addNeighbor(Edge edge){
        if(this.neighborhood.contains(edge)){
            return;
        }
        
        this.neighborhood.add(edge);
    }
    
    
    /**
     * 
     * @param other The edge for which to search
     * @return true iff other is contained in this.neighborhood
     */
    public boolean containsNeighbor(Edge other){
        return this.neighborhood.contains(other);
    }
    
    /**
     * 
     * @param index The index of the Edge to retrieve
     * @return Edge The Edge at the specified index in this.neighborhood
     */
    public Edge getNeighbor(int index){
        return this.neighborhood.get(index);
    }
    
    
    /**
     * 
     * @param index The index of the edge to remove from this.neighborhood
     * @return Edge The removed Edge
     */
    Edge removeNeighbor(int index){
        return this.neighborhood.remove(index);
    }
    
    /**
     * 
     * @param e The Edge to remove from this.neighborhood
     */
    public void removeNeighbor(Edge e){
        this.neighborhood.remove(e);
    }
    
    
    /**
     * 
     * @return int The number of neighbors of this Vertex
     */
    public int getNeighborCount(){
        return this.neighborhood.size();
    }
    
    
    /**
     * 
     * @return String The label of this Vertex
     */
    public String getLabel(){
        return this.label;
    }
    
    
    /**
     * 
     * @return String A String representation of this Vertex
     */
    public String toString(){
        return "Vertex " + label;
    }
    
    /**
     * 
     * @return The hash code of this Vertex's label
     */
    public int hashCode(){
        return this.label.hashCode();
    }
    
    /**
     * 
     * @param other The object to compare
     * @return true iff other instanceof Vertex and the two Vertex objects have the same label
     */
    public boolean equals(Object other){
        if(!(other instanceof Vertex)){
            return false;
        }
        
        Vertex v = (Vertex)other;
        return this.label.equals(v.label);
    }
    
    /**
     * 
     * @return ArrayList<Edge> A copy of this.neighborhood. Modifying the returned
     * ArrayList will not affect the neighborhood of this Vertex
     */
    public ArrayList<Edge> getNeighbors(){
        return new ArrayList<Edge>(this.neighborhood);
    }
    
}




Next, we examine the Edge class. An Edge models the adjacency relation between two vertices. So the Edge class has two vertices. In many situations, the notion of an edge weight is also important. Intuitively, the edge weight represents the distance between two vertices. Even in unweighted graphs, it is a commonly accepted notion that traversing two edges bears greater cost than staying at the current vertex. So the Edge class allows for a weight attribute, assuming by convention a uniform weight of 1 if no weight is specified. This allows for treating the graph as "unweighted" in a manner that is still consistent with the preconditions of many common graph algorithms.

It is also important to note that I deviate from a key expectation of the Comparable interface here. The Comparable interface expects that if the compareTo() method returns a value of 0, then the equals() method will return a value of true for the given parameter. I use the compareTo() method to strictly compare Edge weights, while the equals() method simply tests if the Edge references the same pair of Vertices. The design decision has two considerations. The first is to prohibit multiple edges for the same pair of vertices, to which the equals() method contributes. The second consideration is that the compareTo() method only cares about Edge weights in algorithmic considerations.

/**
 * This class models an undirected Edge in the Graph implementation.
 * An Edge contains two vertices and a weight. If no weight is
 * specified, the default is a weight of 1. This is so traversing
 * edges is assumed to be of greater distance or cost than staying
 * at the given vertex.
 * 
 * This class also deviates from the expectations of the Comparable interface
 * in that a return value of 0 does not indicate that this.equals(other). The
 * equals() method only compares the vertices, while the compareTo() method 
 * compares the edge weights. This provides more efficient implementation for
 * checking uniqueness of edges, as well as the fact that two edges of equal weight
 * should be considered equitably in a pathfinding or spanning tree algorithm.
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Edge implements Comparable<Edge> {

    private Vertex one, two;
    private int weight;
    
    /**
     * 
     * @param one The first vertex in the Edge
     * @param two The second vertex in the Edge
     */
    public Edge(Vertex one, Vertex two){
        this(one, two, 1);
    }
    
    /**
     * 
     * @param one The first vertex in the Edge
     * @param two The second vertex of the Edge
     * @param weight The weight of this Edge
     */
    public Edge(Vertex one, Vertex two, int weight){
        this.one = (one.getLabel().compareTo(two.getLabel()) <= 0) ? one : two;
        this.two = (this.one == one) ? two : one;
        this.weight = weight;
    }
    
    
    /**
     * 
     * @param current
     * @return The neighbor of current along this Edge
     */
    public Vertex getNeighbor(Vertex current){
        if(!(current.equals(one) || current.equals(two))){
            return null;
        }
        
        return (current.equals(one)) ? two : one;
    }
    
    /**
     * 
     * @return Vertex this.one
     */
    public Vertex getOne(){
        return this.one;
    }
    
    /**
     * 
     * @return Vertex this.two
     */
    public Vertex getTwo(){
        return this.two;
    }
    
    
    /**
     * 
     * @return int The weight of this Edge
     */
    public int getWeight(){
        return this.weight;
    }
    
    
    /**
     * 
     * @param weight The new weight of this Edge
     */
    public void setWeight(int weight){
        this.weight = weight;
    }
    
    
    /**
     * Note that the compareTo() method deviates from 
     * the specifications in the Comparable interface. A 
     * return value of 0 does not indicate that this.equals(other).
     * The equals() method checks the Vertex endpoints, while the 
     * compareTo() is used to compare Edge weights
     * 
     * @param other The Edge to compare against this
     * @return int this.weight - other.weight
     */
    public int compareTo(Edge other){
        return this.weight - other.weight;
    }
    
    /**
     * 
     * @return String A String representation of this Edge
     */
    public String toString(){
        return "({" + one + ", " + two + "}, " + weight + ")";
    }
    
    /**
     * 
     * @return int The hash code for this Edge 
     */
    public int hashCode(){
        return (one.getLabel() + two.getLabel()).hashCode(); 
    }
    
    /**
     * 
     * @param other The Object to compare against this
     * @return ture iff other is an Edge with the same Vertices as this
     */
    public boolean equals(Object other){
        if(!(other instanceof Edge)){
            return false;
        }
        
        Edge e = (Edge)other;
        
        return e.one.equals(this.one) && e.two.equals(this.two);
    }   
}




Lastly, consider the Graph class implementation. I utilize an incidence list implementation, which is favorable for many (but not all) Graph algorithms. Basic operations of insertion, lookup, and removal are supported for both Vertex and Edge objects. Vertex objects are uniquely identified by their labels, and no two Vertex objects can share the same label. However, there is support to overwrite existing Vertex objects. Note that doing such will remove from the Graph all Edges associated with the existing Vertex.

No equals() method is provided for the Graph class. The notion of Graph equality is referred to as Graph isomorphism. The problem deciding if two Graphs are isomorphic is not known to be in the complexity class P. Therefore, it is not known if a polynomial time algorithm exists to determine if two graphs are isomorphic. For this reason, no equals() method is included to compare the two Graphs.
import java.util.*;

/**
 * This class models a simple, undirected graph using an 
 * incidence list representation. Vertices are identified 
 * uniquely by their labels, and only unique vertices are allowed.
 * At most one Edge per vertex pair is allowed in this Graph.
 * 
 * Note that the Graph is designed to manage the Edges. You
 * should not attempt to manually add Edges yourself.
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Graph {
    
    private HashMap<String, Vertex> vertices;
    private HashMap<Integer, Edge> edges;
    
    public Graph(){
        this.vertices = new HashMap<String, Vertex>();
        this.edges = new HashMap<Integer, Edge>();
    }
    
    /**
     * This constructor accepts an ArrayList<Vertex> and populates
     * this.vertices. If multiple Vertex objects have the same label,
     * then the last Vertex with the given label is used. 
     * 
     * @param vertices The initial Vertices to populate this Graph
     */
    public Graph(ArrayList<Vertex> vertices){
        this.vertices = new HashMap<String, Vertex>();
        this.edges = new HashMap<Integer, Edge>();
        
        for(Vertex v: vertices){
            this.vertices.put(v.getLabel(), v);
        }
        
    }
    
    /**
     * This method adds am edge between Vertices one and two
     * of weight 1, if no Edge between these Vertices already
     * exists in the Graph.
     * 
     * @param one The first vertex to add
     * @param two The second vertex to add
     * @return true iff no Edge relating one and two exists in the Graph
     */
    public boolean addEdge(Vertex one, Vertex two){
        return addEdge(one, two, 1);
    }
    
    
    /**
     * Accepts two vertices and a weight, and adds the edge 
     * ({one, two}, weight) iff no Edge relating one and two 
     * exists in the Graph.
     * 
     * @param one The first Vertex of the Edge
     * @param two The second Vertex of the Edge
     * @param weight The weight of the Edge
     * @return true iff no Edge already exists in the Graph
     */
    public boolean addEdge(Vertex one, Vertex two, int weight){
        if(one.equals(two)){
            return false;   
        }
       
        //ensures the Edge is not in the Graph
        Edge e = new Edge(one, two, weight);
        if(edges.containsKey(e.hashCode())){
            return false;
        }
       
        //and that the Edge isn't already incident to one of the vertices
        else if(one.containsNeighbor(e) || two.containsNeighbor(e)){
            return false;
        }
            
        edges.put(e.hashCode(), e);
        one.addNeighbor(e);
        two.addNeighbor(e);
        return true;
    }
    
    /**
     * 
     * @param e The Edge to look up
     * @return true iff this Graph contains the Edge e
     */
    public boolean containsEdge(Edge e){
        if(e.getOne() == null || e.getTwo() == null){
            return false;
        }
        
        return this.edges.containsKey(e.hashCode());
    }
    
    
    /**
     * This method removes the specified Edge from the Graph,
     * including as each vertex's incidence neighborhood.
     * 
     * @param e The Edge to remove from the Graph
     * @return Edge The Edge removed from the Graph
     */
    public Edge removeEdge(Edge e){
       e.getOne().removeNeighbor(e);
       e.getTwo().removeNeighbor(e);
       return this.edges.remove(e.hashCode());
    }
    
    /**
     * 
     * @param vertex The Vertex to look up
     * @return true iff this Graph contains vertex
     */
    public boolean containsVertex(Vertex vertex){
        return this.vertices.get(vertex.getLabel()) != null;
    }
    
    /**
     * 
     * @param label The specified Vertex label
     * @return Vertex The Vertex with the specified label
     */
    public Vertex getVertex(String label){
        return vertices.get(label);
    }
    
    /**
     * This method adds a Vertex to the graph. If a Vertex with the same label
     * as the parameter exists in the Graph, the existing Vertex is overwritten
     * only if overwriteExisting is true. If the existing Vertex is overwritten,
     * the Edges incident to it are all removed from the Graph.
     * 
     * @param vertex
     * @param overwriteExisting
     * @return true iff vertex was added to the Graph
     */
    public boolean addVertex(Vertex vertex, boolean overwriteExisting){
        Vertex current = this.vertices.get(vertex.getLabel());
        if(current != null){
            if(!overwriteExisting){
                return false;
            }
            
            while(current.getNeighborCount() > 0){
                this.removeEdge(current.getNeighbor(0));
            }
        }
        
        
        vertices.put(vertex.getLabel(), vertex);
        return true;
    }
    
    /**
     * 
     * @param label The label of the Vertex to remove
     * @return Vertex The removed Vertex object
     */
    public Vertex removeVertex(String label){
        Vertex v = vertices.remove(label);
        
        while(v.getNeighborCount() > 0){
            this.removeEdge(v.getNeighbor((0)));
        }
        
        return v;
    }
    
    /**
     * 
     * @return Set<String> The unique labels of the Graph's Vertex objects
     */
    public Set<String> vertexKeys(){
        return this.vertices.keySet();
    }
    
    /**
     * 
     * @return Set<Edge> The Edges of this graph
     */
    public Set<Edge> getEdges(){
        return new HashSet<Edge>(this.edges.values());
    }
    
}




Here is a demo file to illustrate Graph class functionality:
/**
 *
 * @author Michael Levet
 * @date June 09, 2015
 */
public class DemoGraph {
    
    public static void main(String[] args){
        Graph graph = new Graph();
        
        
        //initialize some vertices and add them to the graph
        Vertex[] vertices = new Vertex[5];
        for(int i = 0; i < vertices.length; i++){
            vertices[i] = new Vertex("" + i);
            graph.addVertex(vertices[i], true);
        }
        
        //illustrate the fact that duplicate edges aren't added
        for(int i = 0; i < vertices.length - 1; i++){
            for(int j = i + 1; j < vertices.length; j++){
               graph.addEdge(vertices[i], vertices[j]);
               graph.addEdge(vertices[i], vertices[j]);
               graph.addEdge(vertices[j], vertices[i]);
            }
        }
        
        //display the initial setup- all vertices adjacent to each other
        for(int i = 0; i < vertices.length; i++){
            System.out.println(vertices[i]);
            
            for(int j = 0; j < vertices[i].getNeighborCount(); j++){
                System.out.println(vertices[i].getNeighbor(j));
            }
            
            System.out.println();
        }
        
        //overwritte Vertex 3
        graph.addVertex(new Vertex("3"), true);
        for(int i = 0; i < vertices.length; i++){
            System.out.println(vertices[i]);
            
            for(int j = 0; j < vertices[i].getNeighborCount(); j++){
                System.out.println(vertices[i].getNeighbor(j));
            }
            
            System.out.println();
        }
        
        
        System.out.println("Vertex 5: " + graph.getVertex("5")); //null
        System.out.println("Vertex 3: " + graph.getVertex("3")); //Vertex 3
        
        //true
        System.out.println("Graph Contains {1, 2}: " +
                graph.containsEdge(new Edge(graph.getVertex("1"), graph.getVertex("2"))));
        
        //true
        System.out.println(graph.removeEdge(new Edge(graph.getVertex("1"), graph.getVertex("2")))); 
        
        //false
        System.out.println("Graph Contains {1, 2}: " + graph.containsEdge(new Edge(graph.getVertex("1"), graph.getVertex("2"))));
        
        //false
        System.out.println("Graph Contains {2, 3} " + graph.containsEdge(new Edge(graph.getVertex("2"), graph.getVertex("3"))));
        
        System.out.println(graph.containsVertex(new Vertex("1"))); //true
        System.out.println(graph.containsVertex(new Vertex("6"))); //false
        System.out.println(graph.removeVertex("2")); //Vertex 2
        System.out.println(graph.vertexKeys()); //[3, 1, 0, 4]
        
    }
}



Is This A Good Question/Topic? 0
  • +

Replies To: Graph Data Structure Tutorial

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 10588
  • View blog
  • Posts: 41,042
  • Joined: 12-June 08

Posted 16 June 2015 - 09:14 AM

Does this draw the pretty points and lines?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 11334
  • View blog
  • Posts: 42,746
  • Joined: 27-December 08

Posted 16 June 2015 - 09:23 AM

It does not draw the pretty pictures, I'm afraid. :P
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1