0 Replies - 4140 Views - Last Post: 27 January 2011 - 09:59 AM Rate Topic: -----

#1 eZACKe   User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Graph Data Structure - Adjacency Matrix

Posted 27 January 2011 - 09:59 AM

I've been tasked with the problem of implementing a directed graph data structure using and adjacency matrix and an adjacency list representation.

Here's some guidelines:
  • Have to have an Abstract class Graph which both representations will inherit from
  • Fully implement as many methods in the abstract class as possible
  • Efficiency is key


**NOTE: The in and out degree array must be there, the edges and nodes variables must be there. It's part of the assignment requirements.

Right now I've only done the Abstract Class Graph, and the Adjacency Matrix representation of it. Everything I've done so far seems to work upon testing it, but I just don't feel that great about what I've done.

I'm here asking what changes can be made to make it better. More efficient, better structured, anything really. I'm also concerned about which methods should be implemented in the abstract class, and which should be implemented in the children classes.

The list of classes I have include:
  • Graph - Abstract Class
  • Node - Represents the nodes in a graph
  • Edge - Represents the edges in a graph
  • AdjacencyMatrixDirectedGraph - Graph with an underlying Adjacency matrix


And here they are in order:

/**
 * Graph is an abstract class which different types of graphs will inherit from
 * 
 * @author Zack Hine
 * @version 1.0
 */
public abstract class Graph
{
	protected int edges;// number of edges in the graph
	protected int nodes;// number of nodes in the graph

	protected int[] outDegrees;// out-degree of every node
	protected int[] inDegrees;// in-degree of every node

	/**
	 * Return the number of edges contained in the graph
	 * 
	 * @return The number of edges contained
	 */
	protected int numEdges()
	{
		return edges;
	}

	/**
	 * Return the number of nodes contained in the graph
	 * 
	 * @return The number of nodes contained
	 */
	protected int numNodes()
	{
		return nodes;
	}

	/**
	 * Determine whether an edge made up of two nodes exists
	 * 
	 * @param i
	 *            The first node in an edge
	 * @param j
	 *            The second node in an edge
	 * @return true if the edge exists
	 */
	protected boolean existsEdge(int i, int j)
	{
		return existsEdge(new Edge(i, j));// i and j are the Node labels
	}

	/**
	 * Determine the degree of a node
	 * 
	 * @param i
	 *            A node
	 * @return The degree of the node
	 */
	protected int degree(Node i)
	{
		int label = i.getName();// get the label of the node
		return inDegrees[label - 1] + outDegrees[label - 1];// degreee is the
															// total
		// number of edges incident
		// to the vertex
	}

	/**
	 * Determine how many edges are going in to a node
	 * 
	 * @param i
	 *            A node
	 * @return The in-degree of the node
	 */
	protected int inDegree(Node i)
	{
		int label = i.getName();// get the label of the node
		return inDegrees[label - 1];// the label corresponds to a position in
									// the
		// array
	}

	/**
	 * Determine how many edges are going out of a node
	 * 
	 * @param i
	 *            A node
	 * @return The out-degree of the node
	 */
	protected int outDegree(Node i)
	{
		int label = i.getName();// get the label of the node
		return outDegrees[label - 1];// the label corresponds to a position in
										// the
										// array
	}

	abstract protected boolean existsEdge(Edge e);

	abstract protected int[] adjacentVertices(Node i);

	abstract protected boolean areAdjacent(Node i, Node j);

	abstract protected void putEdge(Edge e);

	abstract protected void putEdge(int i, int j);

	abstract protected void removeEdge(Edge e);

	abstract protected void removeEdge(int i, int j);

}




/*
 * Holds the data a node specified in the constructor
 */
public class Node
{
	private int name;// the Node label
	
	public Node(int name)
	{
		this.name = name;
	}
	
	public int getName()
	{
		return name;
	}
	
	public String toString()
	{
		return name + "";
	}
}




/*
 * Holds the data for the edge between two nodes given in the constructor
 */
public class Edge
{
	private int node1, node2;
	
	public Edge(int node1, int node2)
	{
		this.node1 = node1;
		this.node2 = node2;
	}
	
	public int getNode1()
	{
		return node1;
	}
	
	public int getNode2()
	{
		return node2;
	}
	
}




/**
 * A graph data structure represented by an underlying Adjacency Matrix
 * 
 * @author Zack Hine
 * @version 1.0
 */
public class AdjacencyMatrixDirectedGraph extends Graph
{
	int[][] adjacencyMatrix;// the underlying matrix

	/**
	 * Create a graph with as many nodes as the user provides
	 * 
	 * @param numNodes
	 *            The number of nodes the graph will contain
	 */
	public AdjacencyMatrixDirectedGraph(int numNodes)
	{
		adjacencyMatrix = new int[numNodes][numNodes];
		nodes = numNodes;
		inDegrees = new int[numNodes];
		outDegrees = new int[numNodes];
	}

	public void printElement(int a, int B)/>
	{
		System.out.println(adjacencyMatrix[a][b]);
	}

	/**
	 * Determines if an edge e exists in the graph
	 * 
	 * @param e
	 *            An edge
	 * @return true if the edge exists in the graph
	 */
	public boolean existsEdge(Edge e)
	{
		if (adjacencyMatrix[e.getNode1() - 1][e.getNode2() - 1] == 1)
		{
			return true;
		} else
		{
			return false;
		}
	}

	/**
	 * Add an edge e to the graph
	 * 
	 * @param e
	 *            The edge to be added to the graph
	 */
	public void putEdge(Edge e)
	{
		// edge has 2 nodes, which are the 2 vertices
		// putting an edge adds an out-degree to the first node and in-degree to
		// the second node
		adjacencyMatrix[e.getNode1() - 1][e.getNode2() - 1] = adjacencyMatrix[e
				.getNode1() - 1][e.getNode2() - 1] + 1;
		outDegrees[e.getNode1() - 1] = outDegrees[e.getNode1() - 1] + 1;
		inDegrees[e.getNode2() - 1] = inDegrees[e.getNode2() - 1] + 1;

		++edges;
	}

	/**
	 * Add an edge from node i to node j in the graph
	 * 
	 * @param i
	 *            The first node
	 * @param j
	 *            The second node
	 */
	public void putEdge(int i, int j)
	{
		putEdge(new Edge(i, j));
	}

	/**
	 * Deletes an edge e from the graph
	 * 
	 * @param e
	 *            The edge to be removed
	 */
	public void removeEdge(Edge e)
	{
		// edge has 2 nodes, which are the 2 vertices
		// removing an edge minuses an out-degree form the first node and
		// in-degree from the second node
		if (existsEdge(e))
		{
			adjacencyMatrix[e.getNode1() - 1][e.getNode2() - 1] = adjacencyMatrix[e
					.getNode1() - 1][e.getNode2() - 1] - 1;
			outDegrees[e.getNode1() - 1] = outDegrees[e.getNode1() - 1] - 1;
			inDegrees[e.getNode2() - 1] = inDegrees[e.getNode2() - 1] - 1;

			--edges;
		}
	}

	/**
	 * Deletes the edge from node i to node j i the graph
	 * 
	 * @param i
	 *            The first node
	 * @param j
	 *            The second node
	 */
	public void removeEdge(int i, int j)
	{
		removeEdge(new Edge(i, j));
	}

	public int[] adjacentVertices(Node i)
	{
		// not done yet
	}

	public boolean areAdjacent(Node i, Node j)
	{
		// not done yet
	}
}






So what changes can I make?
What I've tested seems to work, but maybe you see something that I missed?

Anything would be helpful!

Thanks!

This post has been edited by eZACKe: 27 January 2011 - 10:03 AM


Is This A Good Question/Topic? 0
  • +

Page 1 of 1