Code from text for graph algorithms
To do… implement weighted graph i/o in abstractgraph and show kruskal and prim
package javatext;
public class Edge {
int source,dest;
double weight;
public double getWeight()
{
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public Edge(int source, int dest,
double weight) {
super();
this.source = source;
this.dest = dest;
this.weight = weight;
}
public int getSource()
{
return source;
}
public void setSource(int source) {
this.source = source;
}
public int getDest()
{
return dest;
}
public void setDest(int dest)
{
this.dest = dest;
}
public Edge(int s,int d){
this.source = s;
this.dest = d;
this.weight = 1;
}
}
package javatext;
import java.util.*;
public interface Graph {
int getNumVertices();
boolean isDirected();
void insert(Edge edge);
boolean isEdge(int s,int d);
Edge getEdge(int s,int d);
Iterator<Edge> edgeIterator(int c);
}
package javatext;
import java.util.*;
public abstract class AbstractGraph
implements Graph{
private int numVertices;
private boolean directed;
public AbstractGraph(int numVertices,
boolean directed) {
super();
this.numVertices = numVertices;
this.directed = directed;
}
public void setNumVertices(int n){
numVertices=n;
}
public int getNumVertices()
{
// TODO Auto-generated
method stub
return numVertices;
}
public boolean isDirected()
{
// TODO Auto-generated
method stub
return directed;
}
public void loadEdgesFromFile(Scanner
scan){
//this code is a
text exercise… this version defaults to unweighted
graph
Scanner
lineScanner;
while(scan.hasNext()){
// String line=scan.nextLine();
// System.out.println(line);
// lineScanner=new Scanner(line);
int s=scan.nextInt();
int d=scan.nextInt();
double w=1;
// if(lineScanner.hasNext())
// { w=lineScanner.nextDouble();}
// else w=1;
Edge
e=new Edge(s,d,w);
insert(e);
}
}
public abstract void insert(Edge e);
public static Graph createGraph(Scanner scan,boolean isDirected,
String type){
AbstractGraph returnValue=null;
int numVertices=scan.nextInt();
// if(type.equalsIgnoreCase("Matrix"))//this
part not implemented.. text exercise
// returnValue=new MatrixGraph(numvertices,isDirected);
// else
if(type.equalsIgnoreCase("List"))
returnValue=new ListGraph(numVertices,isDirected);
else throw new IllegalArgumentException();
returnValue.loadEdgesFromFile(scan);
return returnValue;
}
}
package javatext;
import java.util.*;
public class ListGraph
extends AbstractGraph
{
private List<Edge>[]edges;
public ListGraph(int numVertices,boolean isDirected){
super(numVertices,isDirected);
edges=new List[numVertices];
for(int i=0;i<numVertices;i++)
edges[i]=new LinkedList<Edge>();
}
@Override
public void insert(Edge edge) {
edges[edge.getSource()].add(edge);
System.out.println("adding ("+edge.getSource()+","+edge.getDest()+")");
if(!isDirected()){
Edge
z=new Edge(edge.getSource(),edge.getDest(),edge.getWeight());
edges[edge.getDest()].add(z);
System.out.println("undirected...adding ("+z.getSource()+","+z.getDest()+")");
}
}
public boolean isEdge(int s, int d) {
return edges[s].contains(new Edge(s,d));
}
public Edge getEdge(int s, int d) {
Edge
target=new Edge(s,d,Double.POSITIVE_INFINITY);
for(Edge edge:edges[s]){
if (edge.equals(target))
return edge;
}
return target;
}
public Iterator<Edge>
edgeIterator(int s) {
// TODO Auto-generated
method stub
return edges[s].iterator();
}
}
package javatext;
import java.util.*;
public class BreadthFirstSearch
{
// this code returns a “parent” array
which would tell for each vertex who was its parent/predecessor in bfs
public static int[]breadthFirstSearch(Graph
graph,int
start){
Queue<Integer>queue=new LinkedList<Integer>();
int v=graph.getNumVertices();
int parent[]=new int[v];
for(int i=0;i<v;i++){
parent[i]=-1;
}
boolean identified[]=new boolean[v];
identified[start]=true;
queue.offer(start);
while(!queue.isEmpty()){
int c=queue.remove();
Iterator<Edge>iter=graph.edgeIterator(c);
while(iter.hasNext()){
Edge
e=iter.next();
int adjacent=e.getDest();
if(!identified[adjacent]){queue.offer(adjacent);
identified[adjacent]=true;
parent[adjacent]=c;}
}
}
return parent;
}
// I modified text code above to return
the enqueue/visit order of each vertex
public static int[]breadthFirstSearch2(Graph
graph,int
start){
Queue<Integer>queue=new LinkedList<Integer>();
int v=graph.getNumVertices();
int parent[]=new int[v];
for(int i=0;i<v;i++){
parent[i]=-1;
}
boolean identified[]=new boolean[v];
identified[start]=true;
queue.offer(start);
int j=0;
while(!queue.isEmpty()){
int c=queue.remove();
parent[j++]=c;
Iterator<Edge>iter=graph.edgeIterator(c);
while(iter.hasNext()){
Edge
e=iter.next();
int adjacent=e.getDest();
if(!identified[adjacent]){queue.offer(adjacent);
identified[adjacent]=true;
//parent[adjacent]=c;
}
}
}
return parent;
}
10
0 1
4 5
4 7
1 4
6 7
1 7
4 6
1 6
0 3
3 2
1 2
2 8
Scanner
s=new Scanner(new FileInputStream("input2.txt"));
Graph
myGraph=AbstractGraph.createGraph(s,false,"List");
int v=myGraph.getNumVertices();
System.out.println("adjacency
lists");
for(int j=0;j<v;j++){
Iterator<Edge>iter=myGraph.edgeIterator(j);
System.out.print("list "+j+" :");
while(iter.hasNext()){
Edge
e=iter.next();
int p=e.getDest();
if(e.getDest()==j)p=e.getSource();
System.out.print(" "+p);
}//has next
System.out.println(" ");
}//for
//notice I used my own bfs fn…not parent array:
int
list[]=BreadthFirstSearch.breadthFirstSearch2(myGraph,0);
//does not use int
ordering of level sets
for(int i=0;i<list.length;i++)System.out.println(""+list[i]);
adjacency lists
list 0 : 1 3
list 1 : 0 4 7 6 2
list 2 : 3 1 8 9
list 3 : 0 2
list 4 : 5 7 1 6
list 5 : 4
list 6 : 7 4 1
list 7 : 4 6 1
list 8 : 2
list 9 : 2
0
1
3
4
7
6
2
5
8
9
package javatext;
import java.util.Iterator;
/**
* Class to implement the depth-first search
algorithm.
* @author Koffman
and Wolfgang
**/
public class DepthFirstSearch
{
//
Data Fields
/**
A reference to the graph being searched. */
private Graph graph;
/**
Array of parents in the depth-first search tree. */
private int[] parent;
/**
Flag to indicate whether this vertex has been visited. */
private boolean[] visited;
/**
The array that contains each vertex in discovery
order. */
private int[] discoveryOrder;
/**
The array that contains each vertex in finish order.
*/
private int[] finishOrder;
/**
The index that indicates the discovery order. */
private int discoverIndex = 0;
/**
The index that indicates the finish order. */
private int finishIndex = 0;
//
Constructors
/**
* Construct the depth-first search of a Graph
* starting at vertex 0 and visiting the start vertices in
* ascending order.
* @param graph The graph
*/
public DepthFirstSearch(Graph
graph) {
this.graph = graph;
int n = graph.getNumVertices();
parent = new int[n+1];
visited = new boolean[n+1];
discoveryOrder = new int[n+1];
finishOrder = new int[n+1];
for (int i
= 0; i < n; i++) {
parent[i] = -1;
}
/*
for (int i = 0; i < n; i++) {
if
(!visited[i]) {
depthFirstSearch(i);
}
}*/
}
// Insert solution to programming
exercise 1, section 4, chapter 10 here
public int[] getFinishOrder() {
return finishOrder;
}
public int[] getDiscoveryOrder() {
return discoveryOrder;
}
/**
* Recursively depth-first search the graph
* starting at vertex current.
* @param current The start vertex
*/
public void depthFirstSearch(int current) {
//
Mark the current vertex visited.
visited[current] = true;
discoveryOrder[discoverIndex++] = current;
//
Examine each vertex adjacent to the current vertex
Iterator<Edge> itr = graph.edgeIterator(current);
while (itr.hasNext()) {
int neighbor = itr.next().getDest();
// Process a neighbor that has not been
visited
if (!visited[neighbor]) {
// Insert (current, neighbor) into
the depth-
// first search tree.
parent[neighbor] = current;
// Recursively apply the algorithm
// starting at neighbor.
depthFirstSearch(neighbor);
}
}
//
Mark current finished.
finishOrder[finishIndex++] = current;
}
// Insert solution to programming
exercise 1, section 4, chapter 10 here
}
10
0 1
4 5
4 7
1 4
6 7
1 7
4 6
1 6
0 3
3 2
1 2
2 8
Scanner s=new Scanner(new FileInputStream("input2.txt"));
Graph myGraph=AbstractGraph.createGraph(s,false,"List");
DepthFirstSearch dfs=new DepthFirstSearch(myGraph);
dfs.depthFirstSearch(0);
int discovery[]=dfs.getDiscoveryOrder();
int finish[]=dfs.getFinishOrder();
System.out.println("discovery and
finish order");
for(int i=0;i<myGraph.getNumVertices();i++)
adding (0,1)
undirected...adding (0,1)
adding (4,5)
undirected...adding (4,5)
adding (4,7)
undirected...adding (4,7)
adding (1,4)
undirected...adding (1,4)
adding (6,7)
undirected...adding (6,7)
adding (1,7)
undirected...adding (1,7)
adding (4,6)
undirected...adding (4,6)
adding (1,6)
undirected...adding (1,6)
adding (0,3)
undirected...adding (0,3)
adding (3,2)
undirected...adding (3,2)
adding (1,2)
undirected...adding (1,2)
adding (2,8)
undirected...adding (2,8)
adding (2,9)
undirected...adding (2,9)
discovery and finish order
0 5
1 7
4 6
5 4
7 8
6 9
2 2
8 1
9 3
3 0
9
0
1
1
2
2
5
0
4
0
3
1
5
1
4
3
6
4
6
4
7
5
7
6
8
7 8
Scanner s=new Scanner(new FileInputStream("input3.txt"));
Graph myGraph=AbstractGraph.createGraph(s,true,"List");
DepthFirstSearch dfs=new DepthFirstSearch(myGraph);
dfs.depthFirstSearch(0);
int finish[]=dfs.getFinishOrder();
for(int i=myGraph.getNumVertices()-1;i>0;i--)
System.out.println(" "+finish[i]);
adding (0,1)
adding (1,2)
adding (2,5)
adding (0,4)
adding (0,3)
adding (1,5)
adding (1,4)
adding (3,6)
adding (4,6)
adding (4,7)
adding (5,7)
adding (6,8)
adding (7,8)
Topological sort
0
3
1
4
6
2
5
7