Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
Being advanced-intermediate and not knowing about trees is a contradiction in my book. Check your library for some foundational books (Knuth, Cormen, or some such) and waste precious time with those to really make the jump to intermediate. –  Frank Mar 12 '13 at 6:10
add comment

closed as too localized by MainMa, Kilian Foth, Martin Wickman, Frank Shearar, Glenn Nelson Mar 12 '13 at 11:37

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 0 down vote accepted

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.

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).

share|improve this answer
2  
Please, whatever you do, do not use regexes to parse HTML. –  Mason Wheeler Mar 11 '13 at 23:48
    
@MasonWheeler While that is usually best practice, I have found it depends on the instructor. Mine didn't want us to use any libraries for crawling, so we had to use regex if we wanted to spend the semester working on the actual problem rather than writing an html parser by hand. –  Wesley Baugh Mar 11 '13 at 23:51
    
@Dan-o if you read it a little less sarcastically, it becomes dramatically less ridiculous when you see that I said any libraries for crawling. It all depends on what the learning goal is. In my past case, it was to learn how to make a web crawler. Using a crawling library with one or two function calls doesn't teach anything about using breadth-first search etc. –  Wesley Baugh Mar 12 '13 at 0:49
    
To whomever downvoted: In what way is this answer "not useful"? I believe it goes a long way to ironing out some of the questions the OP had. If you disagree, please comment (or edit the post since this is under Creative Commons). Right now you're just discouraging people from answering questions. –  Wesley Baugh Mar 12 '13 at 5:17
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.