Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/src/graphviz_parser.yy @ 45

Last change on this file since 45 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 14.2 KB
Line 
1%{
2//=======================================================================
3// Copyright 2001 University of Notre Dame.
4// Author: Lie-Quan Lee
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10
11#include <iostream>
12#include <fstream>
13#include <string>
14#include <map>
15#include <vector>
16
17#include <boost/config.hpp>
18#include <boost/graph/graphviz.hpp>
19
20#if defined BOOST_NO_STRINGSTREAM
21  //#include <strstream> //We cannot use it since there is a bug in strstream 
22#include <stdlib.h>
23#else
24#include <sstream>
25#endif
26
27using std::free;
28using std::malloc;
29
30#ifndef GRAPHVIZ_DIRECTED
31#error Need to define the GRAPHVIZ_DIRECTED macro to either 0 or 1
32#endif
33
34#if GRAPHVIZ_DIRECTED == 0
35#define GRAPHVIZ_GRAPH boost::GraphvizGraph
36#define yyrestart bgl_undir_restart
37#else
38#define GRAPHVIZ_GRAPH boost::GraphvizDigraph
39#define yyrestart bgl_dir_restart
40#endif
41
42#define YYPARSE_PARAM g
43
44#include "yystype.h"
45
46  extern void yyerror(char* str);
47  extern void yyrestart(FILE* str);
48  extern int yylex(YYSTYPE* lvalp);
49
50  enum AttrState {GRAPH_GRAPH_A, GRAPH_NODE_A, GRAPH_EDGE_A, NODE_A, EDGE_A};
51
52  using boost::GraphvizAttrList;
53
54  namespace graphviz {
55
56    typedef boost::graph_traits<GRAPHVIZ_GRAPH>::vertex_descriptor Vertex;
57    typedef boost::graph_traits<GRAPHVIZ_GRAPH>::edge_descriptor   Edge;
58    typedef GRAPHVIZ_GRAPH Subgraph;
59
60    static Vertex current_vertex;
61    static Edge   current_edge;
62    static Subgraph* current_graph = NULL;
63    static Subgraph* previous_graph = NULL;
64
65    static std::vector< std::pair<void*, bool>* > vlist;//store a list of rhs
66
67    static std::map<std::string,std::string> attributes;//store attributes temporarily
68    static AttrState attribute_state;
69
70    static std::map<std::string, Subgraph*> subgraphs;  //store the names of subgraphs
71    static std::map<std::string, Vertex> nodes;         //store the names of nodes
72
73    typedef std::map<std::string, Subgraph*>::iterator It;
74    typedef std::map<std::string, Vertex>::iterator Iter;
75
76    static const std::string& get_graph_name(const Subgraph& g) {
77      const boost::graph_property<Subgraph, boost::graph_name_t>::type&
78        name = boost::get_property(g, boost::graph_name);
79      return name;
80    }
81
82    static std::pair<Iter, bool> lookup(const std::string& name) {
83      //lookup in the top level
84      Iter it = nodes.find(name);
85      bool found = (it != nodes.end() );
86      return std::make_pair(it, found);
87    }
88   
89    static Vertex add_name(const std::string& name, GRAPHVIZ_GRAPH& g) {
90      Vertex v = boost::add_vertex(*current_graph);
91      v = current_graph->local_to_global(v);
92
93      //set the label of vertex, it could be overwritten later.
94      boost::property_map<GRAPHVIZ_GRAPH, boost::vertex_attribute_t>::type
95        va = boost::get(boost::vertex_attribute, g);
96      va[v]["label"] = name;
97     
98      //add v into the map so next time we will find it.
99      nodes[name] = v;
100      return v;
101    }
102
103    static std::pair<It, bool> lookup_subgraph(const std::string& name) {
104      It it = subgraphs.find(name);
105      bool found = (it != subgraphs.end() );
106      return std::make_pair(it, found);
107    }
108   
109    static Subgraph* create_subgraph(const std::string& name) {
110
111      Subgraph* new_subgraph = &(current_graph->create_subgraph());
112
113      subgraphs[name]        = new_subgraph;
114      return new_subgraph;
115    }
116
117   
118    static void set_attribute(GraphvizAttrList& p,
119                              const GraphvizAttrList& attr) {
120      GraphvizAttrList::const_iterator i, end;
121      for ( i=attr.begin(), end=attr.end(); i!=end; ++i)
122        p[i->first]=i->second;
123    }
124 
125    static void set_attribute(Subgraph& g,
126                              AttrState s, bool clear_attribute = true) {
127      typedef Subgraph Graph;
128      switch ( s ) {
129      case GRAPH_GRAPH_A:
130        {
131          boost::graph_property<Graph, boost::graph_graph_attribute_t>::type&
132            gga = boost::get_property(g, boost::graph_graph_attribute);
133          set_attribute(gga, attributes);
134        }
135        break;
136      case GRAPH_NODE_A:
137        {
138          boost::graph_property<Graph, boost::graph_vertex_attribute_t>::type&
139            gna = boost::get_property(g, boost::graph_vertex_attribute);
140          set_attribute(gna, attributes);
141        }
142        break;
143      case GRAPH_EDGE_A:
144        {
145          boost::graph_property<Graph, boost::graph_edge_attribute_t>::type&
146            gea = boost::get_property(g, boost::graph_edge_attribute);
147          set_attribute(gea, attributes);
148        }
149        break;
150      case NODE_A:
151        {
152          boost::property_map<Graph, boost::vertex_attribute_t>::type
153            va = boost::get(boost::vertex_attribute, g);    //va[v]
154          set_attribute(va[current_vertex], attributes);
155        }
156        break;
157      case EDGE_A:
158        {
159          boost::property_map<Graph, boost::edge_attribute_t>::type
160            ea = boost::get(boost::edge_attribute, g);      //ea[e]
161          set_attribute(ea[current_edge], attributes);
162        }
163        break;
164      }
165      if ( clear_attribute )
166        attributes.clear();
167    }
168
169
170    static void add_edges(const Vertex& u,
171                          const Vertex& v, GRAPHVIZ_GRAPH& g) {
172      graphviz::current_edge = boost::add_edge(u, v, g).first;
173      graphviz::set_attribute(g, EDGE_A, false);
174    }
175   
176    static void add_edges(Subgraph* G1, Subgraph* G2,
177                          GRAPHVIZ_GRAPH& g) {
178      boost::graph_traits<Subgraph>::vertex_iterator i, j, m, n;
179      for ( boost::tie(i, j) = boost::vertices(*G1); i != j; ++i) {
180        for ( boost::tie(m, n) = boost::vertices(*G2); m != n; ++m) {
181          graphviz::add_edges(G1->local_to_global(*i),
182                              G2->local_to_global(*m), g);
183        }
184      }
185    }
186
187    static void add_edges(Subgraph* G, const Vertex& v, GRAPHVIZ_GRAPH& g) {
188      boost::graph_traits<Subgraph>::vertex_iterator i, j;
189      for ( boost::tie(i, j) = boost::vertices(*G); i != j; ++i) {
190        graphviz::add_edges(G->local_to_global(*i), v, g);
191      }
192    }
193
194    static void add_edges(const Vertex& u, Subgraph* G, GRAPHVIZ_GRAPH& g) {
195      boost::graph_traits<Subgraph>::vertex_iterator i, j;
196      for ( boost::tie(i, j) = boost::vertices(*G); i != j; ++i) {
197        graphviz::add_edges(u, G->local_to_global(*i), g);
198      }
199    }
200
201    static std::string random_string() {
202      static int i=0;
203#if defined BOOST_NO_STRINGSTREAM
204      //std::strstream out;
205      char buf[256];
206      sprintf(buf, "default%i\0", i);
207      ++i;
208      return std::string(buf);
209#else
210      std::stringstream out;
211      out << "default" << i;
212      ++i;
213      return out.str();
214#endif
215    }
216
217
218    static void set_graph_name(const std::string& name) {
219      boost::graph_property<Subgraph, boost::graph_name_t>::type&
220        gea = boost::get_property(*current_graph, boost::graph_name);
221      gea = name;
222    }
223
224  } //namespace detail {
225
226%}
227
228
229%token<i>   GRAPH_T NODE_T EDGE_T DIGRAPH_T EDGEOP_T SUBGRAPH_T
230%token<ptr> ID_T
231
232%type<i>    graph graph_header graph_type stmt_list stmt attr_stmt attr_header
233%type<i>    attr_list attr compound_stmt node_stmt edge_stmt opt_attr
234%type<i>    graph_body edge_rhs_one edge_rhs graph_attr opt_graph_body
235%type<i>    nonempty_attr_list
236%type<ptr>  graph_name
237%type<ptr>  edge_endpoint node_id  node_port subgraph subgraph_header
238
239%pure_parser
240
241%%
242graph:        graph_header graph_body
243              ;
244
245graph_body:  '{' stmt_list '}' {$$=0;}
246              ;
247
248graph_header: graph_type graph_name
249  {
250    graphviz::vlist.clear();
251    graphviz::attributes.clear();
252    graphviz::subgraphs.clear();
253    graphviz::nodes.clear();
254    std::string* name = static_cast<std::string*>($2);
255    graphviz::previous_graph = static_cast<graphviz::Subgraph*>(g);
256    graphviz::current_graph = static_cast<graphviz::Subgraph*>(g);
257    graphviz::set_graph_name(*name);
258    delete name;
259  }
260              ;
261
262graph_type:   GRAPH_T | DIGRAPH_T
263              ;
264
265graph_name:   ID_T {$$ = $1; } | {$$=(void*)(new std::string("G")); }
266              ;
267
268stmt_list:    stmt_list stmt | stmt
269              ;
270
271semicolon:    ';' |
272              ;
273
274stmt:         attr_stmt semicolon |
275              compound_stmt  semicolon
276              ;
277
278attr_stmt:    attr_header '[' attr_list ']'
279  {
280    graphviz::set_attribute(*graphviz::current_graph,
281                          graphviz::attribute_state);
282  }
283              ;
284
285attr_header:  GRAPH_T  { graphviz::attribute_state = GRAPH_GRAPH_A; }
286              | NODE_T { graphviz::attribute_state = GRAPH_NODE_A; }
287              | EDGE_T { graphviz::attribute_state = GRAPH_EDGE_A; }
288              ;
289
290attr_list: nonempty_attr_list | {}
291              ;
292
293nonempty_attr_list: attr | nonempty_attr_list attr_separator attr
294              ;
295
296attr:         ID_T '=' ID_T
297  {
298    std::string* name  = static_cast<std::string*>($1);
299    std::string* value = static_cast<std::string*>($3);
300    graphviz::attributes[*name] = *value;
301    delete name;
302    delete value;
303  }
304              ;
305
306attr_separator:    ';' | ',' |
307              ;
308
309compound_stmt: node_stmt | edge_stmt  | graph_attr | subgraph { $$ = 0; }
310              ;
311
312graph_attr    : attr
313  {
314    graphviz::set_attribute(
315         *static_cast<graphviz::Subgraph*>(graphviz::current_graph),
316                            GRAPH_GRAPH_A);
317  }
318              ;
319
320node_stmt:    node_id opt_attr
321  {
322    graphviz::Vertex* temp   = static_cast<graphviz::Vertex*>($1);
323    graphviz::current_vertex = *temp;
324    graphviz::set_attribute(*static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM),
325                            NODE_A);
326    delete temp;
327    $$ = 0;
328  }
329              ;
330
331opt_attr:     '[' attr_list ']' { $$=0; } | { $$=0; }
332              ;
333
334node_id:      ID_T
335  {
336    std::string* name  = static_cast<std::string*>($1);
337    std::pair<graphviz::Iter, bool> result = graphviz::lookup(*name);
338    if (result.second) {
339      graphviz::current_vertex = result.first->second;
340      if (! graphviz::current_graph->is_root())
341        boost::add_vertex(graphviz::current_vertex, *graphviz::current_graph);
342    } else
343      graphviz::current_vertex = graphviz::add_name(*name, *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM)) ;
344    graphviz::Vertex* temp = new graphviz::Vertex(graphviz::current_vertex);
345    $$ = (void *)temp;
346    graphviz::attribute_state = NODE_A; 
347    delete name;
348  }
349              | node_port  { $$=$1; }
350              ;
351
352node_port:    ID_T ':' ID_T
353  {
354    //consider port as a special properties ?? --need work here
355    std::string* name = static_cast<std::string*>($1);
356    std::string* port = static_cast<std::string*>($3);
357
358    std::pair<graphviz::Iter, bool> result = graphviz::lookup(*name);
359    if (result.second)
360      graphviz::current_vertex = result.first->second;
361    else
362      graphviz::current_vertex = graphviz::add_name(*name, *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM)) ;
363    graphviz::Vertex* temp = new graphviz::Vertex(graphviz::current_vertex);
364    $$ = (void *)temp;
365    graphviz::attribute_state = NODE_A; 
366    delete name;
367    delete port;
368  }
369              ;
370
371edge_stmt:    edge_endpoint edge_rhs opt_attr
372  {
373
374    typedef std::pair<void*, bool>* Ptr;
375    Ptr source = static_cast<Ptr>($1);
376
377    for (std::vector<Ptr>::iterator it=graphviz::vlist.begin();
378         it !=graphviz::vlist.end(); ++it) {
379      if ( source->second ) {
380        if ( (*it)->second )
381          graphviz::add_edges(static_cast<graphviz::Subgraph*>(source->first),
382                            static_cast<graphviz::Subgraph*>((*it)->first),
383                            *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM));
384        else
385          graphviz::add_edges(static_cast<graphviz::Subgraph*>(source->first),
386                            *static_cast<graphviz::Vertex*>((*it)->first),
387                            *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM));
388      } else {
389        graphviz::Vertex* temp = static_cast<graphviz::Vertex*>(source->first);
390        if ( (*it)->second )
391          graphviz::add_edges(*temp,
392                            static_cast<graphviz::Subgraph*>((*it)->first),
393                            *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM));
394        else
395          graphviz::add_edges(*temp,
396                            *static_cast<graphviz::Vertex*>((*it)->first),
397                            *static_cast<GRAPHVIZ_GRAPH*>(YYPARSE_PARAM));
398        delete temp;
399      }
400
401      delete source;
402      source = *it;
403    }
404   
405    if ( ! source->second ) {
406      graphviz::Vertex* temp = static_cast<graphviz::Vertex*>(source->first);
407      delete temp;
408    }
409    delete source;
410
411    graphviz::attributes.clear();
412    graphviz::vlist.clear();
413  }
414              ;
415
416edge_rhs_one: EDGEOP_T edge_endpoint   
417  { graphviz::vlist.push_back(static_cast<std::pair<void*, bool>*>($2)); }
418;
419
420edge_rhs:     edge_rhs_one | edge_rhs edge_rhs_one
421              ;
422
423edge_endpoint:   node_id
424  {
425    std::pair<void*, bool>* temp = new std::pair<void*, bool>;
426    temp->first = $1;
427    temp->second = false;
428    $$ = (void*)temp;
429
430    graphviz::attribute_state = EDGE_A;
431  }
432                 | subgraph
433  {
434    std::pair<void*, bool>* temp = new std::pair<void*, bool>;
435    temp->first = $1;
436    temp->second = true;
437    $$ = (void*)temp;
438
439    graphviz::attribute_state = EDGE_A;
440  }
441              ;
442
443subgraph:    subgraph_header opt_graph_body
444  {
445    if ( $2 )
446      graphviz::current_graph = &graphviz::current_graph->parent();
447    else
448      graphviz::current_graph = graphviz::previous_graph;
449  }
450             |
451  {
452    graphviz::previous_graph = graphviz::current_graph;
453    std::string name = graphviz::random_string();
454    graphviz::Subgraph* temp = graphviz::create_subgraph(name);
455    graphviz::current_graph = temp;
456    graphviz::set_graph_name(name);
457
458    $$ = (void *) graphviz::current_graph;
459  } graph_body
460  {
461    graphviz::current_graph = &graphviz::current_graph->parent();
462  }
463              ;
464
465subgraph_header: SUBGRAPH_T ID_T
466  {
467    //lookup ID_T if it is already in the subgraph,
468    //if it is not, add a new subgraph
469    std::string* name  = static_cast<std::string*>($2);
470
471    std::pair<graphviz::It, bool> temp = graphviz::lookup_subgraph(*name);
472
473    graphviz::previous_graph = graphviz::current_graph;
474    if ( temp.second )  {//found
475      graphviz::current_graph = (temp.first)->second;
476    } else {
477      graphviz::current_graph = graphviz::create_subgraph(*name);
478      graphviz::set_graph_name(*name);
479    }
480
481    $$ = (void *) graphviz::current_graph;
482    delete name;
483  }
484              ;
485
486opt_graph_body: graph_body {$$ = 1; } |  { $$ = 0; }
487              ;
488%%
489
490namespace boost {
491 
492  void read_graphviz(const std::string& filename, GRAPHVIZ_GRAPH& g) {
493    FILE* file = fopen(filename.c_str(), "r");
494    yyrestart(file);
495    void* in = static_cast<void*>(file);
496    yyparse(static_cast<void*>(&g));
497  }
498
499  void read_graphviz(FILE* file, GRAPHVIZ_GRAPH& g) {
500    void* in = static_cast<void*>(file);
501    yyrestart(file);
502    yyparse(static_cast<void*>(&g));
503  }
504   
505}
506
Note: See TracBrowser for help on using the repository browser.