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.

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 deep-first manner but rather in a breadth-first manner to get a more balanced navigation structure.

share|improve this question
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 '11 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 '11 at 20:03
1  
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 '11 at 20:04
1  
You don't know how to make a tree? –  Robert Harvey Nov 21 '11 at 20:06
1  
See my answer below. I apologize if you're not using C#. –  Robert Harvey Nov 21 '11 at 20:10
show 2 more comments

1 Answer 1

up vote 4 down vote accepted

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; }
}
share|improve this answer
    
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 '11 at 20:10
1  
Yes, exactly. . –  Robert Harvey Nov 21 '11 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 '11 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 '11 at 20:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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