Perl: the Markov chain saw PerlMonks

### Graph in a terminal (ASCII - art)

by baxy77bax (Deacon)
 on Feb 12, 2018 at 16:02 UTC Need Help??
baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

Loosing my mind over this. It looked like a simple task but I spent a day on it and still not getting my result. What I want to do is to visualize a graph in a terminal. I have the following sequence of events:

```1 > 2 > 5 > 6 > 7 > 8 > 9 > 11
1 > 2 > 5 > 6 > 7 > 8 > 10 > 11
1 > 4 > 5 > 6 > 7 > 8 > 9 > 11
1 > 4 > 5 > 6 > 7 > 8 > 10 > 11
1 > 3 > 5 > 6 > 7 > 8 > 9 > 11
1 > 3 > 5 > 6 > 7 > 8 > 10 > 11
1 > 7 > 8 > 10 > 11
Ideally what i am looking for would be something like this:
```       1
|
+---+---+---+
|   |   |   |
2   4   3   |
|   |   |   |
+---+---+   |
|       |
5       |
|       |
6       |
|       |
+---+---+
|
7
|
8
|
+---+---+
|       |
9       10
+---+---+
|
11

Any clue ?? any help? I know you are going to ask me what I did so-far. The truth is, nothing, nothing works. I tried to create a tree out of it and recurse, than make a matrix 11x11 and then ad numbers in that spot but then got confused what goes where when to add/remove a row.. All in all I am going insane over this problem .... any idea on how to solve it ? (written explanation is more than welcomed i just need the logic (the MOST IMPORTANT THING) on how to do it )

Replies are listed 'Best First'.
Re: Graph in a terminal (ASCII - art)
by VinsWorldcom (Parson) on Feb 12, 2018 at 19:12 UTC

```use Graph::Easy;
my \$graph = Graph::Easy->new();
# I think I got all the edges added below?
print \$graph->as_ascii;

Output:

```  +-----------------------------+
|                             |
|                             |
|         +-------------------+-------------------+
|         |                   v                   v
+---+     +---+     +---+     +---+     +---+     +---+     +---+
++----+     +----+
| 4 | <-- |   | --> | 2 | --> | 5 | --> | 6 | --> | 7 | --> | 8 | -->
+| 10 | --> | 11 |
+---+     |   |     +---+     +---+     +---+     +---+     +---+
++----+     +----+
|   |       ^         ^                             |
+             ^
| 1 | ------+         |                             |
+             |
|   |                 |                             v
+             |
|   |                 |                           +---+
+             |
|   |                 |                           | 9 | ----
+-------------+
+---+                 |                           +---+
|                   |
|                   |
v                   |
+---+                 |
| 3 | ----------------+
+---+

UPDATE: Note Graph::Easy only *displays* graphs, it doesn't analyze them. To do graph analysis, you'll need Graph. Of course they use different object constructions, but fear not, Graph::Convert converts wonderfully between the two, so you can create, analyze and display graphs with these three modules (Graph, Graph::Easy, Graph::Convert) and they all depend on core modules - so no dependency spiral.

Thanks for the pointer the Graph::Easy, I'd not seen that before so just installed it. I'd already created a hash of edges from an AoA of the events but had no idea how to turn them into a graph as I don't have a computer science background. Once I had the module I initialised a graph and added the edges from the hash and printed the result. My output differs from yours in that you have two 1 -> 2 edges where I only have one. Reading the module documentation it may be that you did \$graph->add_edge(1,2) twice, although it only appears once in the code you posted.

```use strict;
use warnings;

use 5.022;

use Graph::Easy;
say qq{Using Graph::Easy version \$Graph::Easy::VERSION};

my @events = (
[ 1, 2, 5, 6, 7, 8, 9, 11 ],
[ 1, 2, 5, 6, 7, 8, 10, 11 ],
[ 1, 4, 5, 6, 7, 8, 9, 11 ],
[ 1, 4, 5, 6, 7, 8, 10, 11 ],
[ 1, 3, 5, 6, 7, 8, 9, 11 ],
[ 1, 3, 5, 6, 7, 8, 10, 11 ],
[ 1, 7, 8, 10, 11 ],
);

my %edges;
foreach my \$event ( @events )
{
foreach my \$idx ( 1 .. \$#{ \$event } )
{
\$edges{ join q{ -> }, \$event->[ \$idx - 1 ], \$event->[ \$idx ] }
+ ++;
}
}

say for
map { unpack q{x8a*} }
sort
map { pack q{NNa*}, split( m{ -> } ), \$_ }
keys %edges;

my \$graph = Graph::Easy->new();
\$graph->add_edge( split m{ -> } ) for keys %edges;

print \$graph->as_ascii();

The output.

```Using Graph::Easy version 0.76
1 -> 2
1 -> 3
1 -> 4
1 -> 7
2 -> 5
3 -> 5
4 -> 5
5 -> 6
6 -> 7
7 -> 8
8 -> 9
8 -> 10
9 -> 11
10 -> 11

+-----------------------------+
|                             |
|                             |
|         +-------------------+-------------------+
|         |                   v                   v
+---+     +---+     +---+     +---+     +---+     +---+     +---+
++----+     +----+
| 4 | <-- | 1 | --> | 2 | --> | 5 | --> | 6 | --> | 7 | --> | 8 | -->
+| 10 | --> | 11 |
+---+     +---+     +---+     +---+     +---+     +---+     +---+
++----+     +----+
|                   ^                             |
+             ^
|                   |                             |
+             |
v                   |                             v
+             |
+---+                 |                           +---+
+             |
| 3 | ----------------+                           | 9 | ----
+-------------+
+---+                                             +---+

If I change the graphing code to this I get output that matches yours.

```...
my \$graph = Graph::Easy->new();
\$graph->add_edge( split m{ -> } ) for keys %edges;

print \$graph->as_ascii();

I hope this is of interest.

Cheers,

JohnGG

Beauty of Graph::Easy is that it plays well with Graphviz.

Re: Graph in a terminal (ASCII - art)
by Eily (Prior) on Feb 12, 2018 at 18:02 UTC

The path 1 > 7 > 8 > 9 > 11 doesn't exist in your input but does in the graph, is it on purpose, or an issue?

If it's on purpose, you can drop most of the input and only keep unique pairs, for example there's no need for 1 > 2 to appear twice and 8 > 9 thrice. In that case, by just keeping those unique pairs your graph is already defined. I don't know about ASCII graphs, but your input is really easy to turn into dot, and then into a graph (maybe there is a tool that turns dot data into ASCII graphs...)

If having 1 > 7 > 8 > 9 > 11 in your output graph is a mistake, what you have is a DFA which you want to minimize. There might be a module that does that on graphs in perl.

This is kind of OT but your input can be turned into a regular expression (using A and B for 10 and 11, to have only one char per transition): 1256789B|125678AB|1456789B|145678AB|1356789B|135678AB|178AB.
This can be optimized by a module like Regexp::Optimizer: (?:(?:1(?:[234]5678[9A]|78A)B)) (I cheated on that one, I manually turned the perl regexp into a javascript one)
And then plotted by one of the online tools that turn regexp into graphs: like this (notice the separate branch for 1 > 7 > 8 > 10 > 11 / 178AB).

This is just taking advantage of the fact regular expressions (in the first sense of the name, not the extended stuff allowed by perl) can be turned to a DFA and back. I don't know the implementation of Regexp::Optimizer but it might just do a DFA minization in some form or other.

Edit: oh and that's the result you get by adding 1789B as a possible path in the regex, which is the graph you asked for.

Edit2: How to convert dot graph to ASCII. So if you're in the first case (1 > 7 > 8 > 9 > 11 allowed), your problem becomes really easy to solve.

Re: Graph in a terminal (ASCII - art)
by holli (Monsignor) on Feb 12, 2018 at 17:22 UTC
You don't have a problem, you have two.

One is to display treelike data nicely on a screen, the other to transform your input into such data. You should solve these independently.
See this post on Stackoverflow regarding tree drawing and Tk::TreeGraph for ideas on how to nicely design an interface for your graph drawer.

holli

You can lead your users to water, but alas, you cannot drown them.
Re: Graph in a terminal (ASCII - art)
by Anonymous Monk on Feb 12, 2018 at 17:26 UTC

If there are loops in the topology, use Spanning Tree Protocol to break them and find the root node. But it seems your (unidirectional) graph is already loop-free.

Find the root node with no incoming links. Find the maximum depth for each node. Put the nodes on proper lines (3*depth or so). Assign columns opportunistically, depth first. You cannot avoid crossing links in general. For example, the diamond dependency 1->2; 1->3; 2->4; 2->5; 3->4; 3->5, is impossible to plot.

Re: Graph in a terminal (ASCII - art)
by Anonymous Monk on Feb 13, 2018 at 13:41 UTC

There are plenty of programmer tools for Call Graph generation. Usually, the text they produce is line-by-line indented trees, or maybe descendants grouped under common parent. Ascii-art is uncommon, probably because other formats are more compact or afford better insight. Off-hand, I can't remember anything that would print boxy art, but it might be worth digging in this direction.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1209007]
Approved by Eily
Front-paged by Corion
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2018-05-24 19:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (180 votes). Check out past polls.

Notices?