Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

DotParser.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Graph.h>
38 #include <ogdf/basic/HashArray.h>
39 
40 #include <ogdf/fileformats/DOT.h>
42 
43 #include <cstdio>
44 #include <vector>
45 #include <set>
46 #include <string>
47 
48 
49 namespace ogdf {
50 
51 namespace dot {
52 
53 class Parser;
54 struct SubgraphData;
55 
57 
114 class Ast {
115 public:
116  struct Graph;
117  struct StmtList;
118  struct NodeStmt;
119  struct EdgeStmt;
120  struct AttrStmt;
121  struct AsgnStmt;
122  struct Subgraph;
123  struct NodeId;
124  struct EdgeRhs;
125  struct AttrList;
126  struct AList;
127  struct Port;
128  struct CompassPt;
129 
130  struct Stmt;
131  struct EdgeLhs;
132 
133 private:
134  using Tokens = std::vector<Token>;
135  using Iterator = Tokens::const_iterator;
136 
139 
141 
142  Graph *parseGraph(
143  Iterator current, Iterator &rest);
145  Iterator current, Iterator &rest);
147  Iterator current, Iterator &rest);
149  Iterator current, Iterator &rest);
151  Iterator current, Iterator &rest);
153  Iterator current, Iterator &rest);
155  Iterator current, Iterator &rest);
157  Iterator current, Iterator &rest);
158  Stmt *parseStmt(
159  Iterator current, Iterator &rest);
161  Iterator current, Iterator &rest);
163  Iterator current, Iterator &rest);
164  AList *parseAList(
165  Iterator current, Iterator &rest);
166  Port *parsePort(
167  Iterator current, Iterator &rest);
169  Iterator current, Iterator &rest);
170 
171 public:
173 
176  explicit Ast(const Tokens &tokens);
177  ~Ast();
178 
180 
183  bool build();
184 
186  Graph *root() const;
187 
188  struct Graph {
189  const bool strict;
190  const bool directed;
191  std::string *id;
192 
194 
195  Graph(
196  const bool &paramStrict,
197  const bool &dir,
198  std::string *idString,
199  StmtList *statementList);
200  ~Graph();
201 
202  bool read(
203  Parser &P,
206  };
207 
208  struct StmtList {
211 
212  StmtList(
213  Stmt *headSTMT,
214  StmtList *tailStatementList);
215  ~StmtList();
216  };
217 
218  struct Stmt {
219  virtual ~Stmt() = 0;
220 
221  virtual bool read(
222  Parser &P,
225  const SubgraphData &data) = 0;
226  };
227 
228  struct NodeStmt : public Stmt {
231 
232  NodeStmt(
233  NodeId *nodeID,
234  AttrList *attrList);
235  ~NodeStmt();
236 
237  virtual bool read(
238  Parser &P,
241  const SubgraphData &data) override;
242  };
243 
244  struct EdgeStmt : public Stmt {
248 
249  EdgeStmt(
250  EdgeLhs *edgeLHS,
251  EdgeRhs *edgeRHS,
252  AttrList *attrList);
253  ~EdgeStmt();
254 
255  virtual bool read(
256  Parser &P,
259  const SubgraphData &data) override;
260  };
261 
262  struct AsgnStmt : public Stmt {
263  const std::string lhs;
264  const std::string rhs;
265 
266  AsgnStmt(
267  const std::string &lhsString,
268  const std::string &rhsString);
269  ~AsgnStmt();
270 
271  virtual bool read(
272  Parser &P,
275  const SubgraphData &data) override;
276  };
277 
278  struct AttrStmt : public Stmt {
279  enum class Type { graph, edge, node };
280 
283 
284  AttrStmt(
285  const Type &paramType,
286  AttrList *attrList);
287  ~AttrStmt();
288 
289  virtual bool read(
290  Parser &P,
293  const SubgraphData &data) override;
294  };
295 
296  struct EdgeLhs {
297  virtual ~EdgeLhs() = 0;
298 
299  virtual bool read(
300  Parser &P,
303  const SubgraphData &data) = 0;
304  };
305 
306  struct Subgraph : public Stmt, EdgeLhs {
307  std::string *id;
309 
310  Subgraph(
311  std::string *idString,
312  StmtList *statementList);
313  ~Subgraph();
314 
315  virtual bool read(
316  Parser &P,
319  const SubgraphData &data) override;
320  };
321 
322  struct NodeId : public EdgeLhs {
323  const std::string id;
325 
326  NodeId(
327  const std::string &idString,
328  Port *paramPort);
329  ~NodeId();
330 
331  virtual bool read(
332  Parser &P,
335  const SubgraphData &data) override;
336  };
337 
338  struct CompassPt {
339  enum class Type { n, ne, e, se, s, sw, w, nw, c, wildcard };
341 
342  CompassPt(
343  const Type &paramType);
344  ~CompassPt();
345  };
346 
347  struct Port {
348  std::string *id;
350 
351  Port(
352  std::string *idString,
353  CompassPt *compassPT);
354  ~Port();
355  };
356 
357  struct EdgeRhs {
360 
361  EdgeRhs(
362  EdgeLhs *headEdgeLHS,
363  EdgeRhs *tailEdgeRHS);
364  ~EdgeRhs();
365  };
366 
367  struct AttrList {
370 
371  AttrList(
372  AList *headAList,
373  AttrList *tailAttrList);
374  ~AttrList();
375  };
376 
377  struct AList {
380 
381  AList(
382  AsgnStmt *headAsgnStmt,
383  AList *tailAList);
384  ~AList();
385  };
386 };
387 
388 
390 
397 class Parser {
398 private:
399  std::istream &m_in;
400 
401  // Maps node id to Graph node.
403 
404  bool readGraph(
405  Graph &G, GraphAttributes *GA,
407 
408 public:
410  explicit Parser(std::istream &in);
411 
412  bool read(Graph &G);
413  bool read(Graph &G, GraphAttributes &GA);
414  bool read(Graph &G, ClusterGraph &C);
415  bool read(Graph &G, ClusterGraph &C, ClusterGraphAttributes &CA);
416 
418 
430  Graph &G, GraphAttributes *GA, ClusterGraph *C,
431  const SubgraphData &data,
432  const std::string &id);
433 };
434 
435 
437 struct SubgraphData {
439  std::vector<Ast::AttrList *> &nodeDefaults;
440  std::vector<Ast::AttrList *> &edgeDefaults;
441  std::set<node> &nodes;
442 
444 
450  SubgraphData(
451  cluster root,
452  std::vector<Ast::AttrList *> &nodeDefaultsVector,
453  std::vector<Ast::AttrList *> &edgeDefaultsVector,
454  std::set<node> &nodeSet);
455 
456 
459  cluster newRootCluster) const;
460 
463  std::vector<Ast::AttrList *> &newNodeDefaults,
464  std::vector<Ast::AttrList *> &newEdgeDefaults) const;
467  std::set<node> &newNodes) const;
468 };
469 
470 }
471 }
ogdf::dot::Ast::parsePort
Port * parsePort(Iterator current, Iterator &rest)
ogdf::dot::SubgraphData::SubgraphData
SubgraphData(cluster root, std::vector< Ast::AttrList * > &nodeDefaultsVector, std::vector< Ast::AttrList * > &edgeDefaultsVector, std::set< node > &nodeSet)
Initializes structure with given data.
ogdf::dot::Ast::AList::~AList
~AList()
HashArray.h
Declaration and implementation of HashArray class.
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
ogdf::dot::Ast::EdgeStmt
Definition: DotParser.h:244
ogdf::dot::Ast::NodeId::~NodeId
~NodeId()
ogdf::dot::Ast::parseNodeId
NodeId * parseNodeId(Iterator current, Iterator &rest)
Graph.h
Includes declaration of graph class.
ogdf::dot::Ast::AsgnStmt::AsgnStmt
AsgnStmt(const std::string &lhsString, const std::string &rhsString)
ogdf::dot::Ast::CompassPt::Type::w
@ w
ogdf::dot::Ast::EdgeRhs::EdgeRhs
EdgeRhs(EdgeLhs *headEdgeLHS, EdgeRhs *tailEdgeRHS)
ogdf::dot::Parser::m_in
std::istream & m_in
Definition: DotParser.h:399
ogdf::dot::Ast::Graph::read
bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA)
ogdf::dot::Ast::Graph::directed
const bool directed
Definition: DotParser.h:190
ogdf::dot::Ast::CompassPt::Type::n
@ n
ogdf::dot::Ast::StmtList
Definition: DotParser.h:208
ogdf::dot::Ast::Port::compassPt
CompassPt * compassPt
Definition: DotParser.h:349
ogdf::dot::Ast::AsgnStmt::rhs
const std::string rhs
Definition: DotParser.h:264
ogdf::dot::Ast::parseStmt
Stmt * parseStmt(Iterator current, Iterator &rest)
ogdf::dot::Ast::EdgeStmt::attrs
AttrList * attrs
Definition: DotParser.h:247
ogdf::dot::Ast::EdgeRhs::head
EdgeLhs * head
Definition: DotParser.h:358
ogdf::dot::Ast::EdgeStmt::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::Ast::parseAsgnStmt
AsgnStmt * parseAsgnStmt(Iterator current, Iterator &rest)
ogdf::dot::Parser::requestNode
node requestNode(Graph &G, GraphAttributes *GA, ClusterGraph *C, const SubgraphData &data, const std::string &id)
Perfoms a node query, returning node for given attribute.
ogdf::dot::Ast::Graph::strict
const bool strict
Definition: DotParser.h:189
ogdf::dot::Ast::parseAList
AList * parseAList(Iterator current, Iterator &rest)
ogdf::dot::Ast::CompassPt::Type::nw
@ nw
DotLexer.h
Declares stuff related to DOT format lexical analysis.
ogdf::dot::SubgraphData::edgeDefaults
std::vector< Ast::AttrList * > & edgeDefaults
Definition: DotParser.h:440
ogdf::dot::Ast::AList::AList
AList(AsgnStmt *headAsgnStmt, AList *tailAList)
ogdf::dot::Ast::Graph::id
std::string * id
Definition: DotParser.h:191
ogdf::dot::Ast::parseAttrStmt
AttrStmt * parseAttrStmt(Iterator current, Iterator &rest)
ogdf::dot::Ast::CompassPt::Type::se
@ se
ogdf::dot::Ast::AList::tail
AList * tail
Definition: DotParser.h:379
ogdf::dot::Ast::EdgeRhs::~EdgeRhs
~EdgeRhs()
ogdf::dot::SubgraphData::withNodes
SubgraphData withNodes(std::set< node > &newNodes) const
Returns almost the same structure, but with new node list.
ogdf::dot::Ast::NodeStmt::NodeStmt
NodeStmt(NodeId *nodeID, AttrList *attrList)
ogdf::dot::Parser::read
bool read(Graph &G)
ogdf::dot::Ast::EdgeStmt::EdgeStmt
EdgeStmt(EdgeLhs *edgeLHS, EdgeRhs *edgeRHS, AttrList *attrList)
ogdf::dot::Ast::Tokens
std::vector< Token > Tokens
Definition: DotParser.h:134
ogdf::dot::Ast::EdgeRhs::tail
EdgeRhs * tail
Definition: DotParser.h:359
ogdf::dot::Ast::AsgnStmt::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::Ast::AttrStmt::Type::graph
@ graph
ogdf::dot::Ast::EdgeStmt::rhs
EdgeRhs * rhs
Definition: DotParser.h:246
ogdf::dot::Ast::CompassPt
Definition: DotParser.h:338
ogdf::dot::Ast::Iterator
Tokens::const_iterator Iterator
Definition: DotParser.h:135
ogdf::dot::Ast::NodeStmt
Definition: DotParser.h:228
ogdf::dot::Ast::CompassPt::Type::s
@ s
ogdf::dot::Ast::EdgeLhs
Definition: DotParser.h:296
ogdf::dot::Ast::CompassPt::Type::wildcard
@ wildcard
ogdf::dot::Parser::Parser
Parser(std::istream &in)
Initializes parser class with given input (but does nothing to it).
ogdf::dot::Ast::CompassPt::CompassPt
CompassPt(const Type &paramType)
ogdf::dot::Ast::StmtList::head
Stmt * head
Definition: DotParser.h:209
ogdf::dot::Ast::EdgeLhs::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data)=0
ogdf::dot::Ast::EdgeRhs
Definition: DotParser.h:357
ogdf::dot::Ast::CompassPt::Type::c
@ c
ogdf::dot::SubgraphData::withDefaults
SubgraphData withDefaults(std::vector< Ast::AttrList * > &newNodeDefaults, std::vector< Ast::AttrList * > &newEdgeDefaults) const
Returns almost the same structure, but with new defaults.
ogdf::dot::Ast::Stmt::~Stmt
virtual ~Stmt()=0
ogdf::dot::Ast::Stmt
Definition: DotParser.h:218
ogdf::dot::Parser::readGraph
bool readGraph(Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA)
ogdf::dot::SubgraphData
A helper structure containing information for recursive graph reading.
Definition: DotParser.h:437
ogdf::ClusterElement
Representation of clusters in a clustered graph.
Definition: ClusterGraph.h:53
ogdf::dot::Ast::NodeStmt::~NodeStmt
~NodeStmt()
ogdf::dot::Ast::Subgraph::id
std::string * id
Definition: DotParser.h:307
ogdf::dot::Ast::CompassPt::~CompassPt
~CompassPt()
ogdf::ClusterGraphAttributes
Stores additional attributes of a clustered graph (like layout information).
Definition: ClusterGraphAttributes.h:47
ogdf::dot::Ast::AttrList::~AttrList
~AttrList()
ogdf::dot::Ast::CompassPt::Type
Type
Definition: DotParser.h:339
ogdf::dot::Ast::parseSubgraph
Subgraph * parseSubgraph(Iterator current, Iterator &rest)
ogdf::dot::Ast::NodeId::port
Port * port
Definition: DotParser.h:324
ogdf::dot::Ast::Stmt::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data)=0
ogdf::dot::Ast::Subgraph::statements
StmtList * statements
Definition: DotParser.h:308
ogdf::dot::Ast::AsgnStmt::~AsgnStmt
~AsgnStmt()
ogdf::dot::Ast::AttrStmt::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::SubgraphData::withCluster
SubgraphData withCluster(cluster newRootCluster) const
Returns almost the same structure, but with root cluster.
ogdf::dot::Ast::StmtList::~StmtList
~StmtList()
ogdf::dot::Ast::build
bool build()
Builds the DOT format AST.
ogdf::dot::Ast::parseNodeStmt
NodeStmt * parseNodeStmt(Iterator current, Iterator &rest)
ogdf::HashArray
Indexed arrays using hashing for element access.
Definition: HashArray.h:94
ogdf::dot::Ast::StmtList::StmtList
StmtList(Stmt *headSTMT, StmtList *tailStatementList)
ogdf::dot::Ast::AttrStmt::type
Type type
Definition: DotParser.h:281
ogdf::dot::Ast::NodeId
Definition: DotParser.h:322
ogdf::dot::Ast::AttrStmt::AttrStmt
AttrStmt(const Type &paramType, AttrList *attrList)
ogdf::dot::Ast::Port::Port
Port(std::string *idString, CompassPt *compassPT)
ogdf::dot::Ast::AttrStmt::attrs
AttrList * attrs
Definition: DotParser.h:282
ogdf::dot::Ast::m_graph
Graph * m_graph
Definition: DotParser.h:140
ogdf::dot::Ast::Graph
Definition: DotParser.h:188
ogdf::dot::Ast::Port::~Port
~Port()
ogdf::dot::Ast::AsgnStmt
Definition: DotParser.h:262
ogdf::dot::Ast::AsgnStmt::lhs
const std::string lhs
Definition: DotParser.h:263
ogdf::dot::Ast::Ast
Ast(const Tokens &tokens)
Initializes AST building but does not trigger the process itself.
ogdf::dot::Ast::AttrStmt::Type
Type
Definition: DotParser.h:279
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::dot::Ast::CompassPt::Type::ne
@ ne
ogdf::dot::Ast::CompassPt::Type::e
@ e
ogdf::dot::Ast::AttrStmt
Definition: DotParser.h:278
ogdf::dot::Ast::Subgraph::Subgraph
Subgraph(std::string *idString, StmtList *statementList)
ogdf::dot::Ast::parseAttrList
AttrList * parseAttrList(Iterator current, Iterator &rest)
ogdf::dot::Ast::AttrList::tail
AttrList * tail
Definition: DotParser.h:369
ogdf::dot::Ast::Port::id
std::string * id
Definition: DotParser.h:348
ogdf::dot::Ast::NodeId::id
const std::string id
Definition: DotParser.h:323
ogdf::dot::Parser
DOT format parser class.
Definition: DotParser.h:397
ogdf::dot::Ast::StmtList::tail
StmtList * tail
Definition: DotParser.h:210
ogdf::dot::Ast::AList::head
AsgnStmt * head
Definition: DotParser.h:378
ogdf::dot::Parser::m_nodeId
HashArray< std::string, node > m_nodeId
Definition: DotParser.h:402
ogdf::dot::Ast::parseGraph
Graph * parseGraph(Iterator current, Iterator &rest)
ogdf::dot::SubgraphData::nodes
std::set< node > & nodes
Definition: DotParser.h:441
ogdf::dot::Ast::AttrStmt::~AttrStmt
~AttrStmt()
ogdf::dot::SubgraphData::rootCluster
cluster rootCluster
Definition: DotParser.h:438
ogdf::dot::Ast::Graph::Graph
Graph(const bool &paramStrict, const bool &dir, std::string *idString, StmtList *statementList)
ogdf::dot::Ast::Subgraph::~Subgraph
~Subgraph()
ogdf::dot::Ast::root
Graph * root() const
Returns the root of the AST (nullptr if none).
ogdf::dot::Ast::Graph::statements
StmtList * statements
Definition: DotParser.h:193
ClusterGraphAttributes.h
Declares ClusterGraphAttributes, an extension of class GraphAttributes, to store clustergraph layout ...
ClusterGraph.h
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
ogdf::dot::Ast::EdgeStmt::lhs
EdgeLhs * lhs
Definition: DotParser.h:245
ogdf::dot::Ast::NodeStmt::nodeId
NodeId * nodeId
Definition: DotParser.h:229
ogdf::dot::Ast::CompassPt::type
Type type
Definition: DotParser.h:340
ogdf::dot::Ast::AttrList
Definition: DotParser.h:367
ogdf::dot::Ast::Port
Definition: DotParser.h:347
ogdf::dot::Ast::Subgraph
Definition: DotParser.h:306
ogdf::dot::Ast::m_tokens
const Tokens m_tokens
Definition: DotParser.h:137
ogdf::dot::Ast
DOT format abstract syntax tree class, based on official documentation.
Definition: DotParser.h:114
ogdf::dot::Ast::NodeId::NodeId
NodeId(const std::string &idString, Port *paramPort)
ogdf::dot::Ast::parseStmtList
StmtList * parseStmtList(Iterator current, Iterator &rest)
ogdf::dot::Ast::parseEdgeStmt
EdgeStmt * parseEdgeStmt(Iterator current, Iterator &rest)
DOT.h
DOT related enums and string conversion functions.
ogdf::dot::Ast::AList
Definition: DotParser.h:377
ogdf::ClusterGraph
Representation of clustered graphs.
Definition: ClusterGraph.h:291
ogdf::dot::SubgraphData::nodeDefaults
std::vector< Ast::AttrList * > & nodeDefaults
Definition: DotParser.h:439
ogdf::dot::Ast::AttrList::head
AList * head
Definition: DotParser.h:368
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::dot::Ast::~Ast
~Ast()
ogdf::dot::Ast::EdgeLhs::~EdgeLhs
virtual ~EdgeLhs()=0
ogdf::dot::Ast::m_tend
const Iterator m_tend
Definition: DotParser.h:138
ogdf::dot::Ast::AttrList::AttrList
AttrList(AList *headAList, AttrList *tailAttrList)
ogdf::dot::Ast::parseCompassPt
CompassPt * parseCompassPt(Iterator current, Iterator &rest)
ogdf::dot::Ast::NodeId::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::Ast::CompassPt::Type::sw
@ sw
ogdf::dot::Ast::Graph::~Graph
~Graph()
ogdf::dot::Ast::NodeStmt::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::Ast::parseEdgeRhs
EdgeRhs * parseEdgeRhs(Iterator current, Iterator &rest)
ogdf::dot::Ast::Subgraph::read
virtual bool read(Parser &P, ogdf::Graph &G, GraphAttributes *GA, ClusterGraph *C, ClusterGraphAttributes *CA, const SubgraphData &data) override
ogdf::dot::Ast::EdgeStmt::~EdgeStmt
~EdgeStmt()
ogdf::dot::Ast::NodeStmt::attrs
AttrList * attrs
Definition: DotParser.h:230
ogdf::dot::Ast::AttrStmt::Type::edge
@ edge