Utility for graph related algorithm

May 1, 2016July 17, 2018 by omt

This tutorial is just to provide all require utilities for graph related problems and algorithms.

State.java

public enum State {

	VISITED, UNVISITED, FOUND
}

public enum State {

VISITED, UNVISITED, FOUND

}

Node.java

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Node {

	private List<Node> adjacent = new ArrayList<>();
	private String vertex = "";
	private int nodeId = -1;
	private State state = State.UNVISITED;
	private Set<Edge> edges = new HashSet<>();

	public Node(String vertex) {
		this.vertex = vertex;
		setNodeId(vertex.hashCode());
	}

	public void addAdjacent(Node node) {
		Edge e = new Edge(this, node);
		e.setWeight(this.getNodeId() + node.getNodeId());
		edges.add(e);
		adjacent.add(node);
	}

	public Set<Edge> getEdges() {
		return edges;
	}

	public boolean isVisited() {
		return getState() == State.VISITED;
	}

	public boolean isUnvisited() {
		return getState() == State.UNVISITED;
	}

	public boolean isFoundAlready() {
		return getState() == State.FOUND;
	}

	public State getState() {
		return state;
	}

	public void setState(State state) {
		this.state = state;
	}

	public List<Node> getAdjacent() {
		return adjacent;
	}

	public String getVertex() {
		return vertex;
	}

	public int getNodeId() {
		return nodeId;
	}

	public void setNodeId(int nodeId) {
		this.nodeId = nodeId;
	}

}

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class Node {

private List<Node> adjacent = new ArrayList<>();

private String vertex = "";

private int nodeId = -1;

private State state = State.UNVISITED;

private Set<Edge> edges = new HashSet<>();

public Node(String vertex) {

this.vertex = vertex;

setNodeId(vertex.hashCode());

}

public void addAdjacent(Node node) {

Edge e = new Edge(this, node);

e.setWeight(this.getNodeId() + node.getNodeId());

edges.add(e);

adjacent.add(node);

}

public Set<Edge> getEdges() {

return edges;

}

public boolean isVisited() {

return getState() == State.VISITED;

}

public boolean isUnvisited() {

return getState() == State.UNVISITED;

}

public boolean isFoundAlready() {

return getState() == State.FOUND;

}

public State getState() {

return state;

}

public void setState(State state) {

this.state = state;

}

public List<Node> getAdjacent() {

return adjacent;

}

public String getVertex() {

return vertex;

}

public int getNodeId() {

return nodeId;

}

public void setNodeId(int nodeId) {

this.nodeId = nodeId;

}

Edge.java

package com.omt.learn.algo.util.graph;

public class Edge implements Comparable<Edge> {

	private Node from;
	private Node to;
	private int weight = 0;

	public Edge(Node from, Node to) {
		this.from = from;
		this.to = to;
	}

	@Override
	public int hashCode() {
		return from.hashCode() + to.hashCode();
	}

	@Override
	public boolean equals(Object obj) {

		Edge oe = (Edge) obj;

		if ((oe.from == this.from || oe.to == this.from) && (oe.from == this.to || oe.to == this.to)) {
			return true;
		}

		return false;
	}

	public Node getFrom() {
		return from;
	}

	public Node getTo() {
		return to;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	@Override
	public int compareTo(Edge o) {
		if (this.weight == 0 || o.weight == 0) {
			return this.hashCode() - o.hashCode();
		}
		return this.weight - o.weight;
	}

}

package com.omt.learn.algo.util.graph;

public class Edge implements Comparable<Edge> {

private Node from;

private Node to;

private int weight = 0;

public Edge(Node from, Node to) {

this.from = from;

this.to = to;

}

@Override

public int hashCode() {

return from.hashCode() + to.hashCode();

}

@Override

public boolean equals(Object obj) {

Edge oe = (Edge) obj;

if ((oe.from == this.from || oe.to == this.from) && (oe.from == this.to || oe.to == this.to)) {

return true;

}

return false;

}

public Node getFrom() {

return from;

}

public Node getTo() {

return to;

}

public int getWeight() {

return weight;

}

public void setWeight(int weight) {

this.weight = weight;

}

@Override

public int compareTo(Edge o) {

if (this.weight == 0 || o.weight == 0) {

return this.hashCode() - o.hashCode();

}

return this.weight - o.weight;

}

Graph.java

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Graph {

	private List<Node> vertices = new ArrayList<>();

	public void addVertex(Node node) {
		vertices.add(node);
	}

	public List<Node> getVertices() {
		return vertices;
	}

	public int getEdgeCount() {
		return getEdges().size();
	}

	public Set<Edge> getEdges() {
		Set<Edge> totalEdges = new HashSet<>();
		for (Node n : vertices) {
			totalEdges.addAll(n.getEdges());
		}
		return totalEdges;
	}

}

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class Graph {

private List<Node> vertices = new ArrayList<>();

public void addVertex(Node node) {

vertices.add(node);

}

public List<Node> getVertices() {

return vertices;

}

public int getEdgeCount() {

return getEdges().size();

}

public Set<Edge> getEdges() {

Set<Edge> totalEdges = new HashSet<>();

for (Node n : vertices) {

totalEdges.addAll(n.getEdges());

}

return totalEdges;

}

Generating Graph :

public static Graph generateGraph() {

		Graph graph = new Graph();

		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");

		a.addAdjacent(b);
		a.addAdjacent(c);

		b.addAdjacent(d);
		b.addAdjacent(a);

		d.addAdjacent(b);
		d.addAdjacent(e);
		d.addAdjacent(f);

		e.addAdjacent(d);
		e.addAdjacent(f);
		e.addAdjacent(g);

		f.addAdjacent(e);
		f.addAdjacent(d);
		f.addAdjacent(g);

		g.addAdjacent(e);
		g.addAdjacent(f);

		c.addAdjacent(a);
		c.addAdjacent(h);

		h.addAdjacent(c);

		graph.addVertex(a);
		graph.addVertex(b);
		graph.addVertex(c);
		graph.addVertex(d);
		graph.addVertex(e);
		graph.addVertex(f);
		graph.addVertex(g);
		graph.addVertex(h);
		graph.addVertex(i);

		return graph;

	}

omt Lab

Utility for graph related algorithm

Related

1 Comment