instagram

Utility for graph related algorithm

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

State.java


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) {
		edges.add(new Edge(this, node));
		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 {

	private Node from;
	private Node to;

	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;
	}

}

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;
import java.util.TreeSet;

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() {
		Set<Edge> totalEdges = new HashSet<>();
		for (Node n : vertices) {
			totalEdges.addAll(n.getEdges());
		}
		return totalEdges.size();
	}

	public boolean isThereALoopInGraph() {

		Set<Node> nodes = new TreeSet<>();

		for (Node n : vertices) {
			int count = 0;
		}

		return false;
	}

}

Generating Graph :

IAGE (1)

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;

	}
Share
1 Comment