Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

How to print/draw a network graph

by GrandFather (Cardinal)
on Jun 29, 2006 at 05:05 UTC ( #558218=perlquestion: print w/ replies, xml ) Need Help??
GrandFather has asked for the wisdom of the Perl Monks concerning the following question:

I've been batting this problem around on and off for a week without making in useful progress. I have a script that parses trace output from a device and pulls out a series of 'from -> to' connection descriptions that I would like to present as a connection graph.

The current code prints the connection descriptions thus:

'TAvi' (-37) -> 'TDMk' (-32) 'TAvi' (-38) -> 'TMrk' (-34) 'TDMk' (-32) -> xfer (-12) 'TDif' (-7) -> xfer (-11) 'TDif' (-8) -> 'TMCF' (-35) 'TDig' (-27) -> 'TSpN' (-33) 'TLCI' (-36) -> 'TAvi' (-37) 'TMCF' (-35) -> 'TLCI' (-36) 'TMrk' (-34) -> xfer (-28) 'TSpN' (-33) -> 'TAvi' (-38) 'TSpN' (-33) -> 'TDMk' (-32) 'TSpN' (-33) -> 'TMCF' (-35)

By playing around by hand I can rearange that to show the inputs (TDif and TDig) to outputs (xfer) flow as:

'TDif' (-7) -> xfer (-11) 'TDif' (-8) -> 'TMCF' (-35) -> 'TLCI' (-36) -> 'TAvi' (-37) -> 'TDMk' +(-32) -> xfer (-12) ^-----------v-----------------------------------^ 'TDig' (-27) -> 'TSpN' (-33) -> 'TAvi' (-38) -> 'TMrk' (-34) -> xfer ( +-28)

Note that there can be coupling between streams (as shown from 'TSpN' (-33) to two places in the 'TDif' (-8) to xfer (-12) stream), but no loops.

What I've not been able to get my head around is generating some equivelent diagram programaticly. Are there modules around to help with this sort of graphing problem, or is there a way of representing the data that makes the graph "easy" to generate?

At present my internal data format is best represented by @splitLines in the following code fragment (assuming the data shown above is in a __DATA__ section):

use warnings; use strict; my @lines = <DATA>; my @splitLines = map {[/('....')..([-\d]*)\) -> ('?....'?)..([-\d]*)/] +} @lines; print "$_->[0] ($_->[1]) -> $_->[2] ($_->[3])\n" for @splitLines;

This simply reproduces the data above in the same form having parsed it.

In general there are likely to be up to a couple of hundred data lines with up to 17 inputs and 17 outputs.

I appologise for not presenting any half working code. My efforts so far have been less than useful. Hints for solving this problem will be greatly appreciated!


DWIM is Perl's answer to Gödel

Comment on How to print/draw a network graph
Select or Download Code
Re: How to print/draw a network graph
by blokhead (Monsignor) on Jun 29, 2006 at 05:59 UTC
    I don't know whether you need an ASCII-art representation or an image, but for this job, GraphViz springs instantly to mind for me. Its raison d'être is to layout graphs, and there's a lot of research that's gone into it. It does its job very well.

    If you'd rather do something by hand, then as a first step here is how you "rank" the vertices to get a nice attractive flow graph for a DAG:

    • The vertices that have no incoming edges (the "sources"), get rank = 0.
    • All other vertices get rank 1+max{rank(u)}, where the max is over all predecessors u.
    You can compute the ranks by doing a kind of breadth-first search from the source vertices (it's easy to check whether a vertex is a source). Set them as rank=0, then repeatedly set the outgoing neighbors of all the rank-i vertices as the rank-(i+1) vertices. Note that you may end up setting a vertex's rank several times. And if there's a cycle, you never halt.

    Now if you lay out the vertices in columns so that the i-th column contains the rank-i vertices, then when you draw in the edges, they will all go from left to right (it's easy to see this from the definition of rank). It should look very pretty.

    This is essentially what GraphViz (dot engine) does anyway, at least as a first step according to its description on the main GraphViz page. It also has smart ways to arrange the vertices within each column, to minimize the number of edge crossings and other Ugly Things. And it will do something sensible when there are cycles. And it allows you to override and tweak everything of course.

    blokhead

      Thanks for that. GraphViz is probably over kill, at least in the sense of how much work may be required getting up to speed with it, for this task.

      However your analysis of an algorythm is along the lines that I'd been thrashing around and gives me enough confidence to have another go. I was reluctant to do all the backtracking and fixups that seemed to be required and spent a lot of time trying to find a more direct approach. I'll post the code when I get it sorted out.


      DWIM is Perl's answer to Gödel

      Following a little egging on and a simple example from blokhead (my thanks for that!) the following code generates the graph I was after. Note that this code uses dot from GraphViz.

      use warnings; use strict; my @lines = <DATA>; my @splitLines = map {[/'(....)'..([-\d]*)\) -> '?(....)'?..([-\d]*)/] +} @lines; my $graphStr = <<GRAPH; digraph G { graph [rankdir=LR]; node [shape=rect]; GRAPH $graphStr .= " $_->[0]$_->[1] -> $_->[2]$_->[3]\n" for @splitLines; $graphStr =~ s/-(?!>)/_/g; $graphStr .= "}\n"; open outFile, '>', 'graph.dot'; print outFile $graphStr; close outFile; `dot -Tpng -ograph.png graph.dot`; __DATA__ 'TAvi' (-37) -> 'TDMk' (-32) 'TAvi' (-38) -> 'TMrk' (-34) 'TDMk' (-32) -> xfer (-12) 'TDif' (-7) -> xfer (-11) 'TDif' (-8) -> 'TMCF' (-35) 'TDig' (-27) -> 'TSpN' (-33) 'TLCI' (-36) -> 'TAvi' (-37) 'TMCF' (-35) -> 'TLCI' (-36) 'TMrk' (-34) -> xfer (-28) 'TSpN' (-33) -> 'TAvi' (-38) 'TSpN' (-33) -> 'TDMk' (-32) 'TSpN' (-33) -> 'TMCF' (-35)

      DWIM is Perl's answer to Gödel
Re: How to print/draw a network graph
by terce (Friar) on Jun 29, 2006 at 06:49 UTC

    I second blokhead's recommendation of Graphviz. In case you haven't found them already, CPAN hosts Graphviz and Tk::Graphviz, which (as far as my limited understanding goes) provide Perl wrappers around the Graphviz executables.

    Graphviz enables you to create charts as Perl data-structures and then render them using the (extensive) Graphviz options.

    Tk::Graphviz takes output from the Graphviz binaries and renders them as a Tk::Canvas object; it doesn't support all the formatting options of using the binaries, but does enable you to access the chart interactively using a callback when a node is clicked, which I found handy to access additional node information stored in a database. It accepts a filename, a scalar string or a Tk::Graphviz object as input.

Re: How to print/draw a network graph
by GrandFather (Cardinal) on Jun 29, 2006 at 10:32 UTC

    Here's a partial solution. It doesn't "hook up" cross connections between streams yet, but notes the unresolved connections following the resolved connections.

    use warnings; use strict; my @lines = <DATA>; my @splitLines = map {[/('....'..[-\d]*.) -> ('?....'?..[-\d]*.)/]} @l +ines; my %ends; for (@splitLines) { next if $_->[0] !~/T(?:Dif|Dig)/; $ends{$_->[1]} = $_->[0]; } for (keys %ends) { my $match = "$ends{$_}$_"; @splitLines = grep {"$_->[0]$_->[1]" ne $match} @splitLines; } while (@splitLines) { my $match; for (@splitLines) { next if ! exists $ends{$_->[0]}; $ends{$_->[1]} = "$ends{$_->[0]} -> $_->[0]"; $match = $_; delete $ends{$_->[0]}; @splitLines = grep {$_ ne $match} @splitLines; last; } last if ! $match; } print "$ends{$_} -> $_\n" for sort keys %ends; print "*** $_->[0] -> $_->[1]\n" for @splitLines; __DATA__ 'TAvi' (-37) -> 'TDMk' (-32) 'TAvi' (-38) -> 'TMrk' (-34) 'TDMk' (-32) -> xfer (-12) 'TDif' (-7) -> xfer (-11) 'TDif' (-8) -> 'TMCF' (-35) 'TDig' (-27) -> 'TSpN' (-33) 'TLCI' (-36) -> 'TAvi' (-37) 'TMCF' (-35) -> 'TLCI' (-36) 'TMrk' (-34) -> xfer (-28) 'TSpN' (-33) -> 'TAvi' (-38) 'TSpN' (-33) -> 'TDMk' (-32) 'TSpN' (-33) -> 'TMCF' (-35)

    Prints:

    'TDif' (-7) -> xfer (-11) 'TDif' (-8) -> 'TMCF' (-35) -> 'TLCI' (-36) -> 'TAvi' (-37) -> 'TDMk' +(-32) -> xfer (-12) 'TDig' (-27) -> 'TSpN' (-33) -> 'TAvi' (-38) -> 'TMrk' (-34) -> xfer ( +-28) *** 'TSpN' (-33) -> 'TDMk' (-32) *** 'TSpN' (-33) -> 'TMCF' (-35)

    DWIM is Perl's answer to Gödel
      Hi friend, I am doing my Master's project its all about scheduling the processors using the task and network graph.The project is the extension of the previous project where they have a GUI interface to draw the task and network graph and see the scheduling processors assigned as output. But the problem is the Scheduling processors are overlapping with one another. please help me out. I am thinking to work out manually drawing the network and task graph calculating it. But i do not know how to calculate it. It would be helpful to me if u can help me. Thanks

        I suggest you put together a more coherent question and post it as a new question rather than as a reply. Replies to old threads such as this one get much less notice than new questions.

        A new question would need to provide greater detail concerning the data you have for the task and network graph and how you are using that information currently to schedule processors.


        True laziness is hard work
Re: How to print/draw a network graph
by planetscape (Canon) on Jun 30, 2006 at 16:27 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://558218]
Approved by Samy_rio
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (7)
As of 2014-08-20 09:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (108 votes), past polls