(index<- ) ./libgraphviz/lib.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri May 9 13:02:28 2014
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 /*! Generate files suitable for use with [Graphviz](http://www.graphviz.org/)
12
13 The `render` function generates output (e.g. an `output.dot` file) for
14 use with [Graphviz](http://www.graphviz.org/) by walking a labelled
15 graph. (Graphviz can then automatically lay out the nodes and edges
16 of the graph, and also optionally render the graph as an image or
17 other [output formats](
18 http://www.graphviz.org/content/output-formats), such as SVG.)
19
20 Rather than impose some particular graph data structure on clients,
21 this library exposes two traits that clients can implement on their
22 own structs before handing them over to the rendering function.
23
24 Note: This library does not yet provide access to the full
25 expressiveness of the [DOT language](
26 http://www.graphviz.org/doc/info/lang.html). For example, there are
27 many [attributes](http://www.graphviz.org/content/attrs) related to
28 providing layout hints (e.g. left-to-right versus top-down, which
29 algorithm to use, etc). The current intention of this library is to
30 emit a human-readable .dot file with very regular structure suitable
31 for easy post-processing.
32
33 # Examples
34
35 The first example uses a very simple graph representation: a list of
36 pairs of ints, representing the edges (the node set is implicit).
37 Each node label is derived directly from the int representing the node,
38 while the edge labels are all empty strings.
39
40 This example also illustrates how to use `MaybeOwnedVector` to return
41 an owned vector or a borrowed slice as appropriate: we construct the
42 node vector from scratch, but borrow the edge list (rather than
43 constructing a copy of all the edges from scratch).
44
45 The output from this example renders five nodes, with the first four
46 forming a diamond-shaped acyclic graph and then pointing to the fifth
47 which is cyclic.
48
49 ```rust
50 use dot = graphviz;
51 use graphviz::maybe_owned_vec::IntoMaybeOwnedVector;
52
53 type Nd = int;
54 type Ed = (int,int);
55 struct Edges(Vec<Ed>);
56
57 pub fn render_to<W:Writer>(output: &mut W) {
58 let edges = Edges(vec!((0,1), (0,2), (1,3), (2,3), (3,4), (4,4)));
59 dot::render(&edges, output).unwrap()
60 }
61
62 impl<'a> dot::Labeller<'a, Nd, Ed> for Edges {
63 fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example1") }
64
65 fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
66 dot::Id::new(format!("N{}", *n))
67 }
68 }
69
70 impl<'a> dot::GraphWalk<'a, Nd, Ed> for Edges {
71 fn nodes(&self) -> dot::Nodes<'a,Nd> {
72 // (assumes that |N| \approxeq |E|)
73 let &Edges(ref v) = self;
74 let mut nodes = Vec::with_capacity(v.len());
75 for &(s,t) in v.iter() {
76 nodes.push(s); nodes.push(t);
77 }
78 nodes.sort();
79 nodes.dedup();
80 nodes.into_maybe_owned()
81 }
82
83 fn edges(&'a self) -> dot::Edges<'a,Ed> {
84 let &Edges(ref edges) = self;
85 edges.as_slice().into_maybe_owned()
86 }
87
88 fn source(&self, e: &Ed) -> Nd { let &(s,_) = e; s }
89
90 fn target(&self, e: &Ed) -> Nd { let &(_,t) = e; t }
91 }
92
93 # pub fn main() { use std::io::MemWriter; render_to(&mut MemWriter::new()) }
94 ```
95
96 ```no_run
97 # pub fn render_to<W:Writer>(output: &mut W) { unimplemented!() }
98 pub fn main() {
99 use std::io::File;
100 let mut f = File::create(&Path::new("example1.dot"));
101 render_to(&mut f)
102 }
103 ```
104
105 Output from first example (in `example1.dot`):
106
107 ```ignore
108 digraph example1 {
109 N0[label="N0"];
110 N1[label="N1"];
111 N2[label="N2"];
112 N3[label="N3"];
113 N4[label="N4"];
114 N0 -> N1[label=""];
115 N0 -> N2[label=""];
116 N1 -> N3[label=""];
117 N2 -> N3[label=""];
118 N3 -> N4[label=""];
119 N4 -> N4[label=""];
120 }
121 ```
122
123 The second example illustrates using `node_label` and `edge_label` to
124 add labels to the nodes and edges in the rendered graph. The graph
125 here carries both `nodes` (the label text to use for rendering a
126 particular node), and `edges` (again a list of `(source,target)`
127 indices).
128
129 This example also illustrates how to use a type (in this case the edge
130 type) that shares substructure with the graph: the edge type here is a
131 direct reference to the `(source,target)` pair stored in the graph's
132 internal vector (rather than passing around a copy of the pair
133 itself). Note that this implies that `fn edges(&'a self)` must
134 construct a fresh `Vec<&'a (uint,uint)>` from the `Vec<(uint,uint)>`
135 edges stored in `self`.
136
137 Since both the set of nodes and the set of edges are always
138 constructed from scratch via iterators, we use the `collect()` method
139 from the `Iterator` trait to collect the nodes and edges into freshly
140 constructed growable `Vec` values (rather use the `into_maybe_owned`
141 from the `IntoMaybeOwnedVector` trait as was used in the first example
142 above).
143
144 The output from this example renders four nodes that make up the
145 Hasse-diagram for the subsets of the set `{x, y}`. Each edge is
146 labelled with the ⊆ character (specified using the HTML character
147 entity `&sube`).
148
149 ```rust
150 use dot = graphviz;
151 use std::str;
152
153 type Nd = uint;
154 type Ed<'a> = &'a (uint, uint);
155 struct Graph { nodes: Vec<&'static str>, edges: Vec<(uint,uint)> }
156
157 pub fn render_to<W:Writer>(output: &mut W) {
158 let nodes = vec!("{x,y}","{x}","{y}","{}");
159 let edges = vec!((0,1), (0,2), (1,3), (2,3));
160 let graph = Graph { nodes: nodes, edges: edges };
161
162 dot::render(&graph, output).unwrap()
163 }
164
165 impl<'a> dot::Labeller<'a, Nd, Ed<'a>> for Graph {
166 fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example2") }
167 fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
168 dot::Id::new(format!("N{}", n))
169 }
170 fn node_label<'a>(&'a self, n: &Nd) -> dot::LabelText<'a> {
171 dot::LabelStr(str::Slice(self.nodes.get(*n).as_slice()))
172 }
173 fn edge_label<'a>(&'a self, _: &Ed) -> dot::LabelText<'a> {
174 dot::LabelStr(str::Slice("⊆"))
175 }
176 }
177
178 impl<'a> dot::GraphWalk<'a, Nd, Ed<'a>> for Graph {
179 fn nodes(&self) -> dot::Nodes<'a,Nd> { range(0,self.nodes.len()).collect() }
180 fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { self.edges.iter().collect() }
181 fn source(&self, e: &Ed) -> Nd { let & &(s,_) = e; s }
182 fn target(&self, e: &Ed) -> Nd { let & &(_,t) = e; t }
183 }
184
185 # pub fn main() { use std::io::MemWriter; render_to(&mut MemWriter::new()) }
186 ```
187
188 ```no_run
189 # pub fn render_to<W:Writer>(output: &mut W) { unimplemented!() }
190 pub fn main() {
191 use std::io::File;
192 let mut f = File::create(&Path::new("example2.dot"));
193 render_to(&mut f)
194 }
195 ```
196
197 The third example is similar to the second, except now each node and
198 edge now carries a reference to the string label for each node as well
199 as that node's index. (This is another illustration of how to share
200 structure with the graph itself, and why one might want to do so.)
201
202 The output from this example is the same as the second example: the
203 Hasse-diagram for the subsets of the set `{x, y}`.
204
205 ```rust
206 use dot = graphviz;
207 use std::str;
208
209 type Nd<'a> = (uint, &'a str);
210 type Ed<'a> = (Nd<'a>, Nd<'a>);
211 struct Graph { nodes: Vec<&'static str>, edges: Vec<(uint,uint)> }
212
213 pub fn render_to<W:Writer>(output: &mut W) {
214 let nodes = vec!("{x,y}","{x}","{y}","{}");
215 let edges = vec!((0,1), (0,2), (1,3), (2,3));
216 let graph = Graph { nodes: nodes, edges: edges };
217
218 dot::render(&graph, output).unwrap()
219 }
220
221 impl<'a> dot::Labeller<'a, Nd<'a>, Ed<'a>> for Graph {
222 fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example3") }
223 fn node_id(&'a self, n: &Nd<'a>) -> dot::Id<'a> {
224 dot::Id::new(format!("N{:u}", n.val0()))
225 }
226 fn node_label<'a>(&'a self, n: &Nd<'a>) -> dot::LabelText<'a> {
227 let &(i, _) = n;
228 dot::LabelStr(str::Slice(self.nodes.get(i).as_slice()))
229 }
230 fn edge_label<'a>(&'a self, _: &Ed<'a>) -> dot::LabelText<'a> {
231 dot::LabelStr(str::Slice("⊆"))
232 }
233 }
234
235 impl<'a> dot::GraphWalk<'a, Nd<'a>, Ed<'a>> for Graph {
236 fn nodes(&'a self) -> dot::Nodes<'a,Nd<'a>> {
237 self.nodes.iter().map(|s|s.as_slice()).enumerate().collect()
238 }
239 fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> {
240 self.edges.iter()
241 .map(|&(i,j)|((i, self.nodes.get(i).as_slice()),
242 (j, self.nodes.get(j).as_slice())))
243 .collect()
244 }
245 fn source(&self, e: &Ed<'a>) -> Nd<'a> { let &(s,_) = e; s }
246 fn target(&self, e: &Ed<'a>) -> Nd<'a> { let &(_,t) = e; t }
247 }
248
249 # pub fn main() { use std::io::MemWriter; render_to(&mut MemWriter::new()) }
250 ```
251
252 ```no_run
253 # pub fn render_to<W:Writer>(output: &mut W) { unimplemented!() }
254 pub fn main() {
255 use std::io::File;
256 let mut f = File::create(&Path::new("example3.dot"));
257 render_to(&mut f)
258 }
259 ```
260
261 # References
262
263 * [Graphviz](http://www.graphviz.org/)
264
265 * [DOT language](http://www.graphviz.org/doc/info/lang.html)
266
267 */
268
269 #![crate_id = "graphviz#0.11-pre"]
270 #![crate_type = "rlib"]
271 #![crate_type = "dylib"]
272 #![license = "MIT/ASL2"]
273 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
274 html_favicon_url = "http://www.rust-lang.org/favicon.ico",
275 html_root_url = "http://static.rust-lang.org/doc/master")]
276
277 #![experimental]
278
279 use std::io;
280 use std::str;
281 use self::maybe_owned_vec::MaybeOwnedVector;
282
283 pub mod maybe_owned_vec;
284
285 /// The text for a graphviz label on a node or edge.
286 pub enum LabelText<'a> {
287 /// This kind of label preserves the text directly as is.
288 ///
289 /// Occurrences of backslashes (`\`) are escaped, and thus appear
290 /// as backslashes in the rendered label.
291 LabelStr(str::MaybeOwned<'a>),
292
293 /// This kind of label uses the graphviz label escString type:
294 /// http://www.graphviz.org/content/attrs#kescString
295 ///
296 /// Occurrences of backslashes (`\`) are not escaped; instead they
297 /// are interpreted as initiating an escString escape sequence.
298 ///
299 /// Escape sequences of particular interest: in addition to `\n`
300 /// to break a line (centering the line preceding the `\n`), there
301 /// are also the escape sequences `\l` which left-justifies the
302 /// preceding line and `\r` which right-justifies it.
303 EscStr(str::MaybeOwned<'a>),
304 }
305
306 // There is a tension in the design of the labelling API.
307 //
308 // For example, I considered making a `Labeller<T>` trait that
309 // provides labels for `T`, and then making the graph type `G`
310 // implement `Labeller<Node>` and `Labeller<Edge>`. However, this is
311 // not possible without functional dependencies. (One could work
312 // around that, but I did not explore that avenue heavily.)
313 //
314 // Another approach that I actually used for a while was to make a
315 // `Label<Context>` trait that is implemented by the client-specific
316 // Node and Edge types (as well as an implementation on Graph itself
317 // for the overall name for the graph). The main disadvantage of this
318 // second approach (compared to having the `G` type parameter
319 // implement a Labelling service) that I have encountered is that it
320 // makes it impossible to use types outside of the current crate
321 // directly as Nodes/Edges; you need to wrap them in newtype'd
322 // structs. See e.g. the `No` and `Ed` structs in the examples. (In
323 // practice clients using a graph in some other crate would need to
324 // provide some sort of adapter shim over the graph anyway to
325 // interface with this library).
326 //
327 // Another approach would be to make a single `Labeller<N,E>` trait
328 // that provides three methods (graph_label, node_label, edge_label),
329 // and then make `G` implement `Labeller<N,E>`. At first this did not
330 // appeal to me, since I had thought I would need separate methods on
331 // each data variant for dot-internal identifiers versus user-visible
332 // labels. However, the identifier/label distinction only arises for
333 // nodes; graphs themselves only have identifiers, and edges only have
334 // labels.
335 //
336 // So in the end I decided to use the third approach described above.
337
338 /// `Id` is a Graphviz `ID`.
339 pub struct Id<'a> {
340 name: str::MaybeOwned<'a>,
341 }
342
343 impl<'a> Id<'a> {
344 /// Creates an `Id` named `name`.
345 ///
346 /// The caller must ensure that the input conforms to an
347 /// identifier format: it must be a non-empty string made up of
348 /// alphanumeric or underscore characters, not beginning with a
349 /// digit (i.e. the regular expression `[a-zA-Z_][a-zA-Z_0-9]*`).
350 ///
351 /// (Note: this format is a strict subset of the `ID` format
352 /// defined by the DOT language. This function may change in the
353 /// future to accept a broader subset, or the entirety, of DOT's
354 /// `ID` format.)
355 pub fn new<Name:str::IntoMaybeOwned<'a>>(name: Name) -> Id<'a> {
356 let name = name.into_maybe_owned();
357 {
358 let mut chars = name.as_slice().chars();
359 assert!(is_letter_or_underscore(chars.next().unwrap()));
360 assert!(chars.all(is_constituent));
361 }
362 return Id{ name: name };
363
364 fn is_letter_or_underscore(c: char) -> bool {
365 in_range('a', c, 'z') || in_range('A', c, 'Z') || c == '_'
366 }
367 fn is_constituent(c: char) -> bool {
368 is_letter_or_underscore(c) || in_range('0', c, '9')
369 }
370 fn in_range(low: char, c: char, high: char) -> bool {
371 low as uint <= c as uint && c as uint <= high as uint
372 }
373 }
374
375 pub fn as_slice(&'a self) -> &'a str {
376 self.name.as_slice()
377 }
378
379 pub fn name(self) -> str::MaybeOwned<'a> {
380 self.name
381 }
382 }
383
384 /// Each instance of a type that implements `Label<C>` maps to a
385 /// unique identifier with respect to `C`, which is used to identify
386 /// it in the generated .dot file. They can also provide more
387 /// elaborate (and non-unique) label text that is used in the graphviz
388 /// rendered output.
389
390 /// The graph instance is responsible for providing the DOT compatible
391 /// identifiers for the nodes and (optionally) rendered labels for the nodes and
392 /// edges, as well as an identifier for the graph itself.
393 pub trait Labeller<'a,N,E> {
394 /// Must return a DOT compatible identifier naming the graph.
395 fn graph_id(&'a self) -> Id<'a>;
396
397 /// Maps `n` to a unique identifier with respect to `self`. The
398 /// implementor is responsible for ensuring that the returned name
399 /// is a valid DOT identifier.
400 fn node_id(&'a self, n: &N) -> Id<'a>;
401
402 /// Maps `n` to a label that will be used in the rendered output.
403 /// The label need not be unique, and may be the empty string; the
404 /// default is just the output from `node_id`.
405 fn node_label(&'a self, n: &N) -> LabelText<'a> {
406 LabelStr(self.node_id(n).name)
407 }
408
409 /// Maps `e` to a label that will be used in the rendered output.
410 /// The label need not be unique, and may be the empty string; the
411 /// default is in fact the empty string.
412 fn edge_label(&'a self, e: &E) -> LabelText<'a> {
413 let _ignored = e;
414 LabelStr(str::Slice(""))
415 }
416 }
417
418 impl<'a> LabelText<'a> {
419 fn escape_char(c: char, f: |char|) {
420 match c {
421 // not escaping \\, since Graphviz escString needs to
422 // interpret backslashes; see EscStr above.
423 '\\' => f(c),
424 _ => c.escape_default(f)
425 }
426 }
427 fn escape_str(s: &str) -> StrBuf {
428 let mut out = StrBuf::with_capacity(s.len());
429 for c in s.chars() {
430 LabelText::escape_char(c, |c| out.push_char(c));
431 }
432 out
433 }
434
435 /// Renders text as string suitable for a label in a .dot file.
436 pub fn escape(&self) -> ~str {
437 match self {
438 &LabelStr(ref s) => s.as_slice().escape_default(),
439 &EscStr(ref s) => LabelText::escape_str(s.as_slice()).into_owned(),
440 }
441 }
442 }
443
444 pub type Nodes<'a,N> = MaybeOwnedVector<'a,N>;
445 pub type Edges<'a,E> = MaybeOwnedVector<'a,E>;
446
447 // (The type parameters in GraphWalk should be associated items,
448 // when/if Rust supports such.)
449
450 /// GraphWalk is an abstraction over a directed graph = (nodes,edges)
451 /// made up of node handles `N` and edge handles `E`, where each `E`
452 /// can be mapped to its source and target nodes.
453 ///
454 /// The lifetime parameter `'a` is exposed in this trait (rather than
455 /// introduced as a generic parameter on each method declaration) so
456 /// that a client impl can choose `N` and `E` that have substructure
457 /// that is bound by the self lifetime `'a`.
458 ///
459 /// The `nodes` and `edges` method each return instantiations of
460 /// `MaybeOwnedVector` to leave implementors the freedom to create
461 /// entirely new vectors or to pass back slices into internally owned
462 /// vectors.
463 pub trait GraphWalk<'a, N, E> {
464 /// Returns all the nodes in this graph.
465 fn nodes(&'a self) -> Nodes<'a, N>;
466 /// Returns all of the edges in this graph.
467 fn edges(&'a self) -> Edges<'a, E>;
468 /// The source node for `edge`.
469 fn source(&'a self, edge: &E) -> N;
470 /// The target node for `edge`.
471 fn target(&'a self, edge: &E) -> N;
472 }
473
474 /// Renders directed graph `g` into the writer `w` in DOT syntax.
475 /// (Main entry point for the library.)
476 pub fn render<'a, N, E, G:Labeller<'a,N,E>+GraphWalk<'a,N,E>, W:Writer>(
477 g: &'a G,
478 w: &mut W) -> io::IoResult<()>
479 {
480 fn writeln<W:Writer>(w: &mut W, arg: &[&str]) -> io::IoResult<()> {
481 for &s in arg.iter() { try!(w.write_str(s)); }
482 w.write_char('\n')
483 }
484
485 fn indent<W:Writer>(w: &mut W) -> io::IoResult<()> {
486 w.write_str(" ")
487 }
488
489 try!(writeln(w, ["digraph ", g.graph_id().as_slice(), " {"]));
490 for n in g.nodes().iter() {
491 try!(indent(w));
492 let id = g.node_id(n);
493 let escaped = g.node_label(n).escape();
494 try!(writeln(w, [id.as_slice(),
495 "[label=\"", escaped.as_slice(), "\"];"]));
496 }
497
498 for e in g.edges().iter() {
499 let escaped_label = g.edge_label(e).escape();
500 try!(indent(w));
501 let source = g.source(e);
502 let target = g.target(e);
503 let source_id = g.node_id(&source);
504 let target_id = g.node_id(&target);
505 try!(writeln(w, [source_id.as_slice(), " -> ", target_id.as_slice(),
506 "[label=\"", escaped_label.as_slice(), "\"];"]));
507 }
508
509 writeln(w, ["}"])
510 }
511
512 #[cfg(test)]
513 mod tests {
514 use super::{Id, LabelText, LabelStr, EscStr, Labeller};
515 use super::{Nodes, Edges, GraphWalk, render};
516 use std::io::{MemWriter, BufReader, IoResult};
517 use std::str;
518
519 /// each node is an index in a vector in the graph.
520 type Node = uint;
521 struct Edge {
522 from: uint, to: uint, label: &'static str
523 }
524
525 fn Edge(from: uint, to: uint, label: &'static str) -> Edge {
526 Edge { from: from, to: to, label: label }
527 }
528
529 struct LabelledGraph {
530 /// The name for this graph. Used for labelling generated `digraph`.
531 name: &'static str,
532
533 /// Each node is an index into `node_labels`; these labels are
534 /// used as the label text for each node. (The node *names*,
535 /// which are unique identifiers, are derived from their index
536 /// in this array.)
537 ///
538 /// If a node maps to None here, then just use its name as its
539 /// text.
540 node_labels: Vec<Option<&'static str>>,
541
542 /// Each edge relates a from-index to a to-index along with a
543 /// label; `edges` collects them.
544 edges: Vec<Edge>,
545 }
546
547 // A simple wrapper around LabelledGraph that forces the labels to
548 // be emitted as EscStr.
549 struct LabelledGraphWithEscStrs {
550 graph: LabelledGraph
551 }
552
553 enum NodeLabels<L> {
554 AllNodesLabelled(Vec<L>),
555 UnlabelledNodes(uint),
556 SomeNodesLabelled(Vec<Option<L>>),
557 }
558
559 type Trivial = NodeLabels<&'static str>;
560
561 impl NodeLabels<&'static str> {
562 fn to_opt_strs(self) -> Vec<Option<&'static str>> {
563 match self {
564 UnlabelledNodes(len)
565 => Vec::from_elem(len, None).move_iter().collect(),
566 AllNodesLabelled(lbls)
567 => lbls.move_iter().map(
568 |l|Some(l)).collect(),
569 SomeNodesLabelled(lbls)
570 => lbls.move_iter().collect(),
571 }
572 }
573 }
574
575 impl LabelledGraph {
576 fn new(name: &'static str,
577 node_labels: Trivial,
578 edges: Vec<Edge>) -> LabelledGraph {
579 LabelledGraph {
580 name: name,
581 node_labels: node_labels.to_opt_strs(),
582 edges: edges
583 }
584 }
585 }
586
587 impl LabelledGraphWithEscStrs {
588 fn new(name: &'static str,
589 node_labels: Trivial,
590 edges: Vec<Edge>) -> LabelledGraphWithEscStrs {
591 LabelledGraphWithEscStrs {
592 graph: LabelledGraph::new(name, node_labels, edges)
593 }
594 }
595 }
596
597 fn id_name<'a>(n: &Node) -> Id<'a> {
598 Id::new(format!("N{:u}", *n))
599 }
600
601 impl<'a> Labeller<'a, Node, &'a Edge> for LabelledGraph {
602 fn graph_id(&'a self) -> Id<'a> {
603 Id::new(self.name.as_slice())
604 }
605 fn node_id(&'a self, n: &Node) -> Id<'a> {
606 id_name(n)
607 }
608 fn node_label(&'a self, n: &Node) -> LabelText<'a> {
609 match self.node_labels.get(*n) {
610 &Some(ref l) => LabelStr(str::Slice(l.as_slice())),
611 &None => LabelStr(id_name(n).name()),
612 }
613 }
614 fn edge_label(&'a self, e: & &'a Edge) -> LabelText<'a> {
615 LabelStr(str::Slice(e.label.as_slice()))
616 }
617 }
618
619 impl<'a> Labeller<'a, Node, &'a Edge> for LabelledGraphWithEscStrs {
620 fn graph_id(&'a self) -> Id<'a> { self.graph.graph_id() }
621 fn node_id(&'a self, n: &Node) -> Id<'a> { self.graph.node_id(n) }
622 fn node_label(&'a self, n: &Node) -> LabelText<'a> {
623 match self.graph.node_label(n) {
624 LabelStr(s) | EscStr(s) => EscStr(s),
625 }
626 }
627 fn edge_label(&'a self, e: & &'a Edge) -> LabelText<'a> {
628 match self.graph.edge_label(e) {
629 LabelStr(s) | EscStr(s) => EscStr(s),
630 }
631 }
632 }
633
634 impl<'a> GraphWalk<'a, Node, &'a Edge> for LabelledGraph {
635 fn nodes(&'a self) -> Nodes<'a,Node> {
636 range(0u, self.node_labels.len()).collect()
637 }
638 fn edges(&'a self) -> Edges<'a,&'a Edge> {
639 self.edges.iter().collect()
640 }
641 fn source(&'a self, edge: & &'a Edge) -> Node {
642 edge.from
643 }
644 fn target(&'a self, edge: & &'a Edge) -> Node {
645 edge.to
646 }
647 }
648
649 impl<'a> GraphWalk<'a, Node, &'a Edge> for LabelledGraphWithEscStrs {
650 fn nodes(&'a self) -> Nodes<'a,Node> {
651 self.graph.nodes()
652 }
653 fn edges(&'a self) -> Edges<'a,&'a Edge> {
654 self.graph.edges()
655 }
656 fn source(&'a self, edge: & &'a Edge) -> Node {
657 edge.from
658 }
659 fn target(&'a self, edge: & &'a Edge) -> Node {
660 edge.to
661 }
662 }
663
664 fn test_input(g: LabelledGraph) -> IoResult<~str> {
665 let mut writer = MemWriter::new();
666 render(&g, &mut writer).unwrap();
667 let mut r = BufReader::new(writer.get_ref());
668 r.read_to_str()
669 }
670
671 // All of the tests use raw-strings as the format for the expected outputs,
672 // so that you can cut-and-paste the content into a .dot file yourself to
673 // see what the graphviz visualizer would produce.
674
675 #[test]
676 fn empty_graph() {
677 let labels : Trivial = UnlabelledNodes(0);
678 let r = test_input(LabelledGraph::new("empty_graph", labels, vec!()));
679 assert_eq!(r.unwrap().as_slice(),
680 r#"digraph empty_graph {
681 }
682 "#);
683 }
684
685 #[test]
686 fn single_node() {
687 let labels : Trivial = UnlabelledNodes(1);
688 let r = test_input(LabelledGraph::new("single_node", labels, vec!()));
689 assert_eq!(r.unwrap().as_slice(),
690 r#"digraph single_node {
691 N0[label="N0"];
692 }
693 "#);
694 }
695
696 #[test]
697 fn single_edge() {
698 let labels : Trivial = UnlabelledNodes(2);
699 let result = test_input(LabelledGraph::new("single_edge", labels,
700 vec!(Edge(0, 1, "E"))));
701 assert_eq!(result.unwrap().as_slice(),
702 r#"digraph single_edge {
703 N0[label="N0"];
704 N1[label="N1"];
705 N0 -> N1[label="E"];
706 }
707 "#);
708 }
709
710 #[test]
711 fn single_cyclic_node() {
712 let labels : Trivial = UnlabelledNodes(1);
713 let r = test_input(LabelledGraph::new("single_cyclic_node", labels,
714 vec!(Edge(0, 0, "E"))));
715 assert_eq!(r.unwrap().as_slice(),
716 r#"digraph single_cyclic_node {
717 N0[label="N0"];
718 N0 -> N0[label="E"];
719 }
720 "#);
721 }
722
723 #[test]
724 fn hasse_diagram() {
725 let labels = AllNodesLabelled(vec!("{x,y}", "{x}", "{y}", "{}"));
726 let r = test_input(LabelledGraph::new(
727 "hasse_diagram", labels,
728 vec!(Edge(0, 1, ""), Edge(0, 2, ""),
729 Edge(1, 3, ""), Edge(2, 3, ""))));
730 assert_eq!(r.unwrap().as_slice(),
731 r#"digraph hasse_diagram {
732 N0[label="{x,y}"];
733 N1[label="{x}"];
734 N2[label="{y}"];
735 N3[label="{}"];
736 N0 -> N1[label=""];
737 N0 -> N2[label=""];
738 N1 -> N3[label=""];
739 N2 -> N3[label=""];
740 }
741 "#);
742 }
743
744 #[test]
745 fn left_aligned_text() {
746 let labels = AllNodesLabelled(vec!(
747 "if test {\
748 \\l branch1\
749 \\l} else {\
750 \\l branch2\
751 \\l}\
752 \\lafterward\
753 \\l",
754 "branch1",
755 "branch2",
756 "afterward"));
757
758 let mut writer = MemWriter::new();
759
760 let g = LabelledGraphWithEscStrs::new(
761 "syntax_tree", labels,
762 vec!(Edge(0, 1, "then"), Edge(0, 2, "else"),
763 Edge(1, 3, ";"), Edge(2, 3, ";" )));
764
765 render(&g, &mut writer).unwrap();
766 let mut r = BufReader::new(writer.get_ref());
767 let r = r.read_to_str();
768
769 assert_eq!(r.unwrap().as_slice(),
770 r#"digraph syntax_tree {
771 N0[label="if test {\l branch1\l} else {\l branch2\l}\lafterward\l"];
772 N1[label="branch1"];
773 N2[label="branch2"];
774 N3[label="afterward"];
775 N0 -> N1[label="then"];
776 N0 -> N2[label="else"];
777 N1 -> N3[label=";"];
778 N2 -> N3[label=";"];
779 }
780 "#);
781 }
782 }
libgraphviz/lib.rs:285:53-285:53 -enum- definition:
/// The text for a graphviz label on a node or edge.
pub enum LabelText<'a> {
/// This kind of label preserves the text directly as is.
references:- 3404: /// default is just the output from `node_id`.
405: fn node_label(&'a self, n: &N) -> LabelText<'a> {
406: LabelStr(self.node_id(n).name)
--
411: /// default is in fact the empty string.
412: fn edge_label(&'a self, e: &E) -> LabelText<'a> {
413: let _ignored = e;
--
418: impl<'a> LabelText<'a> {
419: fn escape_char(c: char, f: |char|) {
libgraphviz/lib.rs:338:29-338:29 -struct- definition:
/// `Id` is a Graphviz `ID`.
pub struct Id<'a> {
name: str::MaybeOwned<'a>,
references:- 5361: }
362: return Id{ name: name };
--
399: /// is a valid DOT identifier.
400: fn node_id(&'a self, n: &N) -> Id<'a>;
libgraphviz/lib.rs:480:4-480:4 -fn- definition:
fn writeln<W:Writer>(w: &mut W, arg: &[&str]) -> io::IoResult<()> {
for &s in arg.iter() { try!(w.write_str(s)); }
w.write_char('\n')
references:- 4509: writeln(w, ["}"])
510: }
libgraphviz/lib.rs:364:8-364:8 -fn- definition:
fn is_letter_or_underscore(c: char) -> bool {
in_range('a', c, 'z') || in_range('A', c, 'Z') || c == '_'
}
references:- 2358: let mut chars = name.as_slice().chars();
359: assert!(is_letter_or_underscore(chars.next().unwrap()));
360: assert!(chars.all(is_constituent));
--
367: fn is_constituent(c: char) -> bool {
368: is_letter_or_underscore(c) || in_range('0', c, '9')
369: }
libgraphviz/lib.rs:485:4-485:4 -fn- definition:
fn indent<W:Writer>(w: &mut W) -> io::IoResult<()> {
w.write_str(" ")
}
references:- 2490: for n in g.nodes().iter() {
491: try!(indent(w));
492: let id = g.node_id(n);
--
499: let escaped_label = g.edge_label(e).escape();
500: try!(indent(w));
501: let source = g.source(e);
libgraphviz/lib.rs:370:8-370:8 -fn- definition:
fn in_range(low: char, c: char, high: char) -> bool {
low as uint <= c as uint && c as uint <= high as uint
}
references:- 3364: fn is_letter_or_underscore(c: char) -> bool {
365: in_range('a', c, 'z') || in_range('A', c, 'Z') || c == '_'
366: }
367: fn is_constituent(c: char) -> bool {
368: is_letter_or_underscore(c) || in_range('0', c, '9')
369: }