1<?php
2# MantisBT - A PHP based bugtracking system
3
4# MantisBT is free software: you can redistribute it and/or modify
5# it under the terms of the GNU General Public License as published by
6# the Free Software Foundation, either version 2 of the License, or
7# (at your option) any later version.
8#
9# MantisBT is distributed in the hope that it will be useful,
10# but WITHOUT ANY WARRANTY; without even the implied warranty of
11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12# GNU General Public License for more details.
13#
14# You should have received a copy of the GNU General Public License
15# along with MantisBT.  If not, see <http://www.gnu.org/licenses/>.
16
17/**
18 * GraphViz API
19 *
20 * Wrapper classes around GraphViz utilities (dot and neato) for
21 * directed and undirected graph generation. These wrappers are enhanced
22 * enough just to support relationship_graph_api.php. They don't
23 * support subgraphs yet.
24 *
25 * The original Graphviz package including documentation is available at:
26 * 	- https://www.graphviz.org/
27 *
28 * @package CoreAPI
29 * @subpackage GraphVizAPI
30 * @author Juliano Ravasi Ferraz <jferraz at users sourceforge net>
31 * @copyright Copyright 2002  MantisBT Team - mantisbt-dev@lists.sourceforge.net
32 * @link http://www.mantisbt.org
33 *
34 * @uses constant_inc.php
35 * @uses utility_api.php
36 */
37
38require_api( 'constant_inc.php' );
39require_api( 'utility_api.php' );
40
41# constant(s) defining the output formats supported by dot and neato.
42define( 'GRAPHVIZ_ATTRIBUTED_DOT', 0 );
43define( 'GRAPHVIZ_PS', 1 );
44define( 'GRAPHVIZ_HPGL', 2 );
45define( 'GRAPHVIZ_PCL', 3 );
46define( 'GRAPHVIZ_MIF', 4 );
47define( 'GRAPHVIZ_PLAIN', 6 );
48define( 'GRAPHVIZ_PLAIN_EXT', 7 );
49define( 'GRAPHVIZ_GIF', 11 );
50define( 'GRAPHVIZ_JPEG', 12 );
51define( 'GRAPHVIZ_PNG', 13 );
52define( 'GRAPHVIZ_WBMP', 14 );
53define( 'GRAPHVIZ_XBM', 15 );
54define( 'GRAPHVIZ_ISMAP', 16 );
55define( 'GRAPHVIZ_IMAP', 17 );
56define( 'GRAPHVIZ_CMAP', 18 );
57define( 'GRAPHVIZ_CMAPX', 19 );
58define( 'GRAPHVIZ_VRML', 20 );
59define( 'GRAPHVIZ_SVG', 25 );
60define( 'GRAPHVIZ_SVGZ', 26 );
61define( 'GRAPHVIZ_CANONICAL_DOT', 27 );
62define( 'GRAPHVIZ_PDF', 28 );
63
64/**
65 * Base class for graph creation and manipulation. By default,
66 * undirected graphs are generated. For directed graphs, use Digraph
67 * class.
68 */
69class Graph {
70	/**
71	 * Name
72	 */
73	public $name = 'G';
74
75	/**
76	 * Attributes
77	 */
78	public $attributes = array();
79
80	/**
81	 * Default node
82	 */
83	public $default_node = null;
84
85	/**
86	 * Default edge
87	 */
88	public $default_edge = null;
89
90	/**
91	 * Nodes
92	 */
93	public $nodes = array();
94
95	/**
96	 * Edges
97	 */
98	public $edges = array();
99
100	/**
101	 * Graphviz tool
102	 */
103	public $graphviz_tool;
104
105	/**
106	 * Formats
107	 */
108	public $formats = array(
109		'dot' => array(
110			'binary' => false,
111			'type' => GRAPHVIZ_ATTRIBUTED_DOT,
112			'mime' => 'text/x-graphviz',
113		),
114		'ps' => array(
115			'binary' => false,
116			'type' => GRAPHVIZ_PS,
117			'mime' => 'application/postscript',
118		),
119		'hpgl' => array(
120			'binary' => true,
121			'type' => GRAPHVIZ_HPGL,
122			'mime' => 'application/vnd.hp-HPGL',
123		),
124		'pcl' => array(
125			'binary' => true,
126			'type' => GRAPHVIZ_PCL,
127			'mime' => 'application/vnd.hp-PCL',
128		),
129		'mif' => array(
130			'binary' => true,
131			'type' => GRAPHVIZ_MIF,
132			'mime' => 'application/vnd.mif',
133		),
134		'gif' => array(
135			'binary' => true,
136			'type' => GRAPHVIZ_GIF,
137			'mime' => 'image/gif',
138		),
139		'jpg' => array(
140			'binary' => false,
141			'type' => GRAPHVIZ_JPEG,
142			'mime' => 'image/jpeg',
143		),
144		'jpeg' => array(
145			'binary' => true,
146			'type' => GRAPHVIZ_JPEG,
147			'mime' => 'image/jpeg',
148		),
149		'png' => array(
150			'binary' => true,
151			'type' => GRAPHVIZ_PNG,
152			'mime' => 'image/png',
153		),
154		'wbmp' => array(
155			'binary' => true,
156			'type' => GRAPHVIZ_WBMP,
157			'mime' => 'image/vnd.wap.wbmp',
158		),
159		'xbm' => array(
160			'binary' => false,
161			'type' => GRAPHVIZ_XBM,
162			'mime' => 'image/x-xbitmap',
163		),
164		'ismap' => array(
165			'binary' => false,
166			'type' => GRAPHVIZ_ISMAP,
167			'mime' => 'text/plain',
168		),
169		'imap' => array(
170			'binary' => false,
171			'type' => GRAPHVIZ_IMAP,
172			'mime' => 'application/x-httpd-imap',
173		),
174		'cmap' => array(
175			'binary' => false,
176			'type' => GRAPHVIZ_CMAP,
177			'mime' => 'text/html',
178		),
179		'cmapx' => array(
180			'binary' => false,
181			'type' => GRAPHVIZ_CMAPX,
182			'mime' => 'application/xhtml+xml',
183		),
184		'vrml' => array(
185			'binary' => true,
186			'type' => GRAPHVIZ_VRML,
187			'mime' => 'x-world/x-vrml',
188		),
189		'svg' => array(
190			'binary' => false,
191			'type' => GRAPHVIZ_SVG,
192			'mime' => 'image/svg+xml',
193		),
194		'svgz' => array(
195			'binary' => true,
196			'type' => GRAPHVIZ_SVGZ,
197			'mime' => 'image/svg+xml',
198		),
199		'pdf' => array(
200			'binary' => true,
201			'type' => GRAPHVIZ_PDF,
202			'mime' => 'application/pdf',
203		),
204	);
205
206	/**
207	 * Constructor for Graph objects.
208	 * @param string $p_name       Graph name.
209	 * @param array  $p_attributes Attributes.
210	 * @param string $p_tool       Graph generation tool.
211	 */
212	function __construct( $p_name = 'G', array $p_attributes = array(), $p_tool = 'neato' ) {
213		if( is_string( $p_name ) ) {
214			$this->name = $p_name;
215		}
216
217		$this->set_attributes( $p_attributes );
218
219		$this->graphviz_tool = $p_tool;
220	}
221
222	/**
223	 * Sets graph attributes.
224	 * @param array $p_attributes Attributes.
225	 * @return void
226	 */
227	function set_attributes( array $p_attributes ) {
228		if( is_array( $p_attributes ) ) {
229			$this->attributes = $p_attributes;
230		}
231	}
232
233	/**
234	 * Sets default attributes for all nodes of the graph.
235	 * @param array $p_attributes Attributes.
236	 * @return void
237	 */
238	function set_default_node_attr( array $p_attributes ) {
239		if( is_array( $p_attributes ) ) {
240			$this->default_node = $p_attributes;
241		}
242	}
243
244	/**
245	 * Sets default attributes for all edges of the graph.
246	 * @param array $p_attributes Attributes.
247	 * @return void
248	 */
249	 function set_default_edge_attr( array $p_attributes ) {
250		if( is_array( $p_attributes ) ) {
251			$this->default_edge = $p_attributes;
252		}
253	}
254
255	/**
256	 * Adds a node to the graph.
257	 * @param string $p_name       Node name.
258	 * @param array  $p_attributes Attributes.
259	 * @return void
260	 */
261	 function add_node( $p_name, array $p_attributes = array() ) {
262		if( is_array( $p_attributes ) ) {
263			$this->nodes[$p_name] = $p_attributes;
264		}
265	}
266
267	/**
268	 * Adds an edge to the graph.
269	 * @param string $p_src        Source.
270	 * @param string $p_dst        Destination.
271	 * @param array  $p_attributes Attributes.
272	 * @return void
273	 */
274	 function add_edge( $p_src, $p_dst, array $p_attributes = array() ) {
275		if( is_array( $p_attributes ) ) {
276			$this->edges[] = array(
277				'src' => $p_src,
278				'dst' => $p_dst,
279				'attributes' => $p_attributes,
280			);
281		}
282	}
283
284	/**
285	 * Check if an edge is already present.
286	 * @param string $p_src Source.
287	 * @param string $p_dst Destination.
288	 * @return boolean
289	 */
290	function is_edge_present( $p_src, $p_dst ) {
291		foreach( $this->edges as $t_edge ) {
292			if( $t_edge['src'] == $p_src && $t_edge['dst'] == $p_dst ) {
293				return true;
294			}
295		}
296		return false;
297	}
298
299	/**
300	 * Generates an undirected graph representation (suitable for neato).
301	 * @return void
302	 */
303	function generate() {
304		echo 'graph ' . $this->name . ' {' . "\n";
305
306		$this->_print_graph_defaults();
307
308		foreach( $this->nodes as $t_name => $t_attr ) {
309			$t_name = '"' . addcslashes( $t_name, "\0..\37\"\\" ) . '"';
310			$t_attr = $this->_build_attribute_list( $t_attr );
311			echo "\t" . $t_name . ' ' . $t_attr . ";\n";
312		}
313
314		foreach( $this->edges as $t_edge ) {
315			$t_src = '"' . addcslashes( $t_edge['src'], "\0..\37\"\\" ) . '"';
316			$t_dst = '"' . addcslashes( $t_edge['dst'], "\0..\37\"\\" ) . '"';
317			$t_attr = $t_edge['attributes'];
318			$t_attr = $this->_build_attribute_list( $t_attr );
319			echo "\t" . $t_src . ' -- ' . $t_dst . ' ' . $t_attr . ";\n";
320		}
321
322		echo "};\n";
323	}
324
325	/**
326	 * Outputs a graph image or map in the specified format.
327	 * @param string  $p_format  Graphviz output format.
328	 * @param boolean $p_headers Whether to sent http headers.
329	 * @return void
330	 */
331	function output( $p_format = 'dot', $p_headers = false ) {
332		# Check if it is a recognized format.
333		if( !isset( $this->formats[$p_format] ) ) {
334			trigger_error( ERROR_GENERIC, ERROR );
335		}
336
337		$t_binary = $this->formats[$p_format]['binary'];
338		$t_type = $this->formats[$p_format]['type'];
339		$t_mime = $this->formats[$p_format]['mime'];
340
341		# Send Content-Type header, if requested.
342		if( $p_headers ) {
343			header( 'Content-Type: ' . $t_mime );
344		}
345		# Retrieve the source dot document into a buffer
346		ob_start();
347		$this->generate();
348		$t_dot_source = ob_get_contents();
349		ob_end_clean();
350
351		# Start dot process
352
353		$t_command = escapeshellcmd( $this->graphviz_tool . ' -T' . $p_format );
354		$t_descriptors = array(
355			0 => array( 'pipe', 'r', ),
356			1 => array( 'pipe', 'w', ),
357			2 => array( 'file', 'php://stderr', 'w', ),
358			);
359
360		$t_pipes = array();
361		$t_process = proc_open( $t_command, $t_descriptors, $t_pipes );
362
363		if( is_resource( $t_process ) ) {
364			# Filter generated output through dot
365			fwrite( $t_pipes[0], $t_dot_source );
366			fclose( $t_pipes[0] );
367
368			if( $p_headers ) {
369				# Headers were requested, use another output buffer to
370				# retrieve the size for Content-Length.
371				ob_start();
372				while( !feof( $t_pipes[1] ) ) {
373					echo fgets( $t_pipes[1], 1024 );
374				}
375				header( 'Content-Length: ' . ob_get_length() );
376				ob_end_flush();
377			} else {
378				# No need for headers, send output directly.
379				while( !feof( $t_pipes[1] ) ) {
380					print( fgets( $t_pipes[1], 1024 ) );
381				}
382			}
383
384			fclose( $t_pipes[1] );
385			proc_close( $t_process );
386		}
387	}
388
389	/**
390	 * PROTECTED function to build a node or edge attribute list.
391	 * @param array $p_attributes Attributes.
392	 * @return string
393	 */
394	function _build_attribute_list( array $p_attributes ) {
395		if( empty( $p_attributes ) ) {
396			return '';
397		}
398
399		$t_result = array();
400
401		foreach( $p_attributes as $t_name => $t_value ) {
402			if( !preg_match( '/[a-zA-Z]+/', $t_name ) ) {
403				continue;
404			}
405
406			if( is_string( $t_value ) ) {
407				$t_value = '"' . addcslashes( $t_value, "\0..\37\"\\" ) . '"';
408			} else if( is_integer( $t_value ) or is_float( $t_value ) ) {
409				$t_value = (string)$t_value;
410			} else {
411				continue;
412			}
413
414			$t_result[] = $t_name . '=' . $t_value;
415		}
416
417		return '[ ' . implode( ', ', $t_result ) . ' ]';
418	}
419
420	/**
421	 * PROTECTED function to print graph attributes and defaults.
422	 * @return void
423	 */
424	function _print_graph_defaults() {
425		foreach( $this->attributes as $t_name => $t_value ) {
426			if( !preg_match( '/[a-zA-Z]+/', $t_name ) ) {
427				continue;
428			}
429
430			if( is_string( $t_value ) ) {
431				$t_value = '"' . addcslashes( $t_value, "\0..\37\"\\" ) . '"';
432			} else if( is_integer( $t_value ) or is_float( $t_value ) ) {
433				$t_value = (string)$t_value;
434			} else {
435				continue;
436			}
437
438			echo "\t" . $t_name . '=' . $t_value . ";\n";
439		}
440
441		if( null !== $this->default_node ) {
442			$t_attr = $this->_build_attribute_list( $this->default_node );
443			echo "\t" . 'node ' . $t_attr . ";\n";
444		}
445
446		if( null !== $this->default_edge ) {
447			$t_attr = $this->_build_attribute_list( $this->default_edge );
448			echo "\t" . 'edge ' . $t_attr . ";\n";
449		}
450	}
451}
452
453/**
454 * Directed graph creation and manipulation.
455 */
456class Digraph extends Graph {
457	/**
458	 * Constructor for Digraph objects.
459	 * @param string $p_name       Name of the graph.
460	 * @param array  $p_attributes Attributes.
461	 * @param string $p_tool       Graphviz tool.
462	 */
463	function __construct( $p_name = 'G', array $p_attributes = array(), $p_tool = 'dot' ) {
464		parent::__construct( $p_name, $p_attributes, $p_tool );
465	}
466
467	/**
468	 * Generates a directed graph representation (suitable for dot).
469	 * @return void
470	 */
471	function generate() {
472		echo 'digraph ' . $this->name . ' {' . "\n";
473
474		$this->_print_graph_defaults();
475
476		foreach( $this->nodes as $t_name => $t_attr ) {
477			$t_name = '"' . addcslashes( $t_name, "\0..\37\"\\" ) . '"';
478			$t_attr = $this->_build_attribute_list( $t_attr );
479			echo "\t" . $t_name . ' ' . $t_attr . ";\n";
480		}
481
482		foreach( $this->edges as $t_edge ) {
483			$t_src = '"' . addcslashes( $t_edge['src'], "\0..\37\"\\" ) . '"';
484			$t_dst = '"' . addcslashes( $t_edge['dst'], "\0..\37\"\\" ) . '"';
485			$t_attr = $t_edge['attributes'];
486			$t_attr = $this->_build_attribute_list( $t_attr );
487			echo "\t" . $t_src . ' -> ' . $t_dst . ' ' . $t_attr . ";\n";
488		}
489
490		echo "};\n";
491	}
492}
493