algorithm - pseudo-code for visiting a state machine -
i want write pseudo-code visiting state machine using dfs. state machine can considered directed graph. following algorithm cormen book uses dfs algorithm visit graph.
dfs-visit(g, u) //g= graph, u=root vertex u.color = gray each v g.adjacents(u) //edge (u, v) if v.color == white dfs-visit(g, v)
state machine can have multiple edges between 2 vertices. , above algorithm stores edges in adjacency list. have implemented algorithm in java following classes,
class node{ string name; .... arraylist<transition> transitions; void addtransition(transition tr); } class transition { string src; string dest; }
with above given information, have built state machine node , transition objects. want modify above algorithm don't have graph object g. have access root object.
can modify above algorithm below?
dfs-visit(root) //root node root.color = gray each t root.gettransitions() //t=transition v = t.getdestination() //v=destination of t if v.color == white dfs-visit(v)
the algorithm independent of implementation. actually, it's other way around. question should asking this: "do proprietary implementation has exact properties required algorithm?"
the algorithm has few strict demands. need set of nodes , set of edges, each edge connects 2 nodes. that's generic definition of graph. how acquire, store , process these sets irrelevant algorithm. algorithm step need access given node set , access set of neighbors. you've presented seems fine (of course, next step you'll need progress next node after root).
Comments
Post a Comment