//DFS in java with example, Depth first search(DFS) in java example code, dfs program in java
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.NoSuchElementException;
import weiss.nonstandard.PriorityQueue;
import weiss.nonstandard.PairingHeap;
import weiss.nonstandard.BinaryHeap;
// Used to signal violations of preconditions for
// various shortest path algorithms.
class GraphException extends java.lang.RuntimeException
{
public GraphException(java.lang.String name)
{
super(name);
}
}
// Represents an edge in the graph.
class Edge
{
public Vertex dest; // Second vertex in Edge
public double cost; // Edge cost
public Edge( Vertex d, double c )
{
dest = d;
cost = c;
}
}
// Represents an entry in the priority queue for Dijkstra's algorithm.
class Path implements Comparable
{
public Vertex dest; // w
public double cost; // d(w)
public Path( Vertex d, double c )
{
dest = d;
cost = c;
}
public int compareTo( Object rhs )
{
double otherCost = ((Path)rhs).cost;
return cost < otherCost ? -1 : cost > otherCost ? 1 : 0;
}
}
// Represents a vertex in the graph.
class Vertex
{
public String name; // Vertex name
public List adj; // Adjacent vertices
public double dist; // Cost
public Vertex prev; // Previous vertex on shortest path
public int scratch;// Extra variable used in algorithm
public Vertex( String nm )
{ name = nm; adj = new LinkedList( ); reset( ); }
public void reset( )
{ dist = Graph.INFINITY; prev = null; pos = null; scratch = 0; }
public PriorityQueue.Position pos; // Used for dijkstra2 (Chapter 23)
}
public class Graph
{
public static final double INFINITY = Double.MAX_VALUE;
private Map vertexMap = new HashMap( ); // Maps String to Vertex
/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}
/**
* Driver routine to handle unreachables and print total cost.
* It calls recursive routine to print shortest path to
* destNode after a shortest path algorithm has run.
*/
public void printPath( String destName )
{
Vertex w = (Vertex) vertexMap.get( destName );
if( w == null )
throw new NoSuchElementException( "Destination vertex not found" );
else if( w.dist == INFINITY )
System.out.println( destName + " is unreachable" );
else
{
System.out.print( "(Cost is: " + w.dist + ") " );
printPath( w );
System.out.println( );
}
}
/**
* If vertexName is not present, add it to vertexMap.
* In either case, return the Vertex.
*/
private Vertex getVertex( String vertexName )
{
Vertex v = (Vertex) vertexMap.get( vertexName );
if( v == null )
{
v = new Vertex( vertexName );
vertexMap.put( vertexName, v );
}
return v;
}
/**
* Recursive routine to print shortest path to dest
* after running shortest path algorithm. The path
* is known to exist.
*/
private void printPath( Vertex dest )
{
if( dest.prev != null )
{
printPath( dest.prev );
System.out.print( " to " );
}
System.out.print( dest.name );
}
/**
* Initializes the vertex output info prior to running
* any shortest path algorithm.
*/
private void clearAll( )
{
for( Iterator itr = vertexMap.values( ).iterator( ); itr.hasNext( ); )
( (Vertex)itr.next( ) ).reset( );
}
/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;
while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}
/**
* Single-source weighted shortest-path algorithm.
*/
public void dijkstra( String startName )
{
PriorityQueue pq = new BinaryHeap( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
pq.insert( new Path( start, 0 ) ); start.dist = 0;
int nodesSeen = 0;
while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
{
Path vrec = (Path) pq.deleteMin( );
Vertex v = vrec.dest;
if( v.scratch != 0 ) // already processed v
continue;
v.scratch = 1;
nodesSeen++;
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( "Graph has negative edges" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist +cvw;
w.prev = v;
pq.insert( new Path( w, w.dist ) );
}
}
}
}
/**
* Single-source weighted shortest-path algorithm using pairing heaps.
*/
public void dijkstra2( String startName )
{
PriorityQueue pq = new PairingHeap( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
start.pos = pq.insert( new Path( start, 0 ) ); start.dist = 0;
while ( !pq.isEmpty( ) )
{
Path vrec = (Path) pq.deleteMin( );
Vertex v = vrec.dest;
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( "Graph has negative edges" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
Path newVal = new Path( w, w.dist );
if( w.pos == null )
w.pos = pq.insert( newVal );
else
pq.decreaseKey( w.pos, newVal );
}
}
}
}
/**
* Single-source negative-weighted shortest-path algorithm.
*/
public void negative( String startName )
{
clearAll( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0; start.scratch++;
while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );
if( v.scratch++ > 2 * vertexMap.size( ) )
throw new GraphException( "Negative cycle detected" );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
// Enqueue only if not already on the queue
if( w.scratch++ % 2 == 0 )
q.addLast( w );
else
w.scratch--; // undo the enqueue increment
}
}
}
}
/**
* Single-source negative-weighted acyclic-graph shortest-path algorithm.
*/
public void acyclic( String startName )
{
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
LinkedList q = new LinkedList( );
start.dist = 0;
// Compute the indegrees
Collection vertexSet = vertexMap.values( );
for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); )
{
Vertex v = (Vertex) vsitr.next( );
for( Iterator witr = v.adj.iterator( ); witr.hasNext( ); )
( (Edge) witr.next( ) ).dest.scratch++;
}
// Enqueue vertices of indegree zero
for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); )
{
Vertex v = (Vertex) vsitr.next( );
if( v.scratch == 0 )
q.addLast( v );
}
int iterations;
for( iterations = 0; !q.isEmpty( ); iterations++ )
{
Vertex v = (Vertex) q.removeFirst( );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( --w.scratch == 0 )
q.addLast( w );
if( v.dist == INFINITY )
continue;
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
}
}
}
if(iterations!=vertexMap.size())
throw new GraphException("Graph has a cycle!");
}
public static boolean processRequest(java.io.BufferedReader in,Graph g)
{
String startName=null;
String destName=null;
String alg=null;
try
{
System.out.print("Enter start node:");
if((startName=in.readLine())==null)
return false;
System.out.print("Enter destination node:");
if((destName=in.readLine())==null)
return false;
System.out.print("Enter algorithm (u, d, n, a ):");
if((alg=in.readLine())==null)
return false;
if(alg.equals("u"))
g.unweighted(startName);
else if(alg.equals("d"))
{
g.dijkstra(startName);
g.printPath(destName);
g.dijkstra2(startName);
}
else if(alg.equals("n"))
g.negative(startName);
else if(alg.equals("a"))
g.acyclic(startName);
g.printPath(destName);
}
catch(java.io.IOException e)
{
System.err.println(e);
}
catch(NoSuchElementException e)
{
System.err.println(e);
}
catch(GraphException e)
{
System.err.println(e);
}
return true;
}
/**
* A main routine that:
* 1. Reads a file containing edges (supplied as a command-line parameter);
* 2. Forms the graph;
* 3. Repeatedly prompts for two vertices and
* runs the shortest path algorithm.
* The data file is a sequence of lines of the format source destination.
*/
public static void main(String []args)
{
Graph g=new Graph();
try
{
java.io.FileReader fin=new java.io.FileReader(args[0]);
java.io.BufferedReader graphFile=new java.io.BufferedReader(fin);
java.lang.String line;
while((line=graphFile.readLine())!=null)
{
java.util.StringTokenizer st=new java.util.StringTokenizer(line);
try
{
if(st.countTokens()!=3)
{
System.err.println("Skipping ill-formatted line"+line);
continue;
}
String source=st.nextToken();
String dest=st.nextToken();
int cost=java.lang.Integer.parseInt(st.nextToken());
g.addEdge(source,dest,cost);
}
catch(java.lang.NumberFormatException e )
{
System.err.println("Skipping ill-formatted line"+line);
}
}
}
catch(java.io.IOException e)
{
System.err.println(e);
}
System.out.println("File read");
System.out.println(g.vertexMap.size()+"vertices");
java.io.BufferedReader in=new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
while(processRequest(in,g));
}
}
graph.txt
D C 10
A B 12
D B 23
A D 87
E D 43
B E 11
C A 19
Running Procedure:
c:\>java classname graph.txt
For ieee projects visit our site here
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.NoSuchElementException;
import weiss.nonstandard.PriorityQueue;
import weiss.nonstandard.PairingHeap;
import weiss.nonstandard.BinaryHeap;
// Used to signal violations of preconditions for
// various shortest path algorithms.
class GraphException extends java.lang.RuntimeException
{
public GraphException(java.lang.String name)
{
super(name);
}
}
// Represents an edge in the graph.
class Edge
{
public Vertex dest; // Second vertex in Edge
public double cost; // Edge cost
public Edge( Vertex d, double c )
{
dest = d;
cost = c;
}
}
// Represents an entry in the priority queue for Dijkstra's algorithm.
class Path implements Comparable
{
public Vertex dest; // w
public double cost; // d(w)
public Path( Vertex d, double c )
{
dest = d;
cost = c;
}
public int compareTo( Object rhs )
{
double otherCost = ((Path)rhs).cost;
return cost < otherCost ? -1 : cost > otherCost ? 1 : 0;
}
}
// Represents a vertex in the graph.
class Vertex
{
public String name; // Vertex name
public List adj; // Adjacent vertices
public double dist; // Cost
public Vertex prev; // Previous vertex on shortest path
public int scratch;// Extra variable used in algorithm
public Vertex( String nm )
{ name = nm; adj = new LinkedList( ); reset( ); }
public void reset( )
{ dist = Graph.INFINITY; prev = null; pos = null; scratch = 0; }
public PriorityQueue.Position pos; // Used for dijkstra2 (Chapter 23)
}
public class Graph
{
public static final double INFINITY = Double.MAX_VALUE;
private Map vertexMap = new HashMap( ); // Maps String to Vertex
/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}
/**
* Driver routine to handle unreachables and print total cost.
* It calls recursive routine to print shortest path to
* destNode after a shortest path algorithm has run.
*/
public void printPath( String destName )
{
Vertex w = (Vertex) vertexMap.get( destName );
if( w == null )
throw new NoSuchElementException( "Destination vertex not found" );
else if( w.dist == INFINITY )
System.out.println( destName + " is unreachable" );
else
{
System.out.print( "(Cost is: " + w.dist + ") " );
printPath( w );
System.out.println( );
}
}
/**
* If vertexName is not present, add it to vertexMap.
* In either case, return the Vertex.
*/
private Vertex getVertex( String vertexName )
{
Vertex v = (Vertex) vertexMap.get( vertexName );
if( v == null )
{
v = new Vertex( vertexName );
vertexMap.put( vertexName, v );
}
return v;
}
/**
* Recursive routine to print shortest path to dest
* after running shortest path algorithm. The path
* is known to exist.
*/
private void printPath( Vertex dest )
{
if( dest.prev != null )
{
printPath( dest.prev );
System.out.print( " to " );
}
System.out.print( dest.name );
}
/**
* Initializes the vertex output info prior to running
* any shortest path algorithm.
*/
private void clearAll( )
{
for( Iterator itr = vertexMap.values( ).iterator( ); itr.hasNext( ); )
( (Vertex)itr.next( ) ).reset( );
}
/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;
while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}
/**
* Single-source weighted shortest-path algorithm.
*/
public void dijkstra( String startName )
{
PriorityQueue pq = new BinaryHeap( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
pq.insert( new Path( start, 0 ) ); start.dist = 0;
int nodesSeen = 0;
while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
{
Path vrec = (Path) pq.deleteMin( );
Vertex v = vrec.dest;
if( v.scratch != 0 ) // already processed v
continue;
v.scratch = 1;
nodesSeen++;
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( "Graph has negative edges" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist +cvw;
w.prev = v;
pq.insert( new Path( w, w.dist ) );
}
}
}
}
/**
* Single-source weighted shortest-path algorithm using pairing heaps.
*/
public void dijkstra2( String startName )
{
PriorityQueue pq = new PairingHeap( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
start.pos = pq.insert( new Path( start, 0 ) ); start.dist = 0;
while ( !pq.isEmpty( ) )
{
Path vrec = (Path) pq.deleteMin( );
Vertex v = vrec.dest;
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( "Graph has negative edges" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
Path newVal = new Path( w, w.dist );
if( w.pos == null )
w.pos = pq.insert( newVal );
else
pq.decreaseKey( w.pos, newVal );
}
}
}
}
/**
* Single-source negative-weighted shortest-path algorithm.
*/
public void negative( String startName )
{
clearAll( );
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0; start.scratch++;
while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );
if( v.scratch++ > 2 * vertexMap.size( ) )
throw new GraphException( "Negative cycle detected" );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
// Enqueue only if not already on the queue
if( w.scratch++ % 2 == 0 )
q.addLast( w );
else
w.scratch--; // undo the enqueue increment
}
}
}
}
/**
* Single-source negative-weighted acyclic-graph shortest-path algorithm.
*/
public void acyclic( String startName )
{
Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
LinkedList q = new LinkedList( );
start.dist = 0;
// Compute the indegrees
Collection vertexSet = vertexMap.values( );
for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); )
{
Vertex v = (Vertex) vsitr.next( );
for( Iterator witr = v.adj.iterator( ); witr.hasNext( ); )
( (Edge) witr.next( ) ).dest.scratch++;
}
// Enqueue vertices of indegree zero
for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); )
{
Vertex v = (Vertex) vsitr.next( );
if( v.scratch == 0 )
q.addLast( v );
}
int iterations;
for( iterations = 0; !q.isEmpty( ); iterations++ )
{
Vertex v = (Vertex) q.removeFirst( );
for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
double cvw = e.cost;
if( --w.scratch == 0 )
q.addLast( w );
if( v.dist == INFINITY )
continue;
if( w.dist > v.dist + cvw )
{
w.dist = v.dist + cvw;
w.prev = v;
}
}
}
if(iterations!=vertexMap.size())
throw new GraphException("Graph has a cycle!");
}
public static boolean processRequest(java.io.BufferedReader in,Graph g)
{
String startName=null;
String destName=null;
String alg=null;
try
{
System.out.print("Enter start node:");
if((startName=in.readLine())==null)
return false;
System.out.print("Enter destination node:");
if((destName=in.readLine())==null)
return false;
System.out.print("Enter algorithm (u, d, n, a ):");
if((alg=in.readLine())==null)
return false;
if(alg.equals("u"))
g.unweighted(startName);
else if(alg.equals("d"))
{
g.dijkstra(startName);
g.printPath(destName);
g.dijkstra2(startName);
}
else if(alg.equals("n"))
g.negative(startName);
else if(alg.equals("a"))
g.acyclic(startName);
g.printPath(destName);
}
catch(java.io.IOException e)
{
System.err.println(e);
}
catch(NoSuchElementException e)
{
System.err.println(e);
}
catch(GraphException e)
{
System.err.println(e);
}
return true;
}
/**
* A main routine that:
* 1. Reads a file containing edges (supplied as a command-line parameter);
* 2. Forms the graph;
* 3. Repeatedly prompts for two vertices and
* runs the shortest path algorithm.
* The data file is a sequence of lines of the format source destination.
*/
public static void main(String []args)
{
Graph g=new Graph();
try
{
java.io.FileReader fin=new java.io.FileReader(args[0]);
java.io.BufferedReader graphFile=new java.io.BufferedReader(fin);
java.lang.String line;
while((line=graphFile.readLine())!=null)
{
java.util.StringTokenizer st=new java.util.StringTokenizer(line);
try
{
if(st.countTokens()!=3)
{
System.err.println("Skipping ill-formatted line"+line);
continue;
}
String source=st.nextToken();
String dest=st.nextToken();
int cost=java.lang.Integer.parseInt(st.nextToken());
g.addEdge(source,dest,cost);
}
catch(java.lang.NumberFormatException e )
{
System.err.println("Skipping ill-formatted line"+line);
}
}
}
catch(java.io.IOException e)
{
System.err.println(e);
}
System.out.println("File read");
System.out.println(g.vertexMap.size()+"vertices");
java.io.BufferedReader in=new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
while(processRequest(in,g));
}
}
graph.txt
D C 10
A B 12
D B 23
A D 87
E D 43
B E 11
C A 19
Running Procedure:
c:\>java classname graph.txt
For ieee projects visit our site here
+synchronized+block.jpg)
0 comments:
Post a Comment