Sample Directed Graph and Topological Sort Code [closed]
Anyone know where I can obtain a sample implementation of a Directed Graph and sample code for performing a topological sort on a directed graph? (preferably in Java)
Here is a simple implementation of the first algorithm from the Wikipedia page on Topological Sort:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
public class Graph {
static class Node{
public final String name;
public final HashSet<Edge> inEdges;
public final HashSet<Edge> outEdges;
public Node(String name) {
this.name = name;
inEdges = new HashSet<Edge>();
outEdges = new HashSet<Edge>();
}
public Node addEdge(Node node){
Edge e = new Edge(this, node);
outEdges.add(e);
node.inEdges.add(e);
return this;
}
@Override
public String toString() {
return name;
}
}
static class Edge{
public final Node from;
public final Node to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge e = (Edge)obj;
return e.from == from && e.to == to;
}
}
public static void main(String[] args) {
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
seven.addEdge(eleven).addEdge(eight);
five.addEdge(eleven);
three.addEdge(eight).addEdge(ten);
eleven.addEdge(two).addEdge(nine).addEdge(ten);
eight.addEdge(nine).addEdge(ten);
Node[] allNodes = {seven, five, three, eleven, eight, two, nine, ten};
//L <- Empty list that will contain the sorted elements
ArrayList<Node> L = new ArrayList<Node>();
//S <- Set of all nodes with no incoming edges
HashSet<Node> S = new HashSet<Node>();
for(Node n : allNodes){
if(n.inEdges.size() == 0){
S.add(n);
}
}
//while S is non-empty do
while(!S.isEmpty()){
//remove a node n from S
Node n = S.iterator().next();
S.remove(n);
//insert n into L
L.add(n);
//for each node m with an edge e from n to m do
for(Iterator<Edge> it = n.outEdges.iterator();it.hasNext();){
//remove edge e from the graph
Edge e = it.next();
Node m = e.to;
it.remove();//Remove edge from n
m.inEdges.remove(e);//Remove edge from m
//if m has no other incoming edges then insert m into S
if(m.inEdges.isEmpty()){
S.add(m);
}
}
}
//Check to see if all edges are removed
boolean cycle = false;
for(Node n : allNodes){
if(!n.inEdges.isEmpty()){
cycle = true;
break;
}
}
if(cycle){
System.out.println("Cycle present, topological sort not possible");
}else{
System.out.println("Topological Sort: "+Arrays.toString(L.toArray()));
}
}
}
An implementation I did based on second alternative on wikipedia page: http://en.wikipedia.org/wiki/Topological_sorting
public class Graph {
Hashtable<Node, ArrayList<Node>> adjList = new Hashtable<Node, ArrayList<Node>>();
ArrayList<Node> nodes = new ArrayList<Node>();
LinkedList<Node> topoSorted;
public Graph() {}
public void add(Node node) {
if (adjList.contains(node)) {
return;
} else {
adjList.put(node, new ArrayList<Node>());
nodes.add(node);
}
}
public void addNeighbor(Node from, ArrayList<Node> list) {
for (Node to: list) {
addNeighbor(from, to);
}
}
public void addNeighbor(Node from, Node to) {
if (!adjList.containsKey(from)) {
add(from);
}
if (!adjList.containsKey(to)) {
add(to);
}
adjList.get(from).add(to);
to.inDegree++;
to.inNodes.add(from);
}
public void remove(Node node) {
for (Node n: nodes) {
for (Node x: adjList.get(n)) {
if (x.equals(node)) removeNeighbor(n, x);
}
}
adjList.remove(node);
nodes.remove(node);
}
public void removeNeighbor(Node from, Node to) {
adjList.get(from).remove(to);
to.inDegree--;
to.inNodes.remove(from);
}
public void resetVisited() {
for (Node node: nodes) {
node.visited = false;
}
}
public boolean hasEdge(Node from, Node to) {
return adjList.get(from).contains(to) ? true : false;
}
/**
* for DAGS only
* @throws Exception
*/
public void topologicalSort() throws Exception {
/* L <-- Empty list that will contain the sorted elements */
topoSorted = new LinkedList<Node>();
/* Use set to keep track of permanently visited nodes
* in constant time. Does have pointer overhead */
HashSet<Node> visited = new HashSet<Node>();
/* while there are unmarked nodes do */
for (Node n: nodes) {
/* select an unmarked node n
* visit(n)
*/
if (!visited.contains(n)) visit(n, visited);
}
}
/* function: visit(node n) */
public void visit(Node node, HashSet<Node> set) throws Exception {
/* if n has a temporary mark then stop (not a DAG) */
if (node.visited) {
throw new Exception("graph cyclic");
/* if n is not marked (i.e. has not been visited) then... */
} else {
/* mark n temporarily [using boolean field in node]*/
node.visited = true;
/* for each node m with an edge n to m do... */
for (Node m: adjList.get(node)) {
/* visit(m) */
if (!set.contains(m)) visit(m, set);
}
/* mark n permanently */
set.add(node);
/* unmark n temporarily */
node.visited = false;
/* add n to head of L */
topoSorted.addFirst(node);
}
}
public void printGraph() {
for (Node node: nodes) {
System.out.print("from: " + node.value + " | to: ");
for (Node m: adjList.get(node)) {
System.out.print(m.value + " ");
}
System.out.println();
}
}
public void instantiateGraph() {
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
addNeighbor(seven, eleven);
addNeighbor(seven, eight);
addNeighbor(five, eleven);
addNeighbor(three, eight);
addNeighbor(three, ten);
addNeighbor(eleven, two);
addNeighbor(eleven, nine);
addNeighbor(eleven, ten);
addNeighbor(eight, nine);
try {
topologicalSort();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for (Node node: topoSorted) {
System.out.print(node.value + " ");
}
}
public class Node {
String value;
boolean visited = false;
int inDegree = 0;
ArrayList<Node> inNodes = new ArrayList<Node>();
public Node (String value) {
this.value = value;
}
}
public static void main(String[] args) {
Graph g = new Graph();
g.instantiateGraph();
}
}