@ roboticus:

You are right, I should probably explain a bit about the background of my attempt. The Cisco firewalls we maintain at work have become bloated with several duplicate & overlapping rules due to mismanagement. Now a single firewall may have up to 900 ACL's. I want to sort & arrange them to identify rules that can be cleaned up. Most important need is to see which rules are sitting on top of smaller rules, some of them cover such wide access that they supersede quite a few other rules. So the visual representation of this supersets and subsets is very important.

Now, an ACL will contain an array of source & destination networks (may be host address X.X.X.X/32 or network address Y.Y.Y.Y/Z) and another array of service ports (tcp/udp ports). Now the examples I have used are just over-simplified ACL, with one source & destination address each, to be used for unit testing the rest of the code. I have managed to write the code to convert config files to array of hash of arrays(each ACL is a hash) and also the code to compare two ACL's. Now all that is left to do is put them in the right order and display the subsets and supersets.

Now back to your answer, you have summarized all the possibilities rather elegantly. I will not bother about case 5, I will treat such rules as unequal and yet insert them as peers to other rules (i.e, sue would be sister to bob & joe and I am not interested whether it can be split and inserted under the rest). I can think of no practical purpose to explore case 5 in my problem.

I did consider the root node conundrum and that is why I started with "permit ip any any" as the root node. However, I didn't imagine that such a rule would arrive as part of the rule hash. Perhaps I should write a special case for that.

Now that, all the obstructions are taken care of, what is the problem?

I am not really sure how to go about sorting an array of hashes. I have a procedure that compares two hashes and returns 1 or 0. 

# 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 0;
}

[download]

I feel I have to do something similar to overloading the "cmp" operator, but unsure of how to proceed. Any pointers would be of great help!

Also, I realize that if I get the sorting done, I have acheived most of my work, except that of grouping the rules into sets and subsets. At this point, I wonder if it is necessary to build a tree structure. Each comparison is an expensive task. For e.g, comparing hash1{sourcem,destn, portso} against hash2{sourcep,destq, portr} will require (mxp + nXq + oxr) calls to Net::IP->overlaps() procedure. By the time we finish sorting and ready to build tree, each ACL has already been compared every other ACL atleast once and all necessary information to group into sets & subsets have already been computed at least once (perhaps not remembered to be used later). So is there a better way to achieve my goal rather than build a N-ary tree? Should I code my own sort code with facility to group entries in to sets & subsets?Perhaps I am just being overly paranoid about repeating the comparison, deep inside I just want the task to be done. What is your opinion?

Apologies if I am confusing or misleading, I often tend to talk in a confusing manner.

In reply to Re^2: How to create a Tree::DAG_Node tree with sorted hash elements by benny_vroom
in thread 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.