Hi there, I want to sort a list of ACL and group them in to sets and subsets. I decided to go with creating a Tree and populate the rules as leaves of the tree. If a rule is superseded by another rule, it will be added as a daughter node to the latter. If a rule doesn't fit in to any other rule, it will become daughter of the root. By definition, the ACL "permit ip any any" will become the root. I have a rudimentary code (with 3 statically assigned leaf nodes). It walks down the root node and remembers every location where a leaf can fit. Once it reaches a location where the leaf doesn't fit, it inserts the leaf in the last remembered location. Below is the code: 
use Tree::DAG_Node;
use Data::Dumper;
use Net::IP;
# compares two Tree::DAG Nodes and returns positive if right (second) 
+argument is bigger
sub compare_nodes {
    my ($compare_node, $leaf_node) = @_;
    my $source_OK = compare_subnet($compare_node->{'attributes'}{'sour
+ce'},$leaf_node->{'attributes'}{'source'});
    my $destination_OK = compare_subnet($compare_node->{'attributes'}{
+'destination'},$leaf_node->{'attributes'}{'destination'});
    print "$compare_node->{'attributes'}{'original'} is a daughter of 
+$leaf_node->{'attributes'}{'original'}\n\n" if ($source_OK && $destin
+ation_OK);
    return 1 if ($source_OK && $destination_OK);
    return undef;
}

# create nodes for tree construction later on
my $root = Tree::DAG_Node->new;
$root->attributes ({
        original => 'permit ip any any',
        source => ['0.0.0.0/0'], 
        destination => ['0.0.0.0/0']
    });

my $leaf_1 = Tree::DAG_Node->new;
$leaf_1->attributes ({
        original => 'permit ip 10.0.0.0/8 172.16.0.0/16',
        source => ['10.0.0.0/8'], 
        destination => ['172.16.0.0/16']
    });

my $leaf_2 = Tree::DAG_Node->new;
$leaf_2->attributes ({
        original => 'permit ip 10.0.0.0/16 172.16.0.0/24',
        source => ['10.0.0.0/16'], 
        destination => ['172.16.0.0/24']
    });

my $leaf_3 = Tree::DAG_Node->new;
$leaf_3->attributes ({
        original => 'permit ip 192.168.0.0/16 12.16.0.0/24',
        source => ['192.168.0.0/16'], 
        destination => ['12.16.0.0/24']
    });

my @node_list;
push @node_list, $leaf_1, $leaf_2, $leaf_3 ;

# Subnet comparison
# returns true if $x is a subset of $y
sub compare_subnet {
    my ($x, $y) = @_;
    a_in_b ($_, @$y) or return '' foreach @$x;        #Check if each e
+lement of 
    return 1;
};


# check one ip address against array of ip addresses
# first argument is single address, second one is array
sub a_in_b  {
  my $node1 = shift(@_);
  my @ip_list = @_;
  for my $node2 (@ip_list) {
    my $ip1 = new Net::IP ($node1) || die (Net::IP::Error());
    my $ip2 = new Net::IP ($node2) || die (Net::IP::Error());
    if (($ip1->overlaps($ip2) == $IP_A_IN_B_OVERLAP) || ($ip1->overlap
+s($ip2) ==  $IP_IDENTICAL))  {
      return 1;
    }
    
  }
  return '';
}

#build the tree
foreach my $node (@node_list){
    my $location;
    $root->walk_down({
            callback => sub {
                my $this_node = shift;
                if (compare_nodes($node,$this_node)){
                    $location = $this_node->address;
                    1;
                }
                else{
                    0;
                }
            }

        });
    $root->address($location)->add_daughter($node) if defined $root->a
+ddress($location);
}

# print the tree
$root->walk_down({
    callback => sub {
        my $node = shift;
            print "  " x $_[0]->{_depth};
            print $node->{'attributes'}{'original'}, "\n";
        },
    _depth => 0,
});

$root->delete_tree();

[download]
I basically want an output such as this: 
permit ip any any
  permit ip 10.0.0.0/8 172.16.0.0/16
    permit ip 10.0.0.0/16 172.16.0.0/24
  permit ip 192.168.0.0/16 12.16.0.0/24

[download]

Obviously this approach is wrong for several reasons. For e.g, it expects the array entries to be sorted. If a smaller ACL enters the tree before a bigger ACL, when the bigger one's turn arrives, it is not inserted between the parent and the leaf, instead it is entered as a sister node.

For e.g, if I have elements such as:

root > A > B > C

[download]
And they are stored in the array in the below order: 
[A,C,B]

[download]
I would get the result as: 
root
 A
  C
  B

[download]
instead of: 
root
 A
  B
   C

[download]

I have run out of ideas to see how to code this. I understand that the input needs to be sorted in some way, but this case is different from sorting numbers or strings in that two elements can be unrelated (neither bigger, smaller nor equal) to each other. And I am not a computer scientist and not so familiar with the theories behind sorting.

How does this problem look to an experienced programmer? Is there something I should do differently?

In reply to How to create a Tree::DAG_Node tree with sorted hash elements by benny_vroom

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.