Skip to main content

Java - Data Structure (Graphs) -part 1


Graphs are data structures rather like trees. In fact, in a mathematical sense, a tree is kind of graph. In computer programming, however, graphs are used in different ways that trees.

Graphs, on the other hand, often have a shape dictated by a physical problem. for example, nodes in a graph may represent cities, while edges may represent airline flight routes between the cities. 

Definitions:
Before going future, we must mention that, when discussing graphs, nodes are called vertices(the singular is vertex).
Adjacency:two vertices are said to be adjacent to one another if they are connected by a single edge.

Path: a path is a sequence of edges. 

connected graphs: a graph is said to be connected if there is at least one path from every vertex to every other vertex. 

non-directed graphs mean the edges don't have a direction, you can go either way on them.

The Adjacency List: the other way to represent edges is with an adjacency list.  Actually, an adjacency list a is an array of list. Each individual list shows what vertices a given vertext is adjacent to. 

Depth-First search: uses a stack to remember where it should go when it reaches a dead end. To carry out the depth-first search, you pick a starting(vertex A) point and then do three things: visit this vertex, push it onto a stack so you can remember it, and mark it so you won't visit it again.

Next you go to any vertex adjacent to A that hasn't yet been visited. Assume the vertices are selected in alphabetical order, so that brings up B. You visit B, mark it , and push it on the stack. Go to an adjacent vertex that hasn't been visited. This leads you to F. We call this process Rule 1.
Rule 1: if possible, visit an adjacent unvisited vertex, mark it , and push it on the stack.

However, you need to do something else, because there are no unvisited vertices adjacent to F. Here's where Rule 2 comes in.
Rule 2: If you can't follow Rule 1, then, if possible, pop a vertex off the stack.

Following this rule, you Pop H off the stack, which brings you back to B, and then A.
A, however does have unvisited adjacent vertices, so you visit the next one, C. But C is the end of the line again, so you pop it and you're back to A. You visit D,G, and I , and then pop them all when you reach the dead end at I. Now you 're back to A. You visit E, and again you're back to A. This time, however, A has no unvisited neighbors, so we pop it off the stack.But now there's nothing left to pop, which brings up Rule 3.
Rule 3: if you can't follow Rule 1 or Rule 2, you're finished.

class StackX{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX(){
st = new int[SIZe];
top = -1;
}

public void push int j)
{
st[++top] = j;
}
}
public int pop(){
return st[top--];
}
public int peek(){return st[top]}
} //end class StackX

class Vertex{
public char label;
public boolean wasVisited = false;
}

class Graph{
private final int MAX_VERTS=20;
private Vertext vertextList[];
init adjmat[][]; // adjacency matrix
StackX theStack;
private int nVerts; // current number of vertices
}

public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix to 0
adjMat[j][k] = 0;
theStack = new StackX();
} // end constructor

public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}

public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}

public int getAdjUnvisitedVertex(int v){
for(int j = 0; j < nVerts; j++){
if(adjMat[v][j] === 1 && vertextList[j].wasVisited == false)
return j;

return -1;
}//end getAdjUnvisitedVertext
}

public void dfs() //depth first search
{
vertextList[0].wasVisited = true;
displayVertext(0);
theStack.push(0);

while(! theStack.isEmpty()){
int v = getAdjUnvisitedVertext(theStack.peek());
if(v == -1) // if no such vertex
theStack.pop();
else{
vertexList[v].wasvisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); //push it
}
} // end while

}

Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Spring - Operations with jdbcTemplate

This class manages all the database communication and exception handling using a java.sql.Connection that is obtained from the provided DataSource. JdbcTemplate is a stateless and threadsafe class and you can safely instantiate a single instance to be used for each DAO.


Use of Callback Methods
JdbcTemplate is based on a template style of programming common to many other parts of Spring. Some method calls are handled entirely by the JdbcTemplate, while others require the calling class to provide callback methods that contain the implementation for parts of the JDBC workflow. This is another form of Inversion of Control. Your application code hands over the responsibility of managing the database access to the template class. The template class in turn calls back to your application code when it needs some detail processing filled in. These callback methods are allowed to throw a java.sql.SQLException, since the framework will be able to catch this exception and use its built-in excepti…