Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

generating a Tree from Array and find the best way

by ultibuzz (Monk)
on Apr 06, 2006 at 21:19 UTC ( #541741=perlquestion: print w/replies, xml ) Need Help??
ultibuzz has asked for the wisdom of the Perl Monks concerning the following question:

hi Monks, i have some serious problem and im not that skilled in programming to fix it. first i will descript the situation and the problem to give you a brief overview for understanding the surroundings

Current Situation

We have some Web-based Forms, that forms will be set to different stats for different work ,exp. submitted, in progress, done

The way how to change the status , the transitions between the states is given

So normal USERS are bound to a pre defined path, but we have 2 more USER types, MOD_USER and ADMIN_USER

The MOD can jump from some STATES to some other, ADMINs can do what ever they want

Internal rule is that even MODs or ADMINs follow the path, but as usual mostly they didnt and this is the problem

Now i need to implement the missing STATES into the whole flow, otherwise some important statistiks are messed up


The Transitions between the STATES are given as pairs exp "0,1" these are the IDs from DB and will be replaced later with the Values

'from_transition_id','to_transition_id' 0,1 0,1 0,1 1,344 1,202 1,300 1,300 2,3 3,4 4,202 4,345 4,5 4,6 5,440 5,500 5,508 5,6 5,505 6,7 6,201 6,507 6,503 7,503 7,2 7,507 7,200 200,202 202,201 202,2 300,2 300,344 300,502 300,506 300,202 344,300 345,4 440,5 500,5 502,300 503,6 503,7 505,5 506,300 507,6 507,7 508,6

Duplicates can be ignored

The problem

The problem have 2 Parts(script for each)

  1. A Tree VIEW of each Possible Way
  2. A given Way where STATES are missing that needs to be filled

1. As you can see Under "Transition List" the Pairs looks like DOMINO STONES and can only be connected when the last and the first are the same exp. "0,1" "1,200" "200,3" is a possible way

so i need a tree view out of this like

200-3 / 0-1

must not be asci connection can what ever is possible, i tryed somthing with a lot of ifs but i end up in a totaly nonsens mess , logicaly the problem is easy like a puzzle but to programm it i need to ask for help

2.I supply a way to the script and it checks if the way is correct exp "0,1" "1,200" "200,3" (this is an correct way)

But this for exp is wrong "0,1" "3,400" "501,2" "2,33"

So if the programm see that there is somthing missing is should insert the missing steps, but there are somtimes more than 1 way so it should use the shortest way, and if you can see in the exp there can be missing somthing in the beginning followed by something correct and then followed by somthing missing to the end

It should not touch parts that are ok and only insert the shortest way missing between the Transitions, and if there is no possible way it should tell no way found or so

I hope this is nice written and clear enough, to programm this i dont have a clue and only using a giant if constuct mess up somthing and my triy with some HoA wasent succesfull either, i need definatly more skill for somthing like that

every help is very welcome

Replies are listed 'Best First'.
Re: generating a Tree from Array and find the best way
by roboticus (Chancellor) on Apr 06, 2006 at 21:46 UTC
    That's a bit more than I want to bite off right now. However, I recently saw another monk here refer to the module Graph::Easy::Parser. You may want to take a look at it. It will help you turn your list of edges into a graph. I don't know about filling in missing nodes or not, but I wouldn't be surprised if some tools for that are in there as well.

    Once you start looking into the Graph modules, you'll see that they have ways to create HTML, ASCII, and many other useful output formats. Try going to and getting some of the Graph modules and work through the examples. Then you'll be able to ask smaller questions......8^)

    Hope this helps a little...


      thx for the hint im now reading the Graph::Easy::Parser, and maybe my question is somkind of challenge for someone who is borred at the moment ;D

      well the Graph thing looks good i made somthing quick and dirty

      now i just need to do it automaticly because a few things needs to be clear when you have more then one connection it depends on the order of notes if its going trough or not

      for exp if you switch the last 2 lines in the code it will generate an compiler error, so i need to figure out how to do it manually , but im in bed now in 4 h i need to get to work

      thx again for the hint
      UPDATE i get that this is maybe to complex for this module because lots of connections are messed up and as an html file it spit out can only place 22 nodes out of 43 , but i will test tomorrow more

      UPDATE 2so here is some more optimised version im atm writing som script that check all possible transitions and will link those who are same if the second pair is reversed as a double connection <-> and not as -> this save alot of lines in the tree, i find some eq testing for my second problem and will look this up but im not sure if i get it ;D

Re: generating a Tree from Array and find the best way
by jdporter (Canon) on Apr 07, 2006 at 14:46 UTC

    It's almost like you wrote a textbook problem for a graph module. :-)

    Here's my solution. Essentially all the work is done by the module.

    We're building the house of the future together.

      great superb and so on
      your code is working great ive implement it in the main script so the vertexes are generated out of a DB query and states are given from a ticket and the new path is used for the stat
      really awsome

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://541741]
Approved by jdporter
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2017-10-21 18:34 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (270 votes). Check out past polls.