Graphs, Graphs, Graphs - RobinBalzer/approximateQueries GitHub Wiki

Below you'll find the properties of each graph in this project

QueryGraph

QueryNode

  • String identifier (name of the node)
  • boolean initialState
  • boolean finalState
  • LinkedList edges (list of emerging edges from this vertex)

QueryEdges

  • QueryNode source (source of the edge)
  • QueryNode target (target of the edge)
  • String label (label of the edge)

We move from source to target if we read label.

TransducerGraph

TransducerNode

  • String identifier (name of the node)
  • boolean initialState
  • boolean finalState
  • LinkedList edges (list of emerging edges from this vertex)

TransducerEdge

  • TransducerNode source (source of the node)
  • TransducerNode target (target of the node)
  • String incomingString ("read" label of the edge)
  • String outgoingString ("write" label of the edge)
  • double cost (cost of the replacement operation)

We move from source to target if we read incomingString and replace it with outgoingString at cost k.

DatabaseGraph

DatabaseNode

  • String identifier
  • LinkedList edges (list of emerging edges from this vertex)

The databaseNodes are always initial and final since their initial/finalState should not influence the productAutomaton at all.

DatabaseEdge

  • DatabaseNode source (source of the edge)
  • DatabaseNode target (target of the edge)
  • String label (label of the edge)

We move from source to target if we read the label.

ProductAutomatonGraph

This gets a bit bigger since we merge all three previous graphs into one graph while keeping all relevant information.

ProductAutomatonNode

  • Triplet<QueryNode, TransducerNode, DatabaseNode> identifier (the identifier now is a triplet that contains one of each node types.)
  • boolean initialState
  • boolean finalState
  • Double weight (weight/cost that is needed to reach this node from an initial node. -> important for Dijkstra later on)
  • LinkedList edges (list of emerging edges from this vertex)

Example

(s0, t0, a): ProductAutomatonNode, with

  • s0: QueryNode.identifier
  • t0: TransducerNode.identifier
  • a: DatabaseNode.identifier

ProductAutomatonEdge

  • ProductAutomatonNode source (source of the edge)
  • ProductAutomatonNode target (target of the edge)
  • String incomingString ("read" label of the edge)
  • String outgoingString ("write" label of the edge)
  • double cost (cost of the replacement operation)

Example

(s0, t0, c) -[ u1, u2, 0.0]-> (s1, t0, d): ProductAutomatonEdge, with

  • (s0, t0, c) and (s1, t0, d): ProductAutomatonNode

    • s0 and s1: QueryNode.identifier
    • t0: TransducerNode.identifier
    • c and d: Database.identifier

  • u1: ProductAutomatonEdge.incomingString

  • u2: ProductAutomatonEdge.outgoingString

  • 0.0: ProductAutomatonEdge.cost

⚠️ **GitHub.com Fallback** ⚠️