r/javaexamples • • May 02 '15

[Intermediate] Generic Un-directed Graph Implementation with Depth-First Search

1 Upvotes

Generic Un-directed Graph Implementation with Depth-First Search

A Graph is a data structure that is a mathematical model that has tons of real-world uses.

We use a Depth-First Search here to see if the Edges are 'connected'.

Here is a simple implementation in Java that could be extended to include other elements such as Breadth-First Search, Shortest Path, etc.

// Generic Un-directed Graph Implementation with Depth-First Search
// by /u/Philboyd_Studge

import java.util.ArrayList;

@SuppressWarnings("unchecked")

public class Graph<T extends Comparable<T>>
{
	// an enum for the three stated used by the Depth first search
	public enum State { UNVISITED, VISITED, COMPLETE };

	// a list to hold all the vertices
	private ArrayList<Vertex> vertexList;

	// list to hold the edges 
	// not really used for anything
	// but display purposes
	private ArrayList<Edge> edgeList;

	public Graph()
	{
		vertexList = new ArrayList<>();
		edgeList = new ArrayList<>();
	}


	public void add(T x, T y)
	{
		Edge e = new Edge(x, y);
		edgeList.add(e);
	}

	public Vertex findVertex(T v)
	{
		for (Vertex each : vertexList)
		{
			if (each.getValue().compareTo(v)==0)
				return each;
		}
		return null;
	}

	public String toString()
	{
		String retval = "";
		for (Vertex each : vertexList)
		{
			retval += each.toString() + "\n";
		}
		return retval;
	}

	public String edgesToString()
	{
		String retval = "";
		for (Edge each : edgeList)
		{
			retval += each;
		}
		return retval;
	}

	// get first node and call recursive method
	// check if is graph is connected
	public boolean DepthFirstSearch()
	{
		if (vertexList.isEmpty()) return false;

		// get first node
		Vertex root = vertexList.get(0);
		if (root==null) return false;

		// call recursive function
		DepthFirstSearch(root);
		return isConnected();
	}

	// recurse through nodes
	private void DepthFirstSearch(Vertex v)
	{
		v.setState(State.VISITED);

		// loop through neighbors
		for (Vertex each : v.getAdjacentList())
		{
			if (each.getState()==State.UNVISITED)
			{
				DepthFirstSearch(each);
			}
		}
		v.setState(State.COMPLETE);
	}

	// test if DFS returned a connected graph
	public boolean isConnected()
	{
		for (Vertex each : vertexList)
		{
			if (each.getState() != State.COMPLETE)
				return false;
		}
		return true;
	}

	// vertex class
	class Vertex
	{
		T value;
		ArrayList<Vertex> adjacent;
		State state;

		public Vertex(T v)
		{
			value = v;
			adjacent = new ArrayList<>();
			state = State.UNVISITED;
		}

		public State getState()
		{
			return state;
		}

		public void setState(State s)
		{
			state = s;
		}

		public T getValue()
		{
			return value;
		}

		public void addNeighbor(Vertex n)
		{
			adjacent.add(n);
		}

		public ArrayList<Vertex> getAdjacentList()
		{
			return adjacent;
		}

		public String toString()
		{
			String retval = "";
			retval += "Vertex: " + value + ":";
			for (Vertex each : adjacent)
			{
				retval += each.getValue() + " ";
			}
			return retval;
		}


	}

	// edge class
	class Edge
	{
		private Vertex x;
		private Vertex y;

		public Edge(T v1, T v2)
		{
			// check to see if first vertex exists
			x = findVertex(v1);
			if (x == null) 
			{
				// doesn't exist, add new
				x = new Vertex(v1);
				// and add to master list
				vertexList.add(x);
			}
			// same for second vertex
			y = findVertex(v2);
			if (y == null) 
			{
				y = new Vertex(v2);
				vertexList.add(y);
			}
			// add each vertex to the adjacent list for the other
			x.addNeighbor(y);
			y.addNeighbor(x);

		}


		public String toString()
		{
			return "Edge X:" + x.getValue() + " Y:" + y.getValue() + "\n";
		}


	}

	public static void main(String[] args) {
		Graph g = new Graph();
		System.out.println(g.DepthFirstSearch());
		g.add(0,1);
		g.add(0,2);
		g.add(1,3);
		g.add(2,3);
		g.add(2,4);
		g.add(3,5);
		g.add(3,6);
		g.add(5,6);


		System.out.println(g);
		System.out.println(g.edgesToString());
		System.out.println("Graph is connected: " + g.DepthFirstSearch());
		System.out.println();

		g.add(7,3);
		
		System.out.println(g);
		System.out.println(g.edgesToString());
		System.out.println("Graph is connected: " + g.DepthFirstSearch());
		System.out.println();

		Graph<String> gString = new Graph<>();
		gString.add("apple","fruit");
		gString.add("orange","fruit");
		gString.add("broccoli","vegetable");
		gString.add("beef","meat");
		gString.add("meat","food");
		gString.add("fruit","food");
		gString.add("vegetable","food");

		System.out.println(gString);
		System.out.println(gString.edgesToString());
		System.out.println("Graph is conected: " + gString.DepthFirstSearch());

	}
}

Output

false
Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6

Graph is connected: true

Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6 7
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5
Vertex: 7:3

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6
Edge X:7 Y:3

Graph is connected: false

Vertex: apple:fruit
Vertex: fruit:apple orange food
Vertex: orange:fruit
Vertex: broccoli:vegetable
Vertex: vegetable:broccoli food
Vertex: beef:meat
Vertex: meat:beef food
Vertex: food:meat fruit vegetable

Edge X:apple Y:fruit
Edge X:orange Y:fruit
Edge X:broccoli Y:vegetable
Edge X:beef Y:meat
Edge X:meat Y:food
Edge X:fruit Y:food
Edge X:vegetable Y:food

Graph is conected: true

r/javaexamples • • May 02 '15

[Intermediate] A Sorted, Doubly-Linked List using Generics

1 Upvotes

A Sorted, Doubly-Linked List using Generics

Even though Java already has a standard library version of a LinkedList class that is already a doubly-linked list (meaning you can iterate backwards or forwards through the list), many classes in Data Structures will make you learn to roll your own.

A Linked List is a data structure made up of recursive Nodes that 'point' to the next item in the list. A doubly-linked list has nodes that point to the previous item in the list also.

In this example, we are inserting new data items in a sorted position as they are added, so the list is always sorted.

We start by declaring the class in a Generic fashion:

public class SortedDoubleLinkedList<E extends Comparable<E>>

Generic means that it can take any non-primitive type as an argument, and will still do the same thing. We can make a list of Strings, Integers, Arrays, or any user-defined class. In the above definition, E becomes the variable name for our class type. the extends comparable<E> is there for the sorting aspect, as we need to be able to compare two of the supplied types for sorting purposes. If you want to make a list of objects, you need to make sure the class implements Comparable and overrides compareTo (More on that later).

Now we define our Node class (I am using an inner class for this)

class Node
{
	private E value;
	private Node next;
	private Node previous;

	public Node(E value, Node next, Node previous)
	{
		this.value = value;
		this.next = next;
		this.previous = previous;

	}

	public E getValue() { return value;	}
	public void setValue(E value) { this.value = value; }
	public Node getNext() { return next; }
	public void setNext(Node node) { this.next = node; }
	public Node getPrevious() { return previous; }
	public void setPrevious(Node node) { this.previous = node; }


}

Each Node instance has itself two Node type member variables, that point to the next or previous Node. We will define two special nodes, head and tail that make the first and last items in the list. These make for special conditions when adding or removing nodes. Note our referencing data type 'E' for the actual data value. Then we add getters/setters for each member variable.

So we define our class like this:

public class SortedDoubleLinkedList<E extends Comparable<E>>
{
	// Nodes for the first and last element
	Node head;
	Node tail;

	// list size
	int length;

	public SortedDoubleLinkedList() 
	{
		this.length = 0;
	}

We onle need three member variables, one to keep track of the head (or first or root) of the list, one for the tail or last or end) of the list, and one that keeps track of the size of the list.

Now to define our add() method, which uses an insertion sort.

// add function that inserts elements sorted
public void add(E value)
{
	// first insert
	if (length==0)
	{
		head = new Node(value, null, null);
		tail = head;
		length++;
		return;
	}
	else
	{
		if (value.compareTo(head.getValue()) < 0)
		{
			// insert before head, make new head
			// set next to head, previous to null
			Node newNode = new Node(value, head, null);
			// point old head previous to new node
			head.setPrevious(newNode);
			// make new node head
			head = newNode;
			length++;
			return;
		}
		else
		{
			Node current = head.getNext();
			while (current != null)
			{
				if (value.compareTo(current.getValue()) <= 0)
				{
					// insert before current
					// make new nodes next = current, previous = current.previous
					Node newNode = new Node(value, current, current.getPrevious());
					// point node before insert's next to newnode
					current.getPrevious().setNext(newNode);
					// make new node previous to current
					current.setPrevious(newNode);
					length++;
					return;
				}
				current = current.getNext();
			}

			// add to tail
			Node newNode = new Node(value, null, tail);
			tail.setNext(newNode);
			tail = newNode;
			length++;
			return;
		}
	}
}

Now we can define a `toString() function that iterates through the list:

public String toString()
{
	String result = "";
	Node current = head;
	result += "Count = " + length + "\n";
	while (current != null)
	{
		result += "" + current.getValue().toString() + "\n";
		current = current.getNext();
	}
	return result;
}

And one backwards:

public String toStringDescending()
{
	String result = "";
	Node current = tail;
	result += "Count = " + length + "\n";
	while (current != null)
	{
		result += "" + current.getValue().toString() + "\n";
		current = current.getPrevious();
	}
	return result;

}

And one recursive:

// recursive display functions
public String toStringRecursive()
{
	return toStringRecursive(head);
}

public String toStringRecursive(Node node)
{
	if (node==null) return "";
	String retval = node.getValue().toString() + "\n";
	return retval + toStringRecursive(node.getNext());
}

(to make a recursive descending function, just change head to tail and change getNext() to getPrevious())

Adding some other functions, such as a remove(), a get-by-index, a find() and contains() and more, here is the final code:

on Gist, as the code is getting pretty long, along with a test program, and a test class to use for objects

Our test class for objects is an updated version of the Inventory class I have used in several examples, in this case it is updated to use the Comparable interface, so the insertion sort will work properly, based on the member field 'Item':

public class Inventory implements Comparable<Inventory>
{
	private String item;
	private int qty;
	private float price;

	public Inventory(String item, int qty, float price)
	{
		this.item = item;
		this.qty = qty;
		this.price = price;
	}

	public String getItem()
	{
		return item;
	}

	public float getTotal()
	{
		return qty * price;
	}

	public String toString()
	{
		return "===================\nItem: " + item + "\n" + "Quantity: " + qty + "\n"
					+ "Price: " + price + "\n====================\n";
	}

	public String toCSVString()
	{
		return item + "," + qty + "," + price;
	}

	@Override
	public int compareTo(Inventory obj)
	{
		return this.item.compareTo(obj.getItem());
	}
}

Here is the output from TestDLL.java:

List in  order:
Count = 6
0
123
234
234
3455
5000

List in descending order:
Count = 6
5000
3455
234
234
123
0

List contains item value of '3455' = true
Removing an item
List contains item value of '3455' = false
List in order:
Count = 5
0
123
234
234
5000

First:0
Last:5000
List of strings
Count = 3
Argue
Fish
Meat

List contains 'Fish' = true

List of doubles:
3.1415967
27.3
120.003


Object list:
Count = 4
===================
Item: Alphabet Soup
Quantity: 100
Price: 0.99
====================

===================
Item: Maple Syrup
Quantity: 20
Price: 5.99
====================

===================
Item: Purple Suit
Quantity: 5
Price: 199.99
====================

===================
Item: Quixotic Journey
Quantity: 10
Price: 20.0
====================


Count = 4
===================
Item: Quixotic Journey
Quantity: 10
Price: 20.0
====================

===================
Item: Purple Suit
Quantity: 5
Price: 199.99
====================

===================
Item: Maple Syrup
Quantity: 20
Price: 5.99
====================

===================
Item: Alphabet Soup
Quantity: 100
Price: 0.99
====================


Object at index 0 =
===================
Item: Alphabet Soup
Quantity: 100
Price: 0.99
====================

Remove object at index 1
Count = 3
===================
Item: Alphabet Soup
Quantity: 100
Price: 0.99
====================

===================
Item: Purple Suit
Quantity: 5
Price: 199.99
====================

===================
Item: Quixotic Journey
Quantity: 10
Price: 20.0
====================

You could add a Binary Search Tree to make the find() method much faster for large amounts of data.


r/javaexamples • • Sep 16 '24

Object Oriented Programming Example in Java

0 Upvotes

Here is a simple example in Java to understand the object oriented programming better:

https://javarevisited.blogspot.com/2010/10/fundamentals-of-object-oriented.html


r/javaexamples • • Sep 06 '24

7 best practices Java developers can follow while dealing with passwords

0 Upvotes

I wrote an article about best practices Java developers can follow while dealing with passwords or sensitive information in Java application - https://javarevisited.blogspot.com/2012/05/best-practices-while-dealing-with.html


r/javaexamples • • Sep 30 '23

Integer ABS - Programming Puzzle of the week

0 Upvotes

The calculation of absolute value is a basic arithmetic operation. In the latest episode of Java Puzzle of the Week 🧩, we are checking if it can be calculated correctly for every value of the Integer type.

https://www.youtube.com/watch?v=ET8jSVskBWM&list=PL8NC5lCgGs6MTxHSPdqpAjtXhs66cZgRL


r/javaexamples • • May 20 '22

How to create and use a jar file in Eclipse

0 Upvotes

A video on Creating and using a jar file in Command-Line is OUT NOW!!!!

You can check out the video here.


r/javaexamples • • May 20 '22

Question for the Day: (Please post your answers in the comments below)

0 Upvotes

What does the following code output when run as java Duck Duck

Goose?

  1. public class Duck {

public void main(String[] args) {

for (int i = 1; i <= args.length; i++)

System.out.println(args[i]);

} }

a) Duck Goose

b) Duck ArrayIndexOutOfBoundsException

c) Goose

d) Goose ArrayIndexOutOfBoundsException

e) None of the above


r/javaexamples • • May 11 '22

Java Examples

0 Upvotes

If you are looking for examples of various concepts of Java. check out the below youtube channel: Youtube/ Deep Diving in Java with Kosha.


r/javaexamples • • Jul 28 '21

How to create JcomboBox in java

0 Upvotes

JComboBox of javax.swing inherits JComponent class.

The following are ways to create JComboBox in java.

  1. JComboBox jcbox=new JComboBox();

  2. JComboBox jcbox=new JComboBox(Object[] items);

  3. JComboBox jcbox=new JComboBox(Vector<?> items)


r/javaexamples • • May 28 '20

Top Java Development Companies & Java Developers 2019

0 Upvotes

Software Applications being an amicable part of the business are being deployed at every end of business irrespective of its size and aid in capturing a larger customer base as well as helps in enforcing the accurate seamless within the company operations.

They are also top-notch, reliable and sophisticated solutions and services thus, since you are reading it, it is safe to say you are looking forward to the software development company.

Websites are the pool of endless opportunities and they deliver an interactive way to connect with clientele.

When we think of robust java developed websites, automatically we are channelized to think about the various dimensions that are important to nurture in our minds  – like the market for website development, various technologies, development cost, expert software development company, etc.


r/javaexamples • • Oct 11 '19

Java Behavioral Design Patterns – Interpreter Design Pattern

0 Upvotes

The Interpreter design pattern is one of the behavioral design patterns that give specification about how to evaluate sentences in a language.

Below article helps you understand the interpreter pattern with a simple example.

You can download the Source Code from their GitHub repository.

https://www.opencodez.com/java/interpreter-design-pattern.htm


r/javaexamples • • Apr 25 '19

Java concurrent API - CountDownLatch

0 Upvotes

Understanding CountDownLatch with examples.

CountDownLatch


r/javaexamples • • Mar 13 '19

Static Nested Class in Java | Uses & Example Programs

0 Upvotes

When an inner class is defined with static modifier inside the body of another class, it is known as a static nested class in Java. https://www.scientecheasy.com/2019/03/static-nested-class-in-java.html


r/javaexamples • • Mar 03 '19

Want to know concepts related to null in java??

0 Upvotes

We all are familiar with null in java..but most of us don't know what exactly is null. To know the concepts related to null watch this

https://youtu.be/zsflcFD2sW8


r/javaexamples • • May 23 '18

Java Program to Compute Average Mark of Students

0 Upvotes

r/javaexamples • • May 12 '22

which one of the following topics would you like to see a video on

0 Upvotes
7 votes, May 13 '22
1 How to create a jar file in eclipse
3 How to create a jar file from java console
3 How to compile and run code from java console

r/javaexamples • • Sep 12 '20

Is Varargs a datatype in java? | Varargs vs Array | JavaBeam |

0 Upvotes

r/javaexamples • • Jun 07 '22

How to Print Pyramid Pattern in Java? Program Example

0 Upvotes