acyclic directed graph instead of tree

jashar

Joined: 2004-06-20
Posts: 11

Posted: Mon, 2004-06-21 23:43

I was wondering if there was any way to make the tree of albums more of an acylic directed graph. By that, I mean, have an AlbumItem be an AlbumItem of more than one Album.

So, this way, I could say, have an Album "Otakons" and another Album "Summer 03" and have Album "Otakon X" be an AlbumItem of both "Otakons" and "Summer 03".

Or, if I had an Album "Pics of me" and another Album "Pics of my sister", I could put Photo "My sister and I" as an AlbumItem of both Albums ("Pics of me" and "Pics of my sister").

signe

Joined: 2003-07-27
Posts: 2322

Posted: Tue, 2004-06-22 08:02

This isn't something that will occur in G1 - it's just not feasible right now. Maybe in G2 (but don't hold me to that.. I have no control over G2)?

jashar

Joined: 2004-06-20
Posts: 11

Posted: Tue, 2004-06-22 13:15

After sifted through the source code and being completely clueless about what's going on, I hacked the photos.dat file of one of my albums to point to the same sub-album as another album. This allowed me to have the same album be a sub-album of two other albums (a). Though having the same picture be in two albums would be more complicated (a symlink + an entry in photos.dat), I think that would be possible, too. I think just adding a drop-down to the album admin options for "existing nested album" wouldn't be too bad, if one were familiar with the code.

(a) the sub-album only has support for one parent album, so it's not 100% right, but it works. adding this to G1 may be a little more work, but i'm sure it can be done, but it's not necessary. it can be a 'feature' and not a 'bug' that when an album is a sub-album of two albums, that it has only one 'primary parent album'.

signe

Joined: 2003-07-27
Posts: 2322

Posted: Tue, 2004-06-22 15:29

Yes, it is something that can be accomplished, but there are more issues at hand than just whether you can create the link. ex:

User creates a link.
User decides that they want to move the link somewhere else.
User accidently moves the link inside its other branch. It is now a doubly-recursive link.

Another:

People (like me) use the tree view in the root album. Having two of the same link means that that subtree is duplicated, as are any other links, in the tree.

Now, before you say it, of course, all these things can be addressed. Unfortunately, each one of them would need to be addressed painstakingly before such a feature could be implemented. Missing anything in a feature of this kind could be horrible for users and their albums.

It's just that we don't see this as a necessary feature at this time. We have far too many important features that are still yet to be implemented (TIFF support? Movie thumbnails? IPTC support? etc.) for something of this magnitude to be planned for.

jashar

Joined: 2004-06-20
Posts: 11

Posted: Wed, 2004-06-23 09:06

Before I go off into a rant (sorry, i know this really isn't the place for a rant), let me say that I'm not saying that you have to put this into G1, would put this into G1, or should put this into G1. I'm just saying that you could.

I'm not suggesting the ability to move links. What I'm suggesting is the ability to create links form an album to an already-existing sub-album. That sub-album already has a parent album, whose link would stay as is. And destroying the link would also have no effect on the parent-album/sub-album relationship. There should not be the ability to move links.

Now let's say the user creates the link within the sub-album. This is an extra check that would need to be done during creation. Hence the "acyclic" part of this discussion topic.

Another problem is making the link, and then removing the sub-album from the parent-album. Though not desirable, it should be okay if the sub-album no longer has a parent album. But, I suppose a link count to the album would need to be kept so that the sub-album is not deleted. (like hard links in a file system)

I also use the tree view. And yes, the sub-album is duplicated. I guess I don't see the problem with this. It seems likea reasonable thing to want to see all my "Otakons" and "Summer 03" sub-albums listed as a group, even if it means duplicates, but I supposed that is a matter of preference.

Yes, this would be a pain in the butt to implement, just toss in on the to-do list way at the end I guess.

signe

Joined: 2003-07-27
Posts: 2322

Posted: Wed, 2004-06-23 09:19

The inherent problem with this kind of thing (yes, in G1), is the cyclic nature of it. There would have to be excessive levels of nest-checking in both up and down directions to prevent infinite loops, among other things.

For example, if you had a tree that started out like this:

and you created a link from E into the C album (so you had ABCE in one tree), there's nothing to prevent you from linking A into E without having a truly n-way tree. In the examples you were giving (only having one parent album) there's no way to tell (from E) that it is an indirect child of A without recusively checking each entry in every album.

The idea is good, and it can be hacked to a point, but implementing this officially would be a rearcitechture from the ground up for Gallery. Virtually everything from album moves to file deletion would need to be adapted to handle the multi-way nature of that kind of structure.

jashar

Joined: 2004-06-20
Posts: 11

Posted: Thu, 2004-06-24 03:59

I'm sorry. I know I shouldn't be continuing this discussion as I know it won't be in G1, but this is what I understand:

(left arrow is parent, right arrow is child/sub)

A<->B
B<->C
D<->E
E<->F

becomes:

A<->B
B<->C
C ->E
D<->E
E<->F

so when you try to add E->A, you check A, childwards, looking for E, not E, parentwards, looking for A, and you would find A->B->C->E and not allow E->A. It doesn't seem too costly to do an exhaustive search on A, looking for E, when you create the link, considering this check is done once per link creation. An exhaustive coverage of the whole tree is done each root page display if you have trees display at the root page.

signe

Joined: 2003-07-27
Posts: 2322

Posted: Thu, 2004-06-24 04:31

jashar wrote:

so when you try to add E->A, you check A, childwards, looking for E, not E, parentwards, looking for A, and you would find A->B->C->E and not allow E->A. It doesn't seem too costly to do an exhaustive search on A, looking for E, when you create the link, considering this check is done once per link creation. An exhaustive coverage of the whole tree is done each root page display if you have trees display at the root page.

That's what I said... "there's no way to tell (from E) that it is an indirect child of A without recusively checking each entry in every album"

Recursively checking A is a very expensive operation that involves loading every image in every album that is a sub of A. In Galleries with lots of images, this can take an excessive amount of time.

jashar

Joined: 2004-06-20
Posts: 11

Posted: Thu, 2004-06-24 13:03

Quote:

Recursively checking A is a very expensive operation that involves loading every image in every album that is a sub of A. In Galleries with lots of images, this can take an excessive amount of time.

But this happens every time someone views your root page (if you have displaying the tree enabled). What I'm suggesting is once per link creation. What is already happenning is once per root page access. This already takes an excessive amount of time, and root page accesses happen way more often than link creations would happen.

jashar Joined: 2004-06-20 Posts: 11	Posted: Mon, 2004-06-21 23:43
	I was wondering if there was any way to make the tree of albums more of an acylic directed graph. By that, I mean, have an AlbumItem be an AlbumItem of more than one Album. So, this way, I could say, have an Album "Otakons" and another Album "Summer 03" and have Album "Otakon X" be an AlbumItem of both "Otakons" and "Summer 03". Or, if I had an Album "Pics of me" and another Album "Pics of my sister", I could put Photo "My sister and I" as an AlbumItem of both Albums ("Pics of me" and "Pics of my sister").
	XUser login Username: * Password: * Create new account Request new password
signe Joined: 2003-07-27 Posts: 2322	Posted: Tue, 2004-06-22 08:02
	This isn't something that will occur in G1 - it's just not feasible right now. Maybe in G2 (but don't hold me to that.. I have no control over G2)?

jashar Joined: 2004-06-20 Posts: 11	Posted: Tue, 2004-06-22 13:15
	After sifted through the source code and being completely clueless about what's going on, I hacked the photos.dat file of one of my albums to point to the same sub-album as another album. This allowed me to have the same album be a sub-album of two other albums (a). Though having the same picture be in two albums would be more complicated (a symlink + an entry in photos.dat), I think that would be possible, too. I think just adding a drop-down to the album admin options for "existing nested album" wouldn't be too bad, if one were familiar with the code. (a) the sub-album only has support for one parent album, so it's not 100% right, but it works. adding this to G1 may be a little more work, but i'm sure it can be done, but it's not necessary. it can be a 'feature' and not a 'bug' that when an album is a sub-album of two albums, that it has only one 'primary parent album'.

signe Joined: 2003-07-27 Posts: 2322	Posted: Tue, 2004-06-22 15:29
	Yes, it is something that can be accomplished, but there are more issues at hand than just whether you can create the link. ex: User creates a link. User decides that they want to move the link somewhere else. User accidently moves the link inside its other branch. It is now a doubly-recursive link. Another: People (like me) use the tree view in the root album. Having two of the same link means that that subtree is duplicated, as are any other links, in the tree. Now, before you say it, of course, all these things can be addressed. Unfortunately, each one of them would need to be addressed painstakingly before such a feature could be implemented. Missing anything in a feature of this kind could be horrible for users and their albums. It's just that we don't see this as a necessary feature at this time. We have far too many important features that are still yet to be implemented (TIFF support? Movie thumbnails? IPTC support? etc.) for something of this magnitude to be planned for.

jashar Joined: 2004-06-20 Posts: 11	Posted: Wed, 2004-06-23 09:06
	Before I go off into a rant (sorry, i know this really isn't the place for a rant), let me say that I'm not saying that you have to put this into G1, would put this into G1, or should put this into G1. I'm just saying that you could. I'm not suggesting the ability to move links. What I'm suggesting is the ability to create links form an album to an already-existing sub-album. That sub-album already has a parent album, whose link would stay as is. And destroying the link would also have no effect on the parent-album/sub-album relationship. There should not be the ability to move links. Now let's say the user creates the link within the sub-album. This is an extra check that would need to be done during creation. Hence the "acyclic" part of this discussion topic. Another problem is making the link, and then removing the sub-album from the parent-album. Though not desirable, it should be okay if the sub-album no longer has a parent album. But, I suppose a link count to the album would need to be kept so that the sub-album is not deleted. (like hard links in a file system) I also use the tree view. And yes, the sub-album is duplicated. I guess I don't see the problem with this. It seems likea reasonable thing to want to see all my "Otakons" and "Summer 03" sub-albums listed as a group, even if it means duplicates, but I supposed that is a matter of preference. Yes, this would be a pain in the butt to implement, just toss in on the to-do list way at the end I guess.

signe Joined: 2003-07-27 Posts: 2322	Posted: Wed, 2004-06-23 09:19
	The inherent problem with this kind of thing (yes, in G1), is the cyclic nature of it. There would have to be excessive levels of nest-checking in both up and down directions to prevent infinite loops, among other things. For example, if you had a tree that started out like this: A B C D E F and you created a link from E into the C album (so you had ABCE in one tree), there's nothing to prevent you from linking A into E without having a truly n-way tree. In the examples you were giving (only having one parent album) there's no way to tell (from E) that it is an indirect child of A without recusively checking each entry in every album. The idea is good, and it can be hacked to a point, but implementing this officially would be a rearcitechture from the ground up for Gallery. Virtually everything from album moves to file deletion would need to be adapted to handle the multi-way nature of that kind of structure.

jashar Joined: 2004-06-20 Posts: 11	Posted: Thu, 2004-06-24 03:59
	I'm sorry. I know I shouldn't be continuing this discussion as I know it won't be in G1, but this is what I understand: (left arrow is parent, right arrow is child/sub) A<->B B<->C D<->E E<->F becomes: A<->B B<->C C ->E D<->E E<->F so when you try to add E->A, you check A, childwards, looking for E, not E, parentwards, looking for A, and you would find A->B->C->E and not allow E->A. It doesn't seem too costly to do an exhaustive search on A, looking for E, when you create the link, considering this check is done once per link creation. An exhaustive coverage of the whole tree is done each root page display if you have trees display at the root page.

signe Joined: 2003-07-27 Posts: 2322	Posted: Thu, 2004-06-24 04:31
	jashar wrote: so when you try to add E->A, you check A, childwards, looking for E, not E, parentwards, looking for A, and you would find A->B->C->E and not allow E->A. It doesn't seem too costly to do an exhaustive search on A, looking for E, when you create the link, considering this check is done once per link creation. An exhaustive coverage of the whole tree is done each root page display if you have trees display at the root page. That's what I said... "there's no way to tell (from E) that it is an indirect child of A without recusively checking each entry in every album" Recursively checking A is a very expensive operation that involves loading every image in every album that is a sub of A. In Galleries with lots of images, this can take an excessive amount of time.

jashar Joined: 2004-06-20 Posts: 11	Posted: Thu, 2004-06-24 13:03
	Quote: Recursively checking A is a very expensive operation that involves loading every image in every album that is a sub of A. In Galleries with lots of images, this can take an excessive amount of time. But this happens every time someone views your root page (if you have displaying the tree enabled). What I'm suggesting is once per link creation. What is already happenning is once per root page access. This already takes an excessive amount of time, and root page accesses happen way more often than link creations would happen.

acyclic directed graph instead of tree

XUser login