Logo Search packages:      
Sourcecode: verilator version File versions  Download package

DfaGraph Class Reference

#include <V3GraphDfa.h>

Inheritance diagram for DfaGraph:

List of all members.

Detailed Description

The NFA graph consists of: DfaVertex(START) The starting point DfaVertex() Interior states DfaVertex(ACCEPT) The completion point

Transitions include a list of all inputs (arbitrary user pointers), or epsilon, represented as a empty list of inputs.

We're only looking for matches, so the only accepting states are at the end of the transformations. (If we want the complement, we call complement and the algorithm makes a REJECT state, then flips accept and reject for you.)

Common transforms:

"*": DfaVertex(START) --> [epsilon] -->DfaVertex(ACCEPT)

"L": ...->[ON_L]-->DfaVtx-->[epsilon]-->DfaVtx(ACCEPT)

"LR": ...->[ON_L]-->DfaVtx-->[epsilon]-->DfaVtx(ACCEPT) ->[ON_R]-->DfaVtx-->[epsilon]-/

"L|R": ...->DfaVtx-->[epsilon]-->DfaVtx-->[ON_L]-->DfaVtx()->[epsilon]-->DfaVtx(ACCEPT) \->[epsilon]-->DfaVtx-->[ON_R]-->DfaVtx()->[epsilon]-/

"L*": ...->DfaVtx-->[epsilon]-->DfaVtx-->[ON_L]-->DfaVtx()->[epsilon]-->DfaVtx(ACCEPT) | ^\----[epsilon]<-------/ | \->[epsilon]-----------------------------------------/

Definition at line 67 of file V3GraphDfa.h.

Public Member Functions

void acyclic (V3EdgeFuncP edgeFuncp)
 Make acyclical (into a tree) by breaking a minimal subset of cutable edges.
void clear ()
void clearColors ()
void deleteCutableOnlyEdges ()
 Delete any nodes with only outputs.
void dfaComplement ()
 Complement result (must already be dfa).
void dfaReduce ()
 Simplify a DFA automata.
virtual string dotRankDir ()
void dump (ostream &os=cout)
void dumpDotFile (const string &filename, bool colorAsSubgraph)
void dumpDotFilePrefixed (const string &nameComment, bool colorAsSubgraph=false)
DfaVertex * findStart ()
 Find start node.
virtual void loopsMessageCb (V3GraphVertex *vertexp)
virtual void loopsVertexCb (V3GraphVertex *vertexp)
void makeEdgesNonCutable (V3EdgeFuncP edgeFuncp)
 Any cutable edged become non-cutable.
void nfaToDfa ()
 Convert automata: NFA to DFA.
void order ()
void rank ()
void rank (V3EdgeFuncP edgeFuncp)
void removeRedundantEdges (V3EdgeFuncP edgeFuncp)
 Remove any redundant edges, weights become MAX of any other weight.
void removeRedundantEdgesSum (V3EdgeFuncP edgeFuncp)
 Remove any redundant edges, weights become SUM of any other weight.
void reportLoops (V3EdgeFuncP edgeFuncp, V3GraphVertex *vertexp)
 Call loopsVertexCb on any loops starting where specified.
void sortEdges ()
 Sort all edges and edges using the V3GraphEdge::sortCmp() function.
void sortVertices ()
 Sort all vertices and edges using the V3GraphVertex::sortCmp() function.
void stronglyConnected (V3EdgeFuncP edgeFuncp)
void userClearEdges ()
void userClearVertices ()
V3GraphVertex * verticesBeginp () const
void weaklyConnected (V3EdgeFuncP edgeFuncp)

Static Public Member Functions

static void debug (int level)
static void test ()

Protected Member Functions

void acyclicCut ()
void acyclicDFS ()
void acyclicDFSIterate (V3GraphVertex *vertexp, int depth, uint32_t currentRank)
void acyclicLoop (V3GraphVertex *vertexp, int depth)
void dumpEdge (ostream &os, V3GraphVertex *vertexp, V3GraphEdge *edgep)
double orderDFSIterate (V3GraphVertex *vertexp)
void verticesUnlink ()

Static Protected Member Functions

static int debug ()


class GraphAcyc
class V3GraphEdge
class V3GraphVertex

The documentation for this class was generated from the following files:

Generated by  Doxygen 1.6.0   Back to index