in reply to In search of an algorithm for loading cyclic graphs

If you have A -> B -> A, what do you expect your table to look like? I don't think that using sequential IDs will work that well ...

If, however, you are using three tables (One for nodes, one for linktypes, and one for node/node/link), then this is trivial:

But, if it was that easy, you wouldn't be asking the question. *shrugs*

  • In general, if you think something isn't in Perl, try it out, because it usually is. :-)
  • "What is the sound of Perl? Is it not the sound of a wall that people have stopped banging their heads against?"

Replies are listed 'Best First'.
Re^2: In search of an algorithm for loading cyclic graphs
by samtregar (Abbot) on May 17, 2005 at 18:32 UTC
    If you have A -> B -> A, what do you expect your table to look like? I don't think that using sequential IDs will work that well ...
     

    Table A

a_id | b_id
-----------
1      1


Table B

b_id | a_id
-----------
1      1

    [download]

    Each table has its own pool of sequential IDs, like most databases.

    If, however, you are using three tables (One for nodes, one for linktypes, and one for node/node/link), then this is trivial:

    Nope, it's not that simple. Each node type has its own table structure and most of them are more complicated than that.

    -sam

[reply]
[d/l]
      I'm not understanding something because that looks like you're creating a table for each node type and the rows of said tables are the edges.

      Personally, I would create the tables for the node types and have a completely separate table that actually demonstrates the links between the nodes. I would also treat the nodes both in one tables (called nodes) and in their separate tables who FK to nodes. Kinda like a base class and child classes. That way, you can handle it as a 3-table graph when convenient, but you can also get to the data when needed.

      • In general, if you think something isn't in Perl, try it out, because it usually is. :-)
      • "What is the sound of Perl? Is it not the sound of a wall that people have stopped banging their heads against?"
[reply]
        I'm not understanding something because that looks like you're creating a table for each node type and the rows of said tables are the edges.

        You've got it. The only part you're missing is that isn't "just" a graph system. It's Krang, the purpose of which is not to be a general graph implementation but rather to publish webpages. The fact that dumping and loading data is essentially a cyclic-graph-loading problem is more a side-effect than a design goal.

        In this case each node type is a completely different kind of data - stories, templates, media, categories, users, etc. The links are forgeign keys in the tables, category_id in the media table for example.

        Does that make sense?

        -sam

[reply]
      I'm not sure where the problem is here. If you know that the ids are unique within each table, and you know the table to be looking in for a given id (from the field name), doesn't that uniquely identify what each field is trying to point to?

      If not, why not just assign each table a starting number, with room for a few million (or however many seems appropriate) rows between each starting number?

      What kind of 'indigestion' does your code get?

[reply]
        Does my answer to your question below help? I'm not sure how to better explain it...

        But really, I'm not looking for help hacking the code. I'm looking for pointers to a generic comp-sci algorithm that applies to loading huge cyclic graphs, with all the problems that causes. If my explanation so far hasn't suggested something to you then either it doesn't exist or you don't know it.

        -sam

[reply]

In Section Seekers of Perl Wisdom