Skip to content

Instantly share code, notes, and snippets.

@khayyamsaleem
Created November 25, 2019 23:56
Show Gist options
  • Save khayyamsaleem/ddde143dda83f0536fe907ff74d9a3ba to your computer and use it in GitHub Desktop.
Save khayyamsaleem/ddde143dda83f0536fe907ff74d9a3ba to your computer and use it in GitHub Desktop.
import java.util.*;
/**
* Class to represent an undirected graph as an adjacency list
*/
public class Graph<E>{
private Map<E,List<E>> graph;
/**
* A small utility class to encode a "marker"
* for a node, consisting of its dfsNum and "back"
*/
private static class Pair<E> {
private E dfsnum,back;
Pair(E dfsnum, E back) {
this.dfsnum = back;
this.back = back;
}
@Override
public String toString() {
return String.format("(%s,%s)", dfsnum,back);
}
}
public Graph() {
this.graph = new HashMap<>();
}
/**
* method that adds nodes and edges to our graph
* @param item an item to add to the graph
* @param otherItem item to connect first argument to
*/
public void addEdge(E item, E otherItem) {
if(this.graph.containsKey(item)) {
this.graph.get(item).add(otherItem);
if (this.graph.containsKey(otherItem)) {
this.graph.get(otherItem).add(item);
} else {
this.graph.put(otherItem, new ArrayList<E>(Arrays.asList(item)));
}
} else {
this.graph.put(item, new ArrayList<E>(Arrays.asList(otherItem)));
if (this.graph.containsKey(otherItem)) {
this.graph.get(otherItem).add(item);
} else {
this.graph.put(otherItem, new ArrayList<E>(Arrays.asList(item)));
}
}
}
/**
* marks graph with dfsNum and back values and returns marking
* @param startNode node at which to start the DFS
* @return an association between nodes and markers
*/
public Map<E,Pair<Integer>> markGraph(E startNode) {
Map<E,Pair<Integer>> visited = new HashMap<>();
Stack<E> s = new Stack<>();
// TODO: Determine whether startNode is a connector
// there is some edge case stuff that you might have
// to do here to determine if startNode is a connector
s.push(startNode);
int dfsNum = 0;
while(!s.empty()) {
E current = s.pop();
if (!visited.containsKey(current)) {
visited.put(current, new Pair<Integer>(dfsNum,dfsNum));
} else {
// TODO: Implement logic to update back and assess
// whether or not it meets connector criteria
// this is the scenario in which we've already
// visited a node, and we want to see whether to
// update "back" or to declare that the node is a
// connector
}
if (this.graph.containsKey(current)) {
Iterator<E> it = this.graph.get(current).iterator();
while (it.hasNext()) {
E c = it.next();
if (!visited.containsKey(c)) s.push(c);
}
}
dfsNum++;
}
return visited;
}
@Override
public String toString() {
return this.graph.toString();
}
public static void main(String[] args) {
Graph<Character> g = new Graph<>();
g.addEdge('a','b');
g.addEdge('b','c');
g.addEdge('b','d');
System.out.println("GRAPH: ");
System.out.println(g);
System.out.println();
System.out.println("Marking starting at 'a'");
System.out.println(g.markGraph('a'));
System.out.println();
System.out.println("Marking starting at 'b'");
System.out.println(g.markGraph('b'));
}
}
@khayyamsaleem
Copy link
Author

OUTPUT:

GRAPH:
{a=[b], b=[a, c, d], c=[b], d=[b]}

Marking starting at 'a'
{a=(0,0), b=(1,1), c=(3,3), d=(2,2)}

Marking starting at 'b'
{a=(3,3), b=(0,0), c=(2,2), d=(1,1)}

@khayyamsaleem
Copy link
Author

This is for the graph here:
image

@khayyamsaleem
Copy link
Author

here's the output for another graph.
image

GRAPH:
{a=[b], b=[a, c, d], c=[b, e], d=[b], e=[c, f, g], f=[e], g=[e, h], h=[g]}

Marking starting at 'a'
{a=(0,0), b=(1,1), c=(3,3), d=(2,2), e=(4,4), f=(7,7), g=(5,5), h=(6,6)}

Marking starting at 'b'
{a=(7,7), b=(0,0), c=(2,2), d=(1,1), e=(3,3), f=(6,6), g=(4,4), h=(5,5)}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment