[BGL] - filesystem graph
Hi, I would like to know how to "best" represent a filesystem using BGL. In this case the filesystem I want to describe is the unix/linux filesystem and its various paths from the root node "/". My questions: 1. What kind of graph is this filesystem and what is best to use in BGL to describe this? 2. How can I also best describe symbolic links (symlinks) and what kind of graph would this be, does this graph defer from the above? 3. How can I describe the metadata of a file (including symlinks) using BGL eg. given a path /usr/bin/ls I also want to stores its creation date, acl etc in BGL, how can I best describe this, is there where properties come in handy? 4. Are there any examples on this anywhere and/or does the BGL book describe any examples on this? Thanks Shams
On 2/28/07, Shams <shams@orcon.net.nz> wrote:
Hi,
I would like to know how to "best" represent a filesystem using BGL. In this case the filesystem I want to describe is the unix/linux filesystem and its various paths from the root node "/".
Hi Shams,
My questions: 1. What kind of graph is this filesystem and what is best to use in BGL to describe this?
The graph defined by the hard links is a tree. The BGL graph you use would depend on what you want to do. For instance, you might want to use a directed graph with edges pointing from a directory to each of its contents, but I'd have to know more about what you want to do to suggest anything.
2. How can I also best describe symbolic links (symlinks) and what kind of graph would this be, does this graph defer from the above?
Symbolic links can create cycles in the graph, so that the graph is no longer a tree. You can use edge properties to specify the type of link an edge represents here - filtering on the hard link properties gives you a tree.
3. How can I describe the metadata of a file (including symlinks) using BGL eg. given a path /usr/bin/ls I also want to stores its creation date, acl etc in BGL, how can I best describe this, is there where properties come in handy?
Yes, exactly - properties can be used to create a mapping between vertices/edges and other types, i.e. mapping each vertex to a string or an integer.
4. Are there any examples on this anywhere and/or does the BGL book describe any examples on this?
Yes, there are many examples online, and the book has an example of building a file dependency graph. Regards, Aaron
Thanks for the info. 1. Imagine a filesystem with just hard links ie. no symbolic links. Now I believe this is a "directed acyclic graph" which is just a rooted tree, right? 2. Now imagine a filesystem with hard links + symbolic links. Now certain directories may contain symbolic links to other directories or files. I want to represent this in BGL, what is this type of graph called? Thanks Shams -- "Aaron Windsor" <aaron.windsor@gmail.com> wrote in message news:2ed236020703010351x4f15c159g4e69e793012ed857@mail.gmail.com...
On 2/28/07, Shams <shams@orcon.net.nz> wrote:
Hi,
I would like to know how to "best" represent a filesystem using BGL. In this case the filesystem I want to describe is the unix/linux filesystem and its various paths from the root node "/".
Hi Shams,
My questions: 1. What kind of graph is this filesystem and what is best to use in BGL to describe this?
The graph defined by the hard links is a tree. The BGL graph you use would depend on what you want to do. For instance, you might want to use a directed graph with edges pointing from a directory to each of its contents, but I'd have to know more about what you want to do to suggest anything.
2. How can I also best describe symbolic links (symlinks) and what kind of graph would this be, does this graph defer from the above?
Symbolic links can create cycles in the graph, so that the graph is no longer a tree. You can use edge properties to specify the type of link an edge represents here - filtering on the hard link properties gives you a tree.
3. How can I describe the metadata of a file (including symlinks) using BGL eg. given a path /usr/bin/ls I also want to stores its creation date, acl etc in BGL, how can I best describe this, is there where properties come in handy?
Yes, exactly - properties can be used to create a mapping between vertices/edges and other types, i.e. mapping each vertex to a string or an integer.
4. Are there any examples on this anywhere and/or does the BGL book describe any examples on this?
Yes, there are many examples online, and the book has an example of building a file dependency graph.
Regards, Aaron
On 3/2/07, Shams <shams@orcon.net.nz> wrote:
Thanks for the info.
1. Imagine a filesystem with just hard links ie. no symbolic links. Now I believe this is a "directed acyclic graph" which is just a rooted tree, right?
2. Now imagine a filesystem with hard links + symbolic links. Now certain directories may contain symbolic links to other directories or files. I want to represent this in BGL, what is this type of graph called?
Hi Shams, 1) Yes, it can be represented by a directed acyclic graph. 2) As stated, there's not enough restrictions on the structure of the graph to call it anything more restrictive than just a "directed graph." It may be acyclic, it may not be. But to suggest a representation, I'd have to know what you're trying to do. If you're not sure, an adjacency_list<vecS,vecS,directedS> would probably be a good starting point. Regards, Aaron
participants (2)
-
Aaron Windsor -
Shams