Utility for graph related algorithm
This tutorial is just to provide all require utilities for graph related problems and algorithms.
State.java
1 2 3 4 |
public enum State { VISITED, UNVISITED, FOUND } |
Node.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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; }
1 Comment
Comments are closed.