user-tools/indent2graph

   1 #!/usr/bin/env perl
   2
   3 =pod
   4
   5 =head1 NAME
   6
   7 indent2graph - Generate graph out of whitespace-indented hierarchical text
   8
   9 =head1 SYNOPSIS
  10
  11 indent2graph < tree.txt > tree.dot
  12
  13 =head1 DESCRIPTION
  14
  15 Take line-based input, and output a directed graph in a given format, eg. dot(1) (see graphviz(1)).
  16 Each input line is a node.
  17 How much the line is indented (by leading spaces or TABs) determines its relation to the nodes of the surrounding lines.
  18 Lines which are indented to the same level, go to the same rank on the tree-like graph in the output.
  19 The graph may contain loops:
  20 lines with the same text (apart from the leading whitespace) are considered the same node
  21 (except when B<--tree> option is set).
  22
  23 =head1 EXAMPLE
  24
  25 Input:
  26
  27   /usr/bin/ssh
  28     libselinux
  29       libpcre2-8
  30     libgssapi_krb5
  31       libkrb5
  32         libkeyutils
  33         libresolv
  34       libk5crypto
  35       libcom_err
  36       libkrb5support
  37     libcrypto
  38     libz
  39     libc
  40
  41 Command:
  42
  43   indent2graph -f clojure | vijual draw-tree -
  44
  45 Output:
  46
  47                                 +------------+
  48                                 | /usr/bin/s |
  49                                 |     sh     |
  50                                 +-----+------+
  51                                       |
  52         +------------------------+----+---------+----------+--------+
  53         |                        |              |          |        |
  54   +-----+------+           +-----+------+ +-----+-----+ +--+---+ +--+---+
  55   | libselinux |           | libgssapi_ | | libcrypto | | libz | | libc |
  56   +-----+------+           |    krb5    | +-----------+ +------+ +------+
  57         |                  +-----+------+
  58         |                        |
  59         |             +----------+-+--------------+--------------+
  60   +-----+------+      |            |              |              |
  61   | libpcre2-8 | +----+----+ +-----+------+ +-----+------+ +-----+------+
  62   +------------+ | libkrb5 | | libk5crypt | | libcom_err | | libkrb5sup |
  63                  +----+----+ |     o      | +------------+ |    port    |
  64                       |      +------------+                +------------+
  65              +--------+-----+
  66              |              |
  67        +-----+------+ +-----+-----+
  68        | libkeyutil | | libresolv |
  69        |     s      | +-----------+
  70        +------------+
  71
  72 =head1 OPTIONS
  73
  74 =over 4
  75
  76 =item -f, --format I<FORMAT>
  77
  78 Output format.
  79
  80 =over 8
  81
  82 =item B<dot> (default)
  83
  84 The graphviz(1) (dot(1)) format.
  85
  86 =item B<pairs>
  87
  88 Simple B<TAB>-separated node name pairs, each describes a graph edge, 1 per line.
  89
  90 =item B<clojure>
  91
  92 Clojure-style nested vectors (represented as string).
  93 Useful for vijual(1).
  94
  95 =item B<grapheasy>
  96
  97 Graph::Easy(3pl)'s own "txt" format.
  98 With graph-easy(1) you can transform further into other formats, like GDL, VCG, ...
  99
 100 =item B<mermaid>
 101
 102 TODO
 103
 104 =back
 105
 106 =item -a, --ascendent
 107
 108 Indentation in the input represents ascendents, not descendents.
 109 Default is descendent chart.
 110 This influences to where arrows point.
 111
 112 =item -t, --tree
 113
 114 Interpret input strictly as a tree with no cycles.
 115 By default, without B<--tree>, lines with the same text represent the same node,
 116 so you can build arbitrary graph.
 117 With B<--tree>, you can build a tree-like graph in which different nodes may have the same text (label).
 118
 119 =item -d, --rankdir I<DIR>
 120
 121 This is the dot(1) graph's B<rankdir> parameter.
 122 This option is although specific to dot(1) format,
 123 but translated to B<grapheasy> if it is the chosen output format.
 124 I<DIR> is one of B<TB>, B<BT>, B<LR>, B<RL>.
 125 Default is B<LR> ie. left-to-right.
 126 See graphviz(1) documentation for details.
 127
 128 =back
 129
 130 =head1 SEE ALSO
 131
 132 indent2tree(1), graphviz(1), dot(1), vijual(1), Graph::Easy(3pl)
 133
 134 =cut
 135
 136
 137 use Data::Dumper;
 138 use Switch;
 139 use Getopt::Long qw/:config no_ignore_case no_bundling no_getopt_compat no_auto_abbrev require_order/;
 140 use Pod::Usage;
 141
 142
 143 sub esc
 144 {
 145         $_[0] =~ s/[\\\Q$_[1]\E]/\\$&/gr;
 146 }
 147
 148 sub esc_dquo
 149 {
 150         esc($_[0], '"');
 151 }
 152
 153 sub output_node_rec
 154 {
 155         my %p = @_;
 156         my $node_id = $p{id};
 157         my $node_text = $NodeText{$node_id};
 158
 159         switch ($OptFormat)
 160         {
 161                 case('clojure')
 162                 {
 163                         print '[';
 164                         print node_repr(text=>$node_text);
 165                         for my $child_node_id (@{$SubTree{$node_id}->{'children'}})
 166                         {
 167                                 print ' ';
 168                                 output_node_rec(id => $child_node_id);
 169                         }
 170                         print ']';
 171                 }
 172                 case(['dot', 'pairs', 'grapheasy'])
 173                 {
 174                         for my $child_node_id (@{$SubTree{$node_id}->{'children'}})
 175                         {
 176                                 print edge_repr({id=>$node_id, text=>$node_text}, {id=>$child_node_id, text=>$NodeText{$child_node_id}});
 177                         }
 178                         for my $child_node_id (@{$SubTree{$node_id}->{'children'}})
 179                         {
 180                                 output_node_rec(id=>$child_node_id);
 181                         }
 182                 }
 183         }
 184 }
 185
 186 sub node_repr
 187 {
 188         my %p = @_;
 189         switch ($OptFormat)
 190         {
 191                 case('dot')
 192                 {
 193                         if(defined $p{id}) { return $p{id}; }
 194                         else { return '"'.esc_dquo($p{text}).'"'; }
 195                 }
 196                 case('pairs') { return $p{text} =~ s/\t/\\t/gr; }
 197                 case('clojure')
 198                 {
 199                         if(defined $p{id}) { return ':'.$p{id}; }
 200                         else { return '"'.esc_dquo($p{text}).'"'; }
 201                 }
 202                 case('grapheasy')
 203                 {
 204                         if(defined $p{id}) { return '[ '.esc($p{id},   ']|').' ]'; }
 205                         else               { return '[ '.esc($p{text}, ']|').' ]'; }
 206                 }
 207         }
 208 }
 209
 210 sub edge_repr
 211 {
 212         my ($n1, $n2) = @_;
 213         switch($OptFormat)
 214         {
 215                 case('dot')       { return sprintf '%s -> %s;', node_repr(%$n1), node_repr(%$n2); }
 216                 case('pairs')     { return sprintf '%s\t%s',    node_repr(%$n1), node_repr(%$n2); }
 217                 case('clojure')   { return sprintf '[%s %s]',   node_repr(%$n1), node_repr(%$n2); }
 218                 case('grapheasy') { return sprintf '%s --> %s', node_repr(%$n1), node_repr(%$n2); }
 219         }
 220 }
 221
 222
 223 $OptFormat = 'dot';
 224 $OptAscendent = 0;
 225 $OptTree = 0;
 226 $OptRankdir = 'LR';
 227
 228 GetOptions(
 229         'a|ascendent!' => \$OptAscendent,
 230         'd|rankdir=s' => \$OptRankdir,
 231         'f|format=s' => \$OptFormat,
 232         't|tree!' => \$OptTree,
 233         'help' => sub { pod2usage(-exitval=>0, -verbose=>99); },
 234 ) or pod2usage(-exitval=>2, -verbose=>99);
 235
 236
 237 die "Output format 'pairs' and strict tree input is not supported.\n" if $OptFormat eq 'pairs' and $OptTree;
 238
 239 $GraphEasyGraphFlow = {qw/TB south LR east RL west BT north/}->{$OptRankdir};
 240
 241 while(<STDIN>)
 242 {
 243         /^(\s*)(.*)$/;
 244         my $indent_level = length $1;
 245         my $node = $2;
 246         my $node_id = $.;
 247         $NodeText{$node_id} = $node;
 248         my $related_node;
 249
 250         if($indent_level > $prev_indent_level)
 251         {
 252                 $parent_of_level{$indent_level} = $prev_node;
 253                 $parent_id_of_level{$indent_level} = $prev_node_id;
 254         }
 255
 256         $related_node = $parent_of_level{$indent_level};
 257         $related_node_id = $parent_id_of_level{$indent_level};
 258
 259         if(defined $related_node)
 260         {
 261                 if($OptTree)
 262                 {
 263                         push @{$SubTree{$related_node_id}->{'children'}}, $node_id;
 264                 }
 265                 else
 266                 {
 267                         $Relation{$node}->{$related_node} = 1;
 268                         push @Relation, [$node, $related_node];
 269                 }
 270         }
 271
 272         $prev_indent_level = $indent_level;
 273         $prev_node = $node;
 274         $prev_node_id = $node_id;
 275 }
 276
 277
 278 $\ = "\n";
 279
 280 switch ($OptFormat)
 281 {
 282         case('dot')
 283         {
 284                 print "digraph {";
 285                 print "rankdir=$OptRankdir;";
 286                 print "node [shape=box];";
 287         }
 288         case('clojure')
 289         {
 290                 $\ = undef;
 291                 print "[";
 292         }
 293         case('grapheasy')
 294         {
 295                 printf 'graph { flow: %s; }'.$\, $GraphEasyGraphFlow;
 296         }
 297 }
 298
 299 if($OptTree)
 300 {
 301         for my $id (keys %NodeText)
 302         {
 303                 my $text = $NodeText{$id};
 304                 switch($OptFormat)
 305                 {
 306                         case('dot')       { print node_repr(id=>$id) . ' [label=' . node_repr(text=>$text) . '];'; }
 307                         case('grapheasy') { print node_repr(id=>$id) . ' { label: ' . esc($text, ';}') . ' }'; }
 308                 }
 309         }
 310
 311         output_node_rec(id => 1);
 312 }
 313 else
 314 {
 315         if($OptFormat eq 'clojure')
 316         {
 317                 for my $relation (@Relation)
 318                 {
 319                         my ($node, $related_node) = @$relation;
 320                         ($node, $related_node) = ($related_node, $node) if not $OptAscendent;
 321                         print edge_repr({text=>$node}, {text=>$related_node});
 322                 }
 323         }
 324         else
 325         {
 326                 for my $node (sort keys %Relation)
 327                 {
 328                         for my $related_node (sort keys %{$Relation{$node}})
 329                         {
 330                                 ($node, $related_node) = ($related_node, $node) if not $OptAscendent;
 331                                 print edge_repr({text=>$node}, {text=>$related_node});
 332                         }
 333                 }
 334         }
 335 }
 336
 337 switch ($OptFormat)
 338 {
 339         case('dot')
 340         {
 341                 print "}";
 342         }
 343         case('clojure')
 344         {
 345                 print "]";
 346                 #if($OptTree)
 347                 #{
 348                 #       print ', {';
 349                 #       for my $id (keys %NodeText)
 350                 #       {
 351                 #               print node_repr(id=>$id).' '.node_repr(text=>$NodeText{$id}).' ';
 352                 #       }
 353                 #       print '}';
 354                 #}
 355         }
 356 }