generating a Tree from Array and find the best way

[ultibuzz]

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

Transitions

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

[roboticus]

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 www.cpan.org 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...

--roboticus

[ultibuzz]

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

Read more... (2 kB)

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

Read more... (2 kB)

[jdporter]

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.

Read more... (3 kB)

[ultibuzz]

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