I have a small array of numbers. [4, 1, 2, 5, 3, 6, 8, 7]
The way my graph is set up is that each number in the array is pointing to all numbers larger than it later on in the array. (4 is pointing to 5, 6, 8, and 7. 3 is pointing to 6, 8, 7. Etc.) I input these numbers into the graph, using an adjacency list to map out all the edges. I'm trying to use some sort of Depth First Search method to find the length of the longest path from any starting point in the graph. I'm just having some troubles getting the traversal started and set up, especially since later on I want to use this same graph for a much larger array of random numbers.
Here is my code for my Graph (also the count variable in my DFSUtil is supposed to be used to count the edges on each path, and then I was going to put those into an array or something to keep track of which path had the most edges (longest path)):
import java.util.NoSuchElementException;
public class Graph {
private static final String NEWLINE = System.getProperty("line.separator");
public final int V; // initializing variables and data structures
private int E = 0;
public Bag<Integer>[] adj;
public Graph(int[] numbers) {
try {
this.V = numbers.length;
adj = (Bag<Integer>[]) new Bag[V]; // bag initialized
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>(); // indices are initialized
}
for (int i = 0; i < V; i++) {
adj[i].label = numbers[i];
int j = (i + 1);
while (j < numbers.length) {
if (numbers[i] < numbers[j]) {
addEdge(i, numbers[j]);
}
j++;
}
}
}
catch (NoSuchElementException e) {
throw new IllegalArgumentException("invalid input format in Graph constructor", e);
}
}
public void addEdge(int index, int num) {
E++; // number of edges increases
adj[index].add(num); // indexes into bag
}
public void print() {
for (int i = 0; i < adj.length; i++) {
System.out.print(adj[i].label + ": ");
for (int w : adj[i]) {
System.out.print(w + " ");
}
System.out.println("");
}
}
public int getIndex(int num) {
for (int i = 0; i < adj.length; i++) {
if (adj[i].label == num) {
return num;
}
}
return -1;
}
void DFSUtil(int start)
{
while (start < adj.length) {
System.out.print(start + " ");
int a = 0;
int count = 0;
for (int i = 0; i < adj[start].edges; i++) //iterate through the linked list and then propagate to the next few nodes
{
int j = 0;
for (int num : adj[start]) {
if (j == i) {
a = getIndex(num);
}
j++;
}
count++;
DFSUtil(a);
}
start++;
}
}
void DFS()
{
DFSUtil(0);
}
}
And here is the code for my Bag method:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Bag<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of bag
private Node<Item> end;
private int n; // number of elements in bag
public int label;
public int edges;
public static class Node<Item> {
private Item item;
private Node<Item> next;
public int label;
public int edges;
}
public Bag() {
first = null; // empty bag initialized
end = null;
n = 0;
}
public void add(Item item) {
if (n==0) {
Node<Item> head = new Node<Item>(); // if bag is empty
first = head;
end = head;
head.item = item; // new node both first and end of bag
edges++;
n++;
}
else {
Node<Item> oldlast = end; // old last assigned to end of node
Node<Item> last = new Node<Item>();
last.item = item;
oldlast.next = last; // new node added after old last
end = last;
n++; // size increased
edges++;
}
}
public int size() {
return n;
}
public void print() {
Node<Item> current = first;
for (int i = 0; i < n; i++) { // starting at front of bag
System.out.println(current.item); // prints item, moves to next
current = current.next;
}
}
public Iterator<Item> iterator() {
return new LinkedIterator(first); // returns an iterator that iterates over the items in this bag in arbitrary order
}
public class LinkedIterator implements Iterator<Item> {
private Node<Item> current;
public LinkedIterator(Node<Item> first) {
current = first; // iterator starts at head of bag
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException(); // if there is next item, current is moved to next
Item item = current.item;
current = current.next;
return item; // item is returned
}
}
}
And then this is all I have in my main function:
public static void main(String[] args) {
int[] num = {4, 1, 2, 5, 3, 6, 8, 7};
Graph G = new Graph(num);
G.print();
G.DFS();
}
I've been trying to get some sort of recursive method going for my search, but I'm having troubles getting the logistics down. Any help would be appreciated!
The problem with your void DFSUtil(int start) is that start is not a node of your graph, it's just an index to access your adjacency list and cannot be used to access its neighbors. In your case, you need to use the label to access the neighbor list.
public Bag<Integer> getAdjList(int src) {
Bag<Integer> adjList = null;
for (Bag<Integer> list : adj) {
if (list.label == src) {
adjList = list;
break;
}
}
return adjList;
}
And this adjacency list should be used to access current node neighbors. To get all the paths from a current node start dfs from the current node and backtrack when there are no nodes left to visit. Create an empty list to track the current path, when visiting a node add it to the list and remove it from the list when backtracking.
public void dfs(int src, ArrayList<Integer> curr) {
curr.add(src);
Bag<Integer> srcAdj = getAdjList(src);
if (srcAdj.size() == 0) {
// Leaf node
// Print this path
System.out.println(curr.toString());
}
for (int neighbor : srcAdj) {
dfs(neighbor, curr);
}
curr.remove(curr.size()-1);
}
To get all the paths from all nodes in your graph, start dfs for all the nodes in your graph.
int[] num = {4, 1, 2, 5, 3, 6, 8, 7};
Graph G = new Graph(num);
G.print();
for (int i=0;i<num.length;i++) {
// Print all paths from current node
G.dfs(num[i],new ArrayList<>());
}