Minimizing transition graph

[noahjonesnoah]

Hi all, Im trying to write a program that minimizes a Transition Graph (its basically combining states with similar numbers). Basically, the algorithm is to first find states with the same 'a' and 'b' inputs, combine them, remove them from the 'leftovers' list, then find states that have either 'a' or 'b' and combine them.

Here is an example:

Initial TG:
final state is state 1
State  Input a  Input b
[0]    [3]      [1]
[1]    [1]      [4]
[2]    [3]      [1]
[3]    [6]      [3]
[4]    [2]      [7]
[5]    [1]      [3]
[6]    [2]      [5]
[7]    [1]      [3]

final state     leftover
[ 1 ]           [ 0 2 3 4 5 6 7 ]

final state    same a,b   leftover
[ 1 ]          [ 0 2 ]    [ 3 4 5 6 7 ]

final state    same a,b   same a,b    leftover
[ 1 ]          [ 0 2 ]    [5 7 ]      [ 3 4 6 ]

final state    same a,b   same a,b    same a     leftover
[ 1 ]          [ 0 2 ]    [ 5 7 ]     [ 4 6 ]    [ 3 ]

The Final Minimized TG now looks like this:
State  Input a  Input b
[0,2]  [3]      [1]
[1]    [1]      [4,6]
[3]    [4,6]    [3]
[4,6]  [0,2]    [5,7]
[5,7]  [1]      [3]

The problem Im facing is knowing how/what to do with the arrays since there could be any number of combinations depending on the amount of states in a given Transition Graph. Any ideas on how to code this?

Thanks

[Adak]

There may be a slick way to do this - sorta has that "smell" to it, but I don't know it.

Right now, I'd make a struct or use parallel arrays to sort the inputs by a and b (both). That will give you all matches of a and b pairs, immediaely. They'll be right next to each other. Be sure to shift the far left column of numbers, with every swap your program makes.

That makes searching for other matches very easy. Resort as needed. If you do this a few times by hand first, you'll find it worth your while as you code the program. I take it for granted that you have or will search Google, as well for this topic.

An interesting problem. I haven't seen that one before. Where is this type of problem solving used, Discrete Math?

[noahjonesnoah]

Thanks for the reply, its automata theory but discrete definitely ties into it. Im still not sure how to handle eveything though

[Adak]

Since I did most of my beer-drinking at home, instead of at a uni, I'm not sure either, but I'm very sure I could solve it, and you can too.

Sometimes, you get to use a handy map to find your way around, and sometimes you have to just use the environment and "just fly the plane". This is the latter case. You will learn how to do it, by doing it. ;)

I'd start with making a struct for each row, with the state, the input a, and the input b, and sort them with input a and input b as keys (that is, if a's are tied, in two structs as you sort, then sort by input b to reach the sorted position. Now you're ready to go on your first matching input "hunt".

Take it step by step to cut the problem down to size. Use a paper and pen if you can't see your way through it yet. Start ASAP, because it always takes longer when you don't have a map to help out.