CPAN::graph seems to be the thing you want to look at. It will give you some basic functionality for storing graphs and lots of functions to work on them.

Now lets say I wanted a program to randomly create graphs. So I would choose 4 levels or 5 levels etc. The starting level would have just 1 node. The subsequent levels can have 2-5 nodes(random, using rand() function.

I think you need to clarify the range of expectations for your randomly generated graphs.

Your example starts with a single node, ends with a single node, and has all intervening nodes cross connected. Is that typical of what you want to generate? How about a direct path from node A to (say) Cn? Or Bn to D?

Perhaps you could hand generate 3 or 4 more examples that fit your expectations?

Okay, imagine my nodes as routes. So if you want to go from level 1 to level 3, you have to pass through 1 level 2 node. the ending node can be single, or there can be multiple nodes.


Imagine, all nodes are bus stops, and the paths are buses. A bus as to stop at all nodes it passes through. So when going from level 1 to level 5, it has to pass through 1 node of each intermediate level.

All I want to do is
1. Create a random graph with 1 starting node, and 4-5 levels, with number of points at each level random. Last level can have one or many nodes, no issues here.
2. Print all possible Paths from A to the end nodes


So its more like a tree where you cannot go from the first level to an intermediate level by skipping the levels between the two.

A quick solution to your issue (with a complexity of O((n*m)^2) (n being the number of levels and m the maximum nodes per level):

• as a structure for your nodes, simply have a hash with the name of the node-level (A, B, ...) and the numbers of nodes on that level
• As an algorithm, try the following
• traverse through each level
• generate all possible node-names of that level
• take all paths you already found and add the new node-names to each of them

The code below solves your issue. It is however just a short hack and in no way optimized. But it hopefully gives you an idea.

HTH, Rata

use strict;
use warnings;

my %nodes = (  A => 2,  B => 4,  C => 5, D => 1);
            
my @path = ("");
my @newpath;
    
foreach my $k (sort (keys(%nodes)))                    # each level
{
    my @nodename;
    for (my $i = 1; $i <= $nodes{$k}; $i++)
    {
        push (@nodename, "$k$i");                           # generate
+ node-names for each level
    }
    
    foreach my $old (@path)                                # take all 
+old paths
    {
        foreach my $new (@nodename)                            # appen
+d new node to each
        {
            push (@newpath, "$old-$new");
        }
    }
    @path = @newpath;                                          # save 
+old paths
    @newpath  = ();                                        # clear lis
+t of new paths
}
print join("\n", @path);    # print all paths (each in a new line)
exit 0;
[download]

Imagine, all nodes are bus stops, and the paths are buses. A bus has to stop at all nodes it passes through. So when going from level 1 to level 5, it has to pass through 1 node of each intermediate level.

?? But buses don't work like that. Buses don't choose between stopping at B1 or B2.

Well, maybe the 45 does. I always try to avoid the 45.

use JAPH;
print JAPH::asString();

This is of course assuming that all you want to do is solve the problem. If you're needing to implement the graph algorithms for some other reason, you'll have a fair amount more work to do - but hashes of hashes (or arrays of arrays, for that matter) would work fine.

All I need to do is
1. Create a graph randomly
2. Identify all possible paths from start node to all the end nodes
Graph creation with hashes seems to be the easier bit. Its creating all the paths which is an issue.

I guess it's just me, but last time I needed to do something like this (verify that there were no cycles in macro definitions), Graph let concentrate on what I wanted to do and let me forget about the nit-picky graph management.

Then again, I have written an AVL tree implementation in FORTRAN, so I shouldn't talk too much about doing things the hard way.

I'd implement something like this:

Create root-node hash
Current level is zero
Establish limits: max & min nodes per level, number of levels
root{A0} = add_levels($current_level, $level_limit, $min_nodes, $max_n
+odes);

sub add_levels {
    return if current level is > the limit, bump it if not
    calculate a random number between high and low limit
    new_level = {};
    for $n (0..$local_limit) {
      generate $name from level and $n
      new_level{$name} = add_levels($current_level, $limit, $min, $max
+)
    }
    return $new_level;
}
[download]

The printing code will be similar, but you'll instead pass a string down the recursive call tree, adding level names until you run out of levels, then printing it. The recursion plus the loop will automatically follow all paths for you.

I have written a program to do this but I'm not posting it; you'll learn a lot more if you follow this outline and write it yourself; as you don't want to handwave the details via Graph, I assume there's a reason for writing it yourself -- and me writing it for you won't teach you anywhere near as much.

I recommend running under the debugger, as you'll be able to x the growing data structure as you go along and see if it's working.

Perhaps a breadth-first search of the graph? Is this homework? It sounds a lot like problems from my undergrad studies.

Nope, I am actually trying to create some graphs as test scenarios for software, to see if it breaks.