4

Currently I am in the process of developing an importer of any existing, arbitrary (static) HTML website into the upcoming release of our CMS.

While the downloading the files is solved successfully, I'm pulling my hair off when it comes to detect a site structure (pages and subpages) purely from the HTML files, without the user specifying additional hints.

Basically I want to get a tree like:

+ Root page 1
     + Child page 1
     + Child page 2
         + Child child page1
     + Child page 3
+ Root page 2
     + Child page 4
+ Root page 3
+ ...

I.e. I want to be able to detect the menu structure from the links inside the pages. This has not to be 100% accurate, but at least I want to achieve more than just a flat list.

I thought of looking at multiple pages to see similar areas and identify these as menu areas and parse the links there, but after all I'm not that satisfied with this idea.

My question:

Can you imagine any algorithm when it comes to detecting such a structure?

Update 1:

What I'm looking for is not a web spider, but an algorithm do create a logical tree of the relationship of the pages to be able to create pages and subpages inside my CMS when importing them.

Update 2:

As of Robert's suggestion I'll solve this by starting at the root page, and then simply parse links as you go and treat every link inside a page simply as a child page. Probably I'll recurse not in a depth-first manner but rather in a breadth-first manner to get a more balanced navigation structure.

Improve this question
6
  • 5
    You're basically describing a web crawler or spider. The algorithm is recursive; it finds the links in the page, follows them, finds the links in those pages, follows them, and so forth. It's essentially a tree traversal algorithm.
    – Robert Harvey
    Nov 21, 2011 at 20:00
  • 1
    @RobertHarvey Hopefully not :-) I've successfully developed a web spider. What I'm looking for might be called a "post mortem web spider". I want to detect the structure of what a web spider produces.
    – Uwe Keim
    Nov 21, 2011 at 20:03
  • 2
    So what's the problem? You already know how to do it. :P Save the links as you crawl. Make a tree.
    – Robert Harvey
    Nov 21, 2011 at 20:04
  • 1
    You don't know how to make a tree?
    – Robert Harvey
    Nov 21, 2011 at 20:06
  • 1
    See my answer below. I apologize if you're not using C#.
    – Robert Harvey
    Nov 21, 2011 at 20:10

1 Answer 1

Reset to default
4

You need a recursive data structure. Something like this:

public class TreeNode<T>
{
    public T node { get; set; }
    public List<TreeNode<T>> descendants { get; set; }
}
Improve this answer
4
  • So basically, you would start at the root page, and simply parse links as you go and treat every link inside a page simply as a child page?
    – Uwe Keim
    Nov 21, 2011 at 20:10
  • 1
    Yes, exactly. .
    – Robert Harvey
    Nov 21, 2011 at 20:14
  • That seems just too simply but quite valid :-) So I'll give it a shot! Thanks for pushing me in the right direction!
    – Uwe Keim
    Nov 21, 2011 at 20:16
  • 2
    Just for the records: Probably I'll should recurse not in a deep-first manner but rather in a breadth-first manner to get a more balanced navigation structure.
    – Uwe Keim
    Nov 21, 2011 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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