How to turn a website into an offline usable directed graph for searching shortest ways between pages [closed]

Question

I am an advanced-intermediate level student focused on the .NET and C#. I know all the basics as well as classes, methods, objects, inheritance, OOP principles and all that. Problem is we haven't covered data structures like trees and graphs yet.

Basically what I need my program to be able to do is this:

Part 1 Console application:

1. Go online to a specific website and following the net of links on it, starting with the main page, create a directed graph with weightless edges and store it locally, so that it can be used without internet connection.
2. Be able to recreate the graph from the locally saved data and then by given 2 links as parameters to find and print the shortest path between them.

Part 2 Some sort of UI:

1. By given webpage address and depth - visually represent in the browser a tree structure with the given website as root and the level of depth of the possible pages accessible by following the links from it.

I would really appreciate it if you can direct me in the choices I have to make to accomplish this task. Mainly I am puzzled by these:

1. How to represent a graph in C#.
2. How to save it locally (program must finish within 5 seconds, so I cannot go online and do everything from scratch).
3. What should I use for the UI part with the tree visualization.

I don't seek for complete answers rather than good directives. I need to learn these fast and not to waste precious time wandering.

Answer 1

Since this sounds like homework, I'll just try giving some "good directives" like you've asked.

Part 1

Go online to a specific website and following the net of links on it, starting with the main page, create a directed graph with weightless edges and store it locally, so that it can be used without internet connection.

This is asking you to write a web crawler (sometimes spider). Basically:

• Start at a specific page; retrieve its contents.
• Process the contents and parse all links (can use regex, or can use an HTML parsing library (better, but may not be what your instructor wants)).
• Put the new links onto a queue so that you can perform a breadth-first search of the pages.
  • You'll have to pay special attention here so that you'll avoid getting stuck in loops. Generally that means using some sort of set that contains all visited links.
• Process the links still in your queue in the same manner (visit, parse links, store, repeat).

Be able to recreate the graph from the locally saved data and then by given 2 links as parameters to find and print the shortest path between them.

• You need to store the links locally as well. Some options:
  • Append to a single file, each line contains a single link (edge).
    1. Source URL
    2. Destination URL
  • Each line contains:
    1. Source URL
    2. All destination URLs (parsed from the source page).
• This will allow you to re-create the graph in sparse matrix notation (I personally prefer lists of lists, but there's many options).
• For the shortest path problem, there are many options.
  • Perhaps the simplest is another breadth-first search on your local graph, starting with the first link given as a parameter.
    • Note: Edges on websites have direction. For this reason, having an indicated "starting" node and "ending" node makes a difference.
    • Can always compute the shortest path starting at both, if you don't care about link direction.
    • Very easy to have an "infinite" shortest path (i.e., there is no path between them).
  • If you don't have very many nodes in your graph, and you are looking at speed (it's already going to be fast anyway, so probably don't bother), then you can pre-compute the shortest paths for all nodes.
    • If you do this, I might use Dijkstra's algorithm or preferably an all pairs shortest path algorithm like the Floyd–Warshall algorithm.

Part 2

By given webpage address and depth - visually represent in the browser a tree structure with the given website as root and the level of depth of the possible pages accessible by following the links from it.

• (This part of my answer could use some improvement.)
• Currently, I would suggest either:
  • Doing it programmatically
    • Perhaps Google Charts has something that can be used for this purpose?
  • Using a graphing or visualization tool to pre-build the graph and display that to the user.
    • yED
    • Graphviz
    • Gephi
    • many others ... can search for "network visualization" as well.

Hope that helps point you in the right direction(s).