Homework Sourse319 Write a program that will take as input two Web page URL
3.19 Write a program that will take as input two Web page URLs and find a path of links from one to the other. What is an appropriate search strategy? Is bidirectional search a good idea? Could a search engine be used to implement a predecessor function?
Solution
package Pathfinder;
import java.io.IOException;
import java.util.ArrayList;
public class PFApp
{
public static void main(String[] args) throws IOException
{
Problem problem = new Problem(“http://www.jsoup.org”, “http://jsoup.org/apidocs/org/jsoup/nodes/DataNode.html#setWholeData(java.lang.String)”);
URLPathfinder urlPathfinder = new URLPathfinder();
ArrayList<String> solution = urlPathfinder.iterativeDeepeningSearch(problem);
System.out.print(solution);
}
}
Java Code – Node.java
package Pathfinder;
import java.util.ArrayList;
public class Node
{
public Node(String state)
{
this.state = state;
stateHistory = new ArrayList<String>();
stateHistory.add(state);
}
public Node(Problem problem, Node node, String link)
{
this(node.getState());
state = link;
stateHistory = new ArrayList<String>(node.stateHistory);
stateHistory.add(state);
}
public String getState() { return state; }
public ArrayList<String> getStateHistory() { return stateHistory; }
private String state;
private ArrayList<String> stateHistory;
}
Java Code – Problem.java
public class Problem
{
public Problem(String initial, String goal)
{
initialState = initial;
goalState = goal;
}
public boolean goalTest(String nodeState)
{
return (goalState.equals(nodeState));
}
public List<String> actions(Node node) throws IOException
{
List<String> actionList = new ArrayList<String>();
// code for adding actions
Document site = Jsoup.connect(node.getState()).get();
Elements links = site.select(“a[href]”);
for (Element link : links)
{
if (!link.attr(“abs:href”).startsWith(“http://”) && !link.attr(“abs:href”).startsWith(“https://”))
continue;
boolean repeat = false;
for (String sites : node.getStateHistory())
{
if (link.attr(“abs:href”) == sites)
repeat = true;
}
if (!repeat)
actionList.add(link.attr(“abs:href”));
}
return actionList;
}
public String getInitialState() { return initialState; }
public String getGoalState() { return goalState; }
private String initialState;
private String goalState;
Java Code – URLPathfinder.java
package Pathfinder;
import java.io.IOException;
import java.util.*;
public class URLPathfinder
{
public URLPathfinder()
{
solution = new ArrayList<String>();
}
public ArrayList<String> iterativeDeepeningSearch(Problem problem) throws IOException
{
solution.add(problem.getInitialState());
for(depth = 0;;++depth)
{
solution = depthLimitedSearch(problem, depth);
if (solution.get(0) != “cutoff”)
return solution;
}
}
public long getDepth() { return depth; }
private ArrayList<String> depthLimitedSearch(Problem problem, long limit) throws IOException
{
return recursiveDLS(new Node(problem.getInitialState()), problem, limit);
}
private ArrayList<String> recursiveDLS(Node node, Problem problem, long limit) throws IOException
{
if (problem.goalTest(node.getState()))
return node.getStateHistory();
else if (limit == 0)
{
ArrayList<String> cutoff = new ArrayList<String>();
cutoff.add(“cutoff”);
return cutoff;
}
else
{
cutoffOccured = false;
for (String link : problem.actions(node))
{
Node child = new Node(problem, node, link);
solution = recursiveDLS(child, problem, limit – 1);
if (solution.get(0) == “cutoff”)
cutoffOccured = true;
else
return solution;
}
if (cutoffOccured)
return solution;
else
return solution;
}
}
private boolean cutoffOccured;
private long depth;
private ArrayList<String> solution;
