depth first search tree
Hi,
I have stored some states in a vector (States are numbers). In my code i have printed out the parent nodes, the 2 elements after the parent nodes are there child.
The element placed at position 0 in the vector is the root.I do not know how to implement a depth first search tree to address unreachable node. In this case, parent node 5 is unreachable, from other nodes. But i do not know how to do this. I have spent ages reading tutorials/ book, but i cant seem to convert this knowledge into java. My code is very short and therefore easy to understand
import java.awt.*;
import java.util.*;
publicclass Vec{
publicstaticvoid main(String argv[]){
Vec v =new Vec();
v.remove();
}//End of main
publicvoid remove(){
Vector mv =new Vector();
//Note how a vector can store objects
//of different types
mv.addElement(1);// root and parent node of 2 elements below
mv.addElement(2);// child of above
mv.addElement(1);// child of above
mv.addElement(2);// parent of 2 elements below
mv.addElement(4);
mv.addElement(2);
mv.addElement(3);// parent of 2 elements below
mv.addElement(1);
mv.addElement(3);
mv.addElement(4);// parent of 2 elements below
mv.addElement(3);
mv.addElement(4);
mv.addElement(5);// parent of 2 elements below
mv.addElement(2);
mv.addElement(4);
// below identifys the parent nodes for you, but doesnt store them as parent nodes
for(int i=0; i< mv.size(); i++){
if (i % 3 == 0)
{
System.out.println(mv.elementAt(i));
}
}
}//End of amethod
}
[2826 byte] By [
javaaaa] at [2007-11-26 17:55:13]
# 1
The below statement calculates the parent index (for root is negative)int parentIndex = (i - 1) / 2;
# 2
This gives me the wrong answer, thats why I defined the parent node as mod 3. Because parent nodes are every three positions.int parentIndex = (i - 1) / 2;
# 3
Aren't you confusing a (directed) graph with a tree? Could you draw your tree/graph? Why do you use a vector for this and not a Node class which holds references to other Node's (it's children)?
# 4
here is the tree1 /\12 / \ 24/ \43 / \1 3Therefore node 5 is unreachable.
# 5
here is the tree1 /\12 / \ 24/ \43 / \1 3Therefore node 5 is unreachable.
# 6
> here is the tree
>
> ...
>
> Therefore node 5 is unreachable.
Ah ok, there are double values in the tree. But still, why do you not go for an approach like this:
class Tree {
private Node root;
private int size;
public Tree() {
root = null;
size = 0;
}
public void add(Node node) {
// your code
}
// your code
}
class Node {
private int value;
private Node left;
private Node right;
public Node(int v) {
value = v;
left = right = null;
}
// your code
}
That Vector approach is not the way to go. Seriously.
# 7
Prometheuzz, thanks for your reply.ok, ill shall try it the way you suggested. If I have any problems, do you mind if I ask for your assistance?
# 8
> Prometheuzz, thanks for your reply.> > ok, ill shall try it the way you suggested. If I> have any problems, do you mind if I ask for your> assistance?Sure, no problem. Post back here if you run into problems.
# 9
As I am dealing with directed graphs (nodes and edges), how can I represent that some nodes loop to themselves. Because, i am getting an error that a PARENT CANNOT BE A CHILD! (ancestor)eg. from the tree, some nodes are chidren of their own.
# 10
Ah ok, it's a graph and not a tree. In that case don't use the tree-code I posted, but model your graph as an adjacency matrix (AM) [1]. The AM for the graph you posted in reply #5 would look like this:
Node | 1 2 3 4 5
--+--
1 | 1 1 0 0 0
|
2 | 0 1 0 1 0
|
3 | 1 0 1 0 0
|
4 | 0 0 1 1 0
|
5 | 0 1 1 0 0
You can implement this by using a simple 2D array of integers like this:class Graph {
private int[][] adjacencyMatrix;
public Graph(int numNodes) {
adjacencyMatrix = new int[numNodes][numNodes];
}
public void addEdge(int from, int to) {
adjacencyMatrix[from-1][to-1] = 1;
}
public boolean isReachable(Integer start, Integer goal) {
// your algorithm here
// ...
return false;
}
public String toString() {
StringBuilder strb = new StringBuilder();
for(int i = 0; i < adjacencyMatrix.length; i++) {
int[] row = adjacencyMatrix[i];
strb.append((i+1)+" | ");
for(int j = 0; j < row.length; j++) {
strb.append(adjacencyMatrix[i][j]+" ");
}
strb.append('\n');
}
return strb.toString();
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(1, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 2);
graph.addEdge(2, 4);
graph.addEdge(3, 1);
graph.addEdge(3, 3);
graph.addEdge(4, 3);
graph.addEdge(4, 4);
graph.addEdge(5, 2);
graph.addEdge(5, 3);
System.out.println("Adjacency Matrix:\n"+graph);
System.out.println("Is node 5 reachable from node 1? "+
graph.isReachable(new Integer(1), new Integer(5))); // should be false
System.out.println("Is node 1 reachable from node 5? "+
graph.isReachable(new Integer(5), new Integer(1))); // should be true: a path exists from 5 -> 3 -> 1 and 5 -> 2 -> 4 -> 3 -> 1
}
}
Good luck.
[1]
http://en.wikipedia.org/wiki/Adjacency_matrix
http://mathworld.wolfram.com/AdjacencyMatrix.html
# 11
wow thanks! :)This means that my graph can have many edges right? (thats what i need)
# 12
> wow thanks! :)> > This means that my graph can have many edges right?> (thats what i need)Yes, every node in your graph can be connected to every other node in it. Read the link(s) I posted earlier about the adjacency matrix.
# 13
Ok, but another question.
My edges are labelled, i,e, if every node has 2 edges, then the label will be a,b,...3 edges the label are a,b,c... etc.
there in this case, is it possible to have the matrix:
ab
_
1 | 12
2 | 24
3 | 13
4 | 43
5 | 24
How will that be done?
# 14
FYIAlso, node 1, is always the ROOT NODE, therefore, the "isreachable" method tracks down nodes that arent reachable from node 1. Not the other way around.
# 15
> ...> How will that be done?Replace the 1's with a, b or c in the AM.
# 16
> FYI
>
> Also, node 1, is always the ROOT NODE, therefore, the
> "isreachable" method tracks down nodes that arent
> reachable from node 1. Not the other way around.
Well then you don't use it as I proposed. Instead of a start and goal parameter, you only use the goal parameter and always work from node 1:
public boolean isReachable(Integer goal) {
// your algorithm here
}
# 17
prometheuzz, I am finding it difficult to program what states are unreachable. Could you please advise/ help me.
I know that I have to define the root node, which is always node 1, and from there I do not know how to scan the 1's recusively to see what nodes are unreachable.
I appreciate your help.
# 18
> prometheuzz, I am finding it difficult to program
> what states are unreachable. Could you please
> advise/ help me.
Sure, but what have you tried yourself?
> I know that I have to define the root node, which is
> always node 1, and from there I do not know how to
> scan the 1's recusively to see what nodes are
> unreachable.
>
> I appreciate your help.
If you have problems doing it recursively, just do it iteratively. Here is such a way:
Keep track of a set of nodes you have visited and a stack which will hold the nodes you have not yet visited (in the beginning the stack will only hold node 1, of course). Now keep looping while there are still nodes on your stack. For each node on the stack, collect it's neighbours. Fo each of those neighbours check if it is the goal-node. If a neighbour-node is not the goal AND it is not present in the set of visited nodes then push it on the stack.
# 19
Hi prometheuzz,
This is what ive done so far, BUT, i cannot seem to get it to acknowledge that only STATE 5 IS UNREACHABLE. It doesnt even acknolwedge state/node 5 and is giving me the wrong answer!
:s
class Graph {
private int[][] adjacencyMatrix;
private intnumStates;
private int[]finalStates;
private intnumFinalStates;
private int[]visited;
private intnumVisited;
private int[]notVisited;
private intnumnotVisited;
public Graph(int numNodes, int numFinals) {
adjacencyMatrix = new int[numNodes][numNodes];
finalStates = new int[numFinals];
visited = new int[numNodes];
notVisited = new int[numNodes];
numFinalStates = 0;
numStates = numNodes;
}
public void addEdge(int from, int to) {
adjacencyMatrix[from-1][to-1] = 1;
}
public void addEdge(int from, int to, boolean isFinal) {
adjacencyMatrix[from-1][to-1] = 1;
if (isFinal) {
finalStates[numFinalStates++] = to;
}
}
public boolean isReachable(Integer start, Integer goal) {
if (adjacencyMatrix[start-1][goal-1] == 1)
return true;
else
return false;
}
public String toString() {
StringBuilder strb = new StringBuilder();
for(int i = 0; i < adjacencyMatrix.length; i++) {
int[] row = adjacencyMatrix[i];
strb.append((i+1)+" | ");
for(int j = 0; j < row.length; j++) {
strb.append(adjacencyMatrix[i][j]+" ");
}
strb.append('\n');
}
return strb.toString();
}
public static void main(String[] args) {
Graph graph = new Graph(5,2);
graph.addEdge(1, 1, true);
graph.addEdge(1, 2);
graph.addEdge(2, 2);
graph.addEdge(2, 4, true);
graph.addEdge(3, 1);
graph.addEdge(3, 3);
graph.addEdge(4, 3);
graph.addEdge(4, 4);
graph.addEdge(5, 2);
graph.addEdge(5, 3);
System.out.println("Adjacency Matrix:\n"+graph);
//for (int n=1; n<numStates; n++)
for (int n=1; n><graph.numStates; n++)
graph.notVisited[n] = n;
graph.visited[graph.numVisited++] = 1;
for (int x=1; x><graph.numStates; x++) {
if (graph.isReachable(1,graph.notVisited[x]))
System.out.println("1," + x + " is reachable");
else
System.out.println("1," + x + " is not reachable");
}
/*
System.out.println("Is node 5 reachable from node 1? "+
graph.isReachable(new Integer(1), new Integer(5))); // should be false
System.out.println("Is node 1 reachable from node 5? "+
graph.isReachable(new Integer(5), new Integer(1))); // should be true: a path exists from 5 -> 3 -> 1 and 5 -> 2 -> 4 -> 3 -> 1
*/
}
}
# 20
> ...
> private intnumStates;
>private int[]finalStates;
> private intnumFinalStates;
>private int[]visited;
> private intnumVisited;
>private int[]notVisited;
> private intnumnotVisited;
> ...
You don't need alll those variables. You only need a stack and a set inside your public boolean isReachable(...) method.
Use the classes from the java.util package for that, not your own arrays-approach!
Stack: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html
HashSet: http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashSet.html
Here is the logic (again) which should be implemented in your isReachable(...) method:
Keep track of a set of nodes you have visited and a stack which will hold the nodes you have not yet visited (in the beginning the stack will only hold node 1, or the start node, of course). Now keep looping while there are still nodes on your stack. For each node on the stack, collect it's neighbours. For each of those neighbours check if it is the goal-node. If a neighbour-node is not the goal AND it is not present in the set of visited nodes then push it on the stack.
# 21
> ...
> public boolean isReachable(Integer start, Integer goal) {
>
>if (adjacencyMatrix[start-1][goal-1] == 1)
>return true;
>else
>return false;
>}
> ...
Right now you're only checking if there's a direct link between the start- and goal node. You'll have to traverse the neighbours from the start node as well.
# 22
As you're already using matrix form, it may be easier to use a reachability matrix where
reachability_1 := adjacencyMatrix;
reachability_(n+1) := if ( reachability_(n) != 0) then reachability_(n) else
| else if (reachability_(n) * adjacencyMatrix != 0 ) then n else 0;
each time you multiply by the adjacencyMatrix it gives non-zeros in sites reachable by one-more step.
As the maximum length of a path is one which passes through all vertices, the reachability matrix will stop changing before n > number of vertices.
So you your graph, reachability may be represented by:
1 | 1 1 3 2 0
2 | 3 1 2 1 0
3 | 1 2 1 2 0
4 | 2 2 1 1 0
5 | 2 1 1 2 0
For large matrices, I believe there are related eigen value methods (with a different form of reachability - not giving number of hops).
For small vertices (<=64 in Java, <=128 in modern C++), you can use single integers to represent the rows as bitmasks, and calculate the products in O(N^2); using arrays it's O(N^3).
A more interesting example may be one where there's a 3->5 link but nothing to 3, so the matrix has not got an obvious column of zeros (indicating something not reachable from anything), but still has vertices unreachable from 1:
Adjacency Matrix:
1 | 1 1 0 0 0
2 | 0 1 0 1 0
3 | 1 0 0 0 1
4 | 0 1 0 1 0
5 | 0 1 1 0 0
reachabilityMatrix:
1 | 1 1 0 2 0
2 | 0 1 0 1 0
3 | 1 2 2 2 1
4 | 0 1 0 1 0
5 | 2 1 1 2 2
1,1 is reachable
1,2 is reachable
1,3 is not reachable
1,4 is reachable
1,5 is not reachable
Pete
# 23
That should be O(N^3) and O(N^4) - one way you're doing M^N of an NxN matrix, each element taking N multiplications to calculate, the other way you're saving the N per element by replacing it with a binary and and a test for non-zero.Pete
