User:Guverneu

Discussion

Its about finding closed loops in a hierarchy, like in nested relations or Super-Relations. I think it can be done like this, though I don't believe that this is the first time to solve such a problem.

Oh it's kind of a Materialized Path solving a graph problem obviously. If anyone knows more, a tip is greatly appreciated.

Tree assembling

A relation-list is modelling a hierarchy as an m:n table. It is usually found on relational databases that tools like Osmosis are made for. In contrast, the xml representation of the Osm data has native tree structure, but is generally harder to query. So given such a relation-list, a path-list can be assembled and closed loops can be found.

Example

Again, based on an example of 11 relations:

        A     
   ^         v
  E                B      
   ^         v     v     v
    D   <   C      G      H  
            v       v   v   ^
            F         I     :
                    v   v   :
                   J      K  

FrTo E A C D I K K H A B D E H I C F G I I J B H B G B C

FrTo E A C D E I K K H I J A B C F A B G I J +r A B H I J +r D E H I J C F G I J I J B H B G B C

FrTo E A B H I J E A B G I J +r E A B C F +r C D E I K H I J ring leave K H I J A B C F A B G I J A B H I J

FrTo E A B H I J leave E A B G I J leave E A B C F leave E A B C D E +r ring leave C D E I K H I ring I J ring-rest

FrTo E A B H I J E A B G I J E A B C F E A B C D E ring I K H I ring I J

Algorithm

Make the paths-table:

• Copy the relation m:n table or list.
• Iterate through the list in any direction. For each row:
  • First check if its not a ring already found.
  • Otherwise search its From relation in the To relation list of all other rows.
    • Is there one match or more:
      • For each of them:
        • If it's the last relation in the list, append the To list of the current processed row.
        • If it's in the middle of the list, add a row and copy the From part as well as the To part from the beginning to the matching relation. Then append the To list of the current processed row.
        • Anyway, check if it's a closed loop.
          • If yes: Split the path of the form fr0 toA to2 to3 toA to5 to path-rows of fr0 toA, toA to2 to3 toA and toA to5. Just the middle part is the closed loop, the rest is not affected.
      • Delete the processed row.
    • If no matches were found, just leave the row. It's a top-level relation then.

Then transform just the the closed loop relations back to a simple relation m:n table. Delete the matching entries from the original simple relation m:n table.

• To do so create an empty table or list. For each row that holds a closed loop in the paths-table:
  • Split the path of the form fr0 to1 to2 to3 to rows of fr0 to1, to1 to2 and to2 to3.
• Delete the matching entries.

Now we at the beginning point, except we have no more closed loops. To continue building trees:

• Transform the enhanced simple relation m:n table to a path table again.
• Start the next episode with level information of each relation.

Example (continued)

In the example, delete all EA AB BC CD DE connections, delete all IK KH HI connections, and reassemble the tree to get a path list:

FrTo E A x C D x I K x K H x A B x D E x H I x C F G I I J B H B G B C x

FrTo C F G I I J B H B G

FrTo Directed Acyclic Graph C F B H B G I J

On the resulting pathlist, there are 3 trees left with 2, 2 and 4 levels of depth. Relation on the left is top-level.