Re^3: How to create a Tree::DAG_Node tree with sorted hash elements

benny_vroom:

Since you can ignore case 5, and it sounds like you're only interested in the case where some rules are possible subsets of others, then I think you can do it relatively easily. I think you could get away with sorting the list, like this:

$ cat 910595.pl
#!/usr/bin/perl
use strict;
use warnings;
use Net::IP;

my @IPranges = map { new Net::IP($_) } <DATA>;

@IPranges = sort {
              # We want largest range first
              ($b->size() <=> $a->size())
              # use IP as next key
              || ($a->ip() cmp $b->ip())
            } @IPranges;

print join("\n", @IPranges), "\n";
__DATA__
1.2.3.0/24
1.2.0.0/16
192.168.0.0/16
192.168.4.0/24
192.168.4.192/26
127.0.0.1/32
10.0.0.0/8

$ ./910595.pl
10/8
1.2/16
192.168/16
1.2.3/24
192.168.4/24
192.168.4.192/26
127.0.0.1/32
[download]

Then you can probably use the rest of your code as-is to find the related rules.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Comment on Re^3: How to create a Tree::DAG_Node tree with sorted hash elements Download Code

Replies are listed 'Best First'.
Re^4: How to create a Tree::DAG_Node tree with sorted hash elements by benny_vroom (Initiate) on Jun 21, 2011 at 14:41 UTC
Roboticus, Note that the output is still not in the preferred order. The preferred order is: `10/8 1.2/16 1.2.3/24 192.168/16 192.168.4/24 192.168.4.192/26 127.0.0.1/32` [download] And this is happening because you are sorting based on network size first and if equal, going on to compare the IP address (which would simply say which one of either has a smaller decimal equivalent). 10/8 may have a big network size, but it is not a supernet for 172.16/16. Also, my comparison is not that of single network address. I need to compare two hashes whose elements are network addresses. Anyways, I learnt that I can use custom expressions in place of cmp or <=> to perform sort operation. my $acl = {}; $acl->{source} = []; # array of Network address e.g, [10/8 +,172.16/16] $acl->{dest} = []; # same as above $acl->{original}= 'unknown'; # A string for original ACL e.g, permit + ip any 10/8 # After I create a hash I will store the hash reference in an array push @acl_grp, \%acl; # After populating the array of hash refs I want to sort them # I would do something similar to this foreach $acl ( sort compare @acl_grp ){ print $acl->{original},"\n"; } # compare function is coded as # return -1 if $b is a supernet of $a # return 1 if $a is a supernet of $b # return 0 for all other cases, mimicking the behaviour of <=> sub compare($$){some code}; [download] Assuming that above code works, I expect to get a list of ACL's sorted in order. Now my problem is, how can I indent them depending on whether above node is a super ACL or an unrelated ACL.	[reply] [d/l] [select]
Re^5: How to create a Tree::DAG_Node tree with sorted hash elements by roboticus (Chancellor) on Jun 21, 2011 at 16:12 UTC
benny_vroom: The sorting was not intended to show the hierarchy of the nodes, but to give you an order to insert nodes with your original code that would give you the correct results. Given your original code, it would always work if (and only if) you inserted the larger ranges before the smaller ones. ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply]
Re^6: How to create a Tree::DAG_Node tree with sorted hash elements by benny_vroom (Initiate) on Jun 21, 2011 at 16:50 UTC
OK, Now I get what you are saying. I should always insert the ACL's with larger ranges in to the tree first. I also take that you suggest to go ahead with creating a Tree to get this done. Let me try this and update back how it works! Thanks for your useful comments so far!	[reply]