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.

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.

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)
[download]

---

DWIM is Perl's answer to Gödel

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

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.

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)
[download]

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)
[download]

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

Mastering Algorithms in Perl has an entire chapter (8) devoted to Graphs; you may be able to find something useful in the sample code.

HTH,