# Commits

committed 380e5bb

Removed graphs_equal.

• Participants

# File t2/graphs_equal/Docs/Description.txt

`-Description of the Algorithm for Verifiying The Isomorphism of Two Graphs`
`--------------------------------------------------------------------------`
`-`
`-                                                           Shlomi Fish`
`-`
`-Revision 2`
`-`
`-1. Preface`
`-----------`
`-`
`-Two graphs are considered isomorphic if they have the same topology. That is,`
`-there is a one-to-one mapping between the indexes of their nodes so that, when`
`-the indexes of one graph are converted to the indexes of the other, they will`
`-have the same adjency matrix.`
`-`
`-This proposed algorithm attempts to solve the question whether two graphs with`
`-the same number of nodes are isomorphic or not, in a time that will usually be`
`-better than that of trying all V! possibilities.`
`-`
`-2. Notation and Preliminary Notes`
`----------------------------------`
`-`
`-Since two graphs are involved they will be marked with G[1](V[1],E[1]) and`
`-G[2](V[2],E[2]). V[i] is the group of nodes (or vertices) of graph i and `
`-E[i] is the group of links (or edges) of the graph i.`
`-`
`-The algorithm can handle variable link multiplicity, i.e. that two nodes can be `
`-connected by more than one link. The number of links leading from each node to`
`-the other will be referred as link multiplicity or link width.`
`-`
`-Each node is uniquely marked with an index in the range [ 0 .. (|V|-1)]. The`
`-choice of indexes for each graph is not important but will be preserved`
`-throughout the algorithm.`
`-`
`-Throughout the algorithm nodes will be assigned IDs, and those IDs will be `
`-manipulated. While those IDs are integers in the range [ 0 .. (|V|-1) ], they`
`-should not be confused with the node indexes. Two IDs can be shared by the`
`-same node.`
`-`
`-The algorithm will focus on non-directed graph but it can also be adapted to`
`-directed graphs.`
`-`
`-3. Decsription of the Algorithm`
`--------------------------------`
`-`
`-3.1 The p->n Transformation`
`----------------------------`
`-`
`-The p->n transforms between two vectors of "previous" IDs p[1,2], to two`
`-vectors of "next" IDs n[1,2], based one two graphes G. It uses an `
`-associative array (dictionary) that maps nodes templates (to be `
`-explained later) to IDs. The associative array to be marked H is `
`-initialize to {} at the beginning of the`
`-transformation and is nor returned by it.`
`-`
`-Given the Graph G(V,E) and p[0 .. |V|] a vector of IDs, the new template for`
`-each node i is allocated using the following fields:`
`-1. p[g][i].`
`-2. The number of self-links i has.`
`-3.    `
`-4.`
`-5.`
`-.`
`-.`
`-3+[maximal link multiplicity in G]-1`
`-`
`-In each multiplicity the prev IDs of the nodes at the end of the links of that`
`-multiplicity. The list should be sorted numerically.`
`-`
`-Next, the algorithm matches a new ID for every template it found and puts it`
`-in n[g][i]. If it allocated a new ID for the second graph it checked it `
`-returns false as its error code. That is because if the graphs have the `
`-same topology and the same prev IDs (in different order), than they must `
`-have the same next IDs too (in a corresponding different order).`
`-`
`-Then it checks whether n[1] and n[2] contain the same number of instances out`
`-of each ID. If they don't, it returns FALSE.`
`-`
`-Else, it returns TRUE and n[1,2];`
`-`
`-3.2 The (p->n)^V transformation`
`--------------------------------`
`-`
`-(p->n)^V runs (p->n) on the two graphs |V| times, while passing the n of the`
`-previous iteration as the p of the next iteration. If one of the (p->n)`
`-iterations fail, it returns an error code. If all the iterations return`
`-positive error codes, it returns the final n.`
`-`
`-The (p->n)^V transform can terminate in the middle if for i=1,2 p[i]==n[i], in `
`-which case it returns true. The intuition for this is that for each i the `
`-n return value of (p->n) transform is based only on the graph topology and on`
`-p, so if it (p->n)[p[i]] = p[i] then it will give the same results in the left`
`-iterations.`
`-`
`-The reason for the limit of |V| is that it takes at most |V| iterations to`
`-propagate all the information from one node in the graph to every other node.`
`-(Re: BFS and DFS Trees from each node)`
`-`
`-3.4 The Recurser Function`
`--------------------------`
`-`
`-The recurser function is a recursive function that accepts two graphs, `
`-and an initial two arrays of IDs (p). It returns an error code and (on `
`-a true value of the error code) a mapping of the indexes from the nodes `
`-of one graph to the other.`
`-`
`-The recurser performs the following steps:`
`-`
`-1. It calls the (p->n)^V transform on p to get n. `
`-`
`-2. If the transformation returns a false error code it also terminates `
`-    with a false error code.`
`-`
`-3. The function seeks an ID in n[1] that appears more than once. If it didn't`
`-find one it returns a mapping based on the IDs of the n[1] and n[2] and a true`
`-error code.`
`-`
`-4. Assuming it did find such an ID, it sets the first occurence of that ID `
`-in n[1] to the first ID in [ 0 .. |V|-1 ] which isn't occupied. Then it `
`-loops on every occurence of the id in n[2] and for each one temporarily `
`-sets it the same ID, and calls itself with a copy of n as the parameter p.`
`-`
`-5. If in one of the loop's iterations the child instance of the function `
`-returned a true error code, it returns true with the mapping as specified by`
`-the child.`
`-`
`-6. If the loop terminates, it returns a false error code.`
`-`
`-3.5 The main function`
`----------------------`
`-`
`-The main function is very simple. It initializes two vectors of IDs to all`
`-zeros, and then returns whatever graph_iso_recurser(G1,G2,init_ids) returns.`
`-`
`-4. Notes and Optimizations`
`---------------------------`
`-`
`-1. All the sorts in the algorithm sort numbers  limited to the range of `
`-[ 0 .. (|V|-1) ]. Thus, they can be done in a linear time using the Counting`
`-Sort algorithm.`
`-`
`-2. In step 4 of the Recurser function the function may choose to set the ID`
`-with the least number of occurences in the arrays, that is still larger than `
`-one. I'm not sure whether it is a good strategy.`
`-`
`-3. For efficiency's sake, the (p->n) transformation can be splitted into two`
`-variants: one which will be excuted for the first time in the algorithm and`
`-the other one in all the other times. The first will consider only the number`
`-of inner links, and the number of connected nodes in each link width. The`
`-second will be the same as the definition except for not considering the`
`-number of self-links.`
`-`
`-5. Complexity Analysis`
`-----------------------`
`-`
`-Assuming the graphs are given as adjency matrices and that we use a`
`-linear-time sort, we can see that each (p->n) transform is O(V^2), and that`
`-the (p->n)^V transform is O(V^3). Now, for analysing the recursion.`
`-`
`-The depth of the recursion is at most |V|. The width of it, starts with at`
`-most |V| at the start and decreases by at least one in each depth level. Thus,`
`-a naive deduction will conclude that it has a worst-case running time of `
`-O(V!). This makes the total complexity of the algorithm O(V!*V^3) or`
`-O((V+3)!).`
`-`
`-That does not looks good considering that the brute force algorithm has a`
`-complexity of O(V!*V^2). However, I believe this algorithm will prove to be `
`-more efficient in most real-life situations, and possibly many symmetric and`
`-pseudo-symmetric graphs given to it as input. For most non-isomorphic graphs,`
`-the first (p->n)^V transform will show that they are indeed so, and most`
`-isomorphic graphs do not contain too many levels of symmetry and`
`-pseudo-symettery.`
`-`
`-6. Off-the-shelf Proof`
`-----------------------`
`-`
`-Well, it is trivial to prove that if the algorithm finds the graphs to be`
`-isomorphic, they are indeed isomorphic. The algorithm returns a one-to-one`
`-mapping between the nodes of one graph to the other, that according to the `
`-qualities of the p->n transform, will make one graph have the same topology `
`-of the other, with the same ordering of the nodes.`
`-`
`-According to the rules of logic, it also proves that if graphs are not `
`-isomorphic, the algorithm will say they are indeed not. Now, we have to show`
`-that for isomorphic graphs the algorithm will always say they are isomorphic.`
`-`
`-Like it was said in the preface the definition of isomorphism dictates that`
`-such a mapping exists, but there can be more than one. Now, to prove that the`
`-algorithm works, all we have to do is prove this lemma:`
`-`
`-Lemma 2: If there is a map from node indexes to IDs in the two graphs, in`
`-which every node from graph G1 has the same ID as a matching node from graph`
`-G2, then applying the p->n transform one time will not change this condition.`
`-`
`-This is easy to prove because if the graphs are indeed isomorphic, then the`
`-p->n transform which is symmetric regarding the indexes of the nodes, will`
`-also generate such a mapping from indexes to IDs.`
`-`
`-The algorithm performs a complete scan and matches every node with an ID that `
`-appears more than once to every other node with that ID (and so recursively), `
`-so it cannot fail.`
`-`
`-This is not a full proof, but I believe it can be built using this as a`
`-skeleton.`
`-`
`-7. References:`
`---------------`
`-`
`-http://t2.technion.ac.il/~shlomif/graphs_equal/`
`-`
`-    Contains Refernce Source code in perl and various test programs in C and `
`-    in perl. Also contains an online version of this document.`
`-`
`-[ I'll have to ask Prof. Shimon Even for more]`
`-`
`-8. To Do`
`-----------`
`-`
`-- Proper Proof.`
`-- More References.`
`-- Convert to LaTeX and/or MS-Word (oh my).`
`-- Learn LaTeX.`
`-`

# File t2/graphs_equal/GraphIso.pm

`-package GraphIso;`
`-`
`-use Exporter;`
`-`
`-@ISA=qw(Exporter);`
`-`
`-@EXPORT=(qw(are_graphs_equal read_graph_from_file shuffle_graph), `
`-    qw(are_graphs_equal_preprocess_graph));`
`-`
`-use strict;`
`-`
`-sub numeric_max`
`-{`
`-    my \$max = shift;`
`-    foreach (@_)`
`-    {`
`-        if (\$_ > \$max)`
`-        {`
`-            \$max = \$_;`
`-        }`
`-    }`
`-    return \$max;`
`-}`
`-`
`-sub are_graphs_equal_preprocess_graph`
`-{`
`-    my \$num_nodes = shift;`
`-    my \$graph = shift;`
`-    my \$ret = { 'g' => \$graph, 'num_nodes' => \$num_nodes };`
`-    my (\$node, \$to_node);`
`-`
`-    # Get the maximal link width the graph has`
`-    `
`-    my \$max_link_count = 0;`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        for(\$to_node=0;\$to_node<\$num_nodes;\$to_node++)`
`-        {`
`-            if (\$node != \$to_node)`
`-            {`
`-                \$max_link_count = numeric_max(`
`-                    \$max_link_count,`
`-                    \$graph->[\$node][\$to_node]`
`-                    );`
`-            }`
`-        }`
`-    }`
`-`
`-    \$ret->{'max_link_count'} = \$max_link_count;`
`-`
`-    return \$ret;    `
`-}`
`-`
`-sub p2n_transform_iterations`
`-{`
`-    my (@graphs);`
`-    my (\$num_nodes, \$max_link_count, \$orig_ids, \$first_call);`
`-`
`-    (\$num_nodes, `
`-        \$graphs[0], `
`-        \$graphs[1], `
`-        \$max_link_count, `
`-        \$orig_ids, `
`-        \$first_call`
`-    ) = @_;`
`-`
`-    my (@prev_ids, @next_ids, \$iteration, %id_map, \$new_id);`
`-    my (\$g, \$node, \$to_node, @link_ids);`
`-    `
`-`
`-    @prev_ids = @{\$orig_ids};`
`-`
`-    for(\$iteration=0;\$iteration<\$num_nodes;\$iteration++)`
`-    {`
`-        @next_ids = ([], []);`
`-        %id_map = ();`
`-        \$new_id = 0;`
`-`
`-        for(\$g=0;\$g<2;\$g++)`
`-        {`
`-            for(\$node=0;\$node<\$num_nodes;\$node++)`
`-            {`
`-                # \$link_ids[\$w] contain the list of nodes which have`
`-                # a \$w-wide link to \$node.`
`-                @link_ids = (map { [] } ((0) x \$max_link_count));`
`-                `
`-                for(\$to_node=0;\$to_node<\$num_nodes;\$to_node++)`
`-                {`
`-                    if (\$to_node == \$node)`
`-                    {`
`-                        \$link_ids[0] = \$graphs[\$g]->[\$node][\$node];`
`-                    }`
`-                    elsif (\$graphs[\$g]->[\$node][\$to_node] > 0)`
`-                    {`
`-                        push `
`-                            @{\$link_ids[`
`-                                \$graphs[\$g]->[\$node][\$to_node]`
`-                            ]}, `
`-                            \$prev_ids[\$g]->[\$to_node];`
`-                    }`
`-                }`
`-`
`-                # Serialize the node ID`
`-`
`-                my \$string;`
`-`
`-                if ((\$iteration == 0) && \$first_call)`
`-                {`
`-                    # 1. We only need to consider the number of `
`-                    # connected nodes and the number of self-links`
`-                    # in the first iteration.`
`-                    #`
`-                    # Afterwards it is part of the information inside`
`-                    # the link ID.`
`-                    #`
`-                    # 2. I use scalar because all the node IDs are 0 `
`-                    # so we can simply count them.`
`-                    `
`-                    \$string = join(";",`
`-                        \$link_ids[0],`
`-                        (map { scalar(@{\$_}) } @link_ids[1 .. \$#link_ids])`
`-                    );`
`-                    `
`-                }`
`-                else`
`-                {`
`-                    # The identification string is built from the prev ID`
`-                    # of the node and from the IDs of the nodes that are`
`-                    # connected to it grouped by link width.`
`-                    #`
`-                    # The sort here can be implemented as Counting Sort`
`-                    # because the node IDs are limited to |V|.                    `
`-                    `
`-                    \$string = join(";",`
`-                        \$prev_ids[\$g]->[\$node],`
`-                        (map `
`-                            { join(",", (sort { \$a <=> \$b } @{\$_})); } `
`-                            @link_ids[1 .. \$#link_ids]`
`-                        )`
`-                    );`
`-                }`
`-`
`-                if (exists(\$id_map{\$string}))`
`-                {`
`-                    \$next_ids[\$g]->[\$node] = \$id_map{\$string};`
`-                }`
`-                else`
`-                {`
`-                    if (\$g == 1)`
`-                    {`
`-                        return 0;  # I encountered a string that `
`-                        # wasn't present in the previous graph, so `
`-                        # the graphs cannot be the same.`
`-                    }`
`-                    else`
`-                    {`
`-                        # Allocate a new ID for this template.`
`-                        \$id_map{\$string} = \$new_id;`
`-                        \$next_ids[\$g]->[\$node] = \$new_id;`
`-                        \$new_id++;`
`-                    }`
`-                }`
`-            }`
`-        }`
`-`
`-        # If there is a different number of nodes from each ID, the `
`-        # two graphs cannot be isomorphic.`
`-        # `
`-        # Again, this sort can be Counting Sort.`
`-        if (join(",", (sort { \$a <=> \$b } @{\$next_ids[0]})) ne `
`-            join(",", (sort { \$a <=> \$b } @{\$next_ids[1]}))   )`
`-        {`
`-            return 0;`
`-        }`
`-        if ((join(",", @{\$prev_ids[0]}) eq join(",", @{\$next_ids[0]})) &&`
`-            (join(",", @{\$prev_ids[1]}) eq join(",", @{\$next_ids[1]})) )`
`-        {`
`-            last;`
`-        }            `
`-        @prev_ids = @next_ids;`
`-    }`
`-    return (1, \@next_ids, \$new_id);`
`-}`
`-`
`-# The recursive part of are_graphs_equal`
`-sub age_recurse`
`-{`
`-    my (@graphs);`
`-    my (\$num_nodes, \$max_link_count, \$orig_ids, \$new_id);`
`-    my (\$safe);`
`-`
`-    (\$num_nodes,`
`-        \$graphs[0],`
`-        \$graphs[1],`
`-        \$max_link_count,`
`-        \$orig_ids,`
`-        \$new_id,`
`-        \$safe`
`-    ) = @_;`
`-    `
`-    # If all nodes of each graph contain |V| separate ID it means we have`
`-    # a one to one correlation between the two graphs. So, return true.`
`-    if (\$new_id == \$num_nodes)`
`-    {`
`-        return 1;`
`-    }`
`-        `
`-`
`-    my (\$id_to_change, \$node, @id_map, \$the_id);`
`-    my (\$place_to_change);    `
`-    `
`-    # Find an ID that is shared by two or more nodes.`
`-`
`-    @id_map = ((0) x \$new_id);`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        \$the_id = \$orig_ids->[0]->[\$node];`
`-        if ((++\$id_map[\$the_id]) == 2)`
`-        {`
`-            \$id_to_change = \$the_id;`
`-            \$place_to_change = \$node;`
`-            last;`
`-        }`
`-    }`
`-    `
`-    # Take one node from each graph that was assigned this ID and`
`-    # modify its ID to a non-existant one.`
`-`
`-`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        if (\$orig_ids->[1]->[\$node] == \$id_to_change)`
`-        {`
`-            my (@updated_ids);`
`-            `
`-            # Generate an IDs configuration with two IDs in the graphs`
`-            # modified to a non-existant ID.`
`-            @updated_ids = ( [ @{\$orig_ids->[0]} ], [ @{\$orig_ids->[1]} ] );`
`-            \$updated_ids[0]->[\$place_to_change] = \$new_id;`
`-            \$updated_ids[1]->[\$node] = \$new_id;`
`-            `
`-            # Run the @prev_ids -> @next_ids transformation on it |V| times.`
`-            my (\$ret, \$next_ids, \$new_id) = p2n_transform_iterations(`
`-                \$num_nodes,`
`-                @graphs,`
`-                \$max_link_count,`
`-                \@updated_ids,`
`-                0`
`-                );`
`-`
`-            if (\$ret)`
`-            {`
`-                # Check the new configuration`
`-                \$ret = age_recurse(`
`-                    \$num_nodes,`
`-                    @graphs,`
`-                    \$max_link_count,`
`-                    \$next_ids,`
`-                    \$new_id,`
`-                    \$safe);`
`-`
`-                # If \$safe is zero we assume that the first `
`-                # p2n_transform_iterations can't be wrong.`
`-                if ((!\$safe) || \$ret)`
`-                {`
`-                    return \$ret;`
`-                }`
`-            }`
`-        }`
`-    }`
`-`
`-    # We couldn't find a working configuration, so let's return`
`-    # false.`
`-`
`-    return 0;`
`-}`
`-`
`-# (\$ret) = are_graphs_equal(\$graph_handle1, \$graph_handle2, \$safe);`
`-#`
`-# The main function as far as the user is concerned.`
`-#`
`-# All it does is call the |V| prev_ids->next_ids transformations once`
`-# and then call age_recurse(). `
`-#`
`-# It is possible that the algorithm may not work if \$safe equals false.`
`-# But then again it usually does.`
`-sub are_graphs_equal`
`-{`
`-    my (@graphs, \$safe, \$max_link_count, \$num_nodes);`
`-    my (@initial_ids);`
`-    my (@graph_handles);`
`-`
`-    \$graph_handles[0] = shift;`
`-    \$graph_handles[1] = shift;`
`-    \$safe = shift;`
`-`
`-    if (\$graph_handles[0]->{'num_nodes'} != \$graph_handles[1]->{'num_nodes'})`
`-    {`
`-        return 0;`
`-    }`
`-    \$num_nodes = \$graph_handles[0]->{'num_nodes'};`
`-`
`-    if (\$graph_handles[0]->{'max_link_count'} != `
`-        \$graph_handles[1]->{'max_link_count'} )`
`-    {`
`-        return 0;`
`-    }`
`-    \$max_link_count = \$graph_handles[0]->{'max_link_count'};`
`-      `
`-`
`-    @graphs = (map { \$_->{'g'} } @graph_handles);`
`-`
`-    @initial_ids = ([ (0) x \$num_nodes ], [ (0) x \$num_nodes ]);`
`-`
`-    # Call the |V| @prev_ids->@next_ids once.`
`-    my (\$ret, \$next_ids, \$new_id) = p2n_transform_iterations(`
`-        \$num_nodes,`
`-        @graphs,`
`-        \$max_link_count,`
`-        \@initial_ids,`
`-        1`
`-        );`
`-`
`-    if (!\$ret)`
`-    {`
`-        return 0;`
`-    }`
`-    else`
`-    {`
`-        return age_recurse(`
`-            \$num_nodes,`
`-            @graphs,`
`-            \$max_link_count,`
`-            \$next_ids,`
`-            \$new_id,`
`-            \$safe`
`-            );`
`-    }`
`-}`
`-`
`-sub read_graph_from_file`
`-{`
`-    my \$filename = shift;`
`-`
`-    open I, "<" . \$filename;`
`-`
`-    my \$num_nodes = <I>;`
`-    chomp(\$num_nodes);`
`-`
`-    my \$graph = [ (0) x \$num_nodes ];`
`-    my (\$node);`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        \$graph->[\$node] = [ (0) x \$num_nodes ];`
`-    }`
`-`
`-    my (@numbers);`
`-`
`-    while (<I>)`
`-    {`
`-        if (! m/\S/)`
`-        {`
`-            last;`
`-        }`
`-        `
`-        @numbers = m/\d+/g;`
`-`
`-        if (\$numbers[0] == \$numbers[1])`
`-        {`
`-            \$graph->[\$numbers[0]]->[\$numbers[1]]++;`
`-        }`
`-        else`
`-        {`
`-            \$graph->[\$numbers[0]]->[\$numbers[1]]++;`
`-            \$graph->[\$numbers[1]]->[\$numbers[0]]++;`
`-        }`
`-    }`
`-`
`-    close(I);`
`-`
`-    return (\$num_nodes, \$graph);`
`-}`
`-`
`-sub shuffle_graph`
`-{`
`-    my \$num_nodes = shift;`
`-    my \$orig_graph = shift;`
`-`
`-    my \$graph = [ (0) x \$num_nodes ];`
`-    my (\$node, \$to_node);`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        \$graph->[\$node] = [ (0) x \$num_nodes ];`
`-    }`
`-`
`-    my (@indexes);`
`-`
`-    @indexes = ( 0 .. (\$num_nodes-1));`
`-    my (\$n, \$j);`
`-`
`-    \$n = \$num_nodes-1;`
`-    while (\$n > 0)`
`-    {`
`-        \$j = int(rand(\$n+1));`
`-        (\$indexes[\$n], \$indexes[\$j]) = (\$indexes[\$j], \$indexes[\$n]);`
`-        \$n--;`
`-    }`
`-`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        for(\$to_node=0;\$to_node<\$num_nodes;\$to_node++)`
`-        {`
`-            \$graph->[\$indexes[\$node]][\$indexes[\$to_node]] = `
`-                \$orig_graph->[\$node][\$to_node];`
`-        }`
`-    }`
`-`
`-    return \$graph;`
`-}`
`-`
`-1;`

# File t2/graphs_equal/Graph_Equal.pl

Empty file removed.

# File t2/graphs_equal/Graphs_Equal.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-srand(105);`
`-`
`-my (\$a);`
`-`
`-my \$num_graphs=100;`
`-`
`-my (\$num_nodes, \$graph, @graphs);`
`-`
`-for(\$a=0;\$a<\$num_graphs;\$a++)`
`-{`
`-    (\$num_nodes, \$graphs[\$a]) = read_graph_from_file("test_graph.\$a.txt");`
`-    \$graphs[\$a] = are_graphs_equal_preprocess_graph(\$num_nodes, \$graphs[\$a]);`
`-}`
`-`
`-my (\$b);`
`-`
`-my \$count = 0;`
`-`
`-my (@param_graphs);`
`-`
`-for(\$a=0;\$a<\$num_graphs;\$a++)`
`-{`
`-    for(\$b=\$a;\$b<\$num_graphs;\$b++)`
`-    {`
`-        if (\$a == \$b)`
`-        {`
`-            @param_graphs = (`
`-                \$graphs[\$a], `
`-                eval {`
`-                    my \$g = {%{\$graphs[\$b]}};`
`-                    \$g->{'g'} = shuffle_graph(\$num_nodes, \$g->{'g'});`
`-                    \$g;`
`-                }`
`-                );`
`-        }`
`-        else`
`-        {`
`-            @param_graphs = @graphs[\$a,\$b];`
`-        }`
`-        my \$ret_safe = are_graphs_equal(@param_graphs, 1);`
`-        my \$ret_unsafe = are_graphs_equal(@param_graphs, 0);`
`-`
`-        if (\$ret_safe != \$ret_unsafe)`
`-        {`
`-            print "\$a ? (\$ret_safe \$ret_unsafe) ? \$b\n";`
`-            exit (5);`
`-        }`
`-        if (\$ret_safe)`
`-        {`
`-            #print "\$a == \$b.\n";`
`-            if (\$a != \$b)`
`-            {`
`-                print "\$a == \$b.\n";`
`-                exit(5);`
`-            }`
`-        }`
`-        elsif ((!\$ret_safe) && (\$a == \$b))`
`-        {`
`-            print "\$a != \$b.\n";`
`-            exit(5);`
`-            #print "\$a != \$b.\n";`
`-        }`
`-        if (\$count++ % 100 == 0)`
`-        {`
`-            print "\$count\n";`
`-        }`
`-    }`
`-}`
`-`
`-exit(0);`
`-`
`-if (0)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph);`
`-`
`-    my \$a = int(rand(\$num_nodes));`
`-    my \$b = int(rand(\$num_nodes));`
`-`
`-    if (\$a == \$b)`
`-    {`
`-        \$shuffled_graph->[\$a][\$a]++;`
`-    }`
`-    else`
`-    {`
`-        \$shuffled_graph->[\$a][\$b]++;`
`-        \$shuffled_graph->[\$b][\$a]++;`
`-    }`
`-    print (are_graphs_equal(\$num_nodes, \$graph, \$shuffled_graph), "\n");`
`-}`

# File t2/graphs_equal/dump.txt

`-\$si=0`
`-\$iteration=0`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=0`
`-\$iteration=1`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=0`
`-\$iteration=2`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=0`
`-\$iteration=3`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=0`
`-\$iteration=4`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=0`
`-\$iteration=5`
`-0,0,0,0,0,0`
`-0,0,0,0,0,0`
`-`
`-`
`-\$si=1`
`-\$iteration=0`
`-0,1,0,0,0,1`
`-0,1,1,0,0,0`
`-`
`-`
`-\$si=1`
`-\$iteration=1`
`-0,1,2,1,2,1`
`-0,2,2,1,1,1`
`-`
`-`
`-\$si=1`
`-\$iteration=2`
`-0,1,0,2,0,1`
`-2,1,1,0,0,0`
`-`
`-`
`-\$si=1`
`-\$iteration=3`
`-0,1,2,1,2,1`
`-0,2,2,1,1,1`
`-`
`-`
`-\$si=1`
`-\$iteration=4`
`-0,1,0,2,0,1`
`-2,1,1,0,0,0`
`-`
`-`
`-\$si=1`
`-\$iteration=5`
`-0,1,2,1,2,1`
`-0,2,2,1,1,1`
`-`
`-`
`-\$si=2`
`-\$iteration=0`
`-0,1,0,2,3,1`
`-2,1,1,3,0,0`
`-`
`-`
`-\$si=2`
`-\$iteration=1`
`-0,1,2,3,2,3`
`-0,2,2,1,3,3`
`-`
`-`
`-\$si=2`
`-\$iteration=2`
`-0,1,0,2,3,1`
`-2,1,1,3,0,0`
`-`
`-`
`-\$si=2`
`-\$iteration=3`
`-0,1,2,3,2,3`
`-0,2,2,1,3,3`
`-`
`-`
`-\$si=2`
`-\$iteration=4`
`-0,1,0,2,3,1`
`-2,1,1,3,0,0`
`-`
`-`
`-\$si=2`
`-\$iteration=5`
`-0,1,2,3,2,3`
`-0,2,2,1,3,3`
`-`
`-`
`-\$si=3`
`-\$iteration=0`
`-0,1,0,2,3,4`
`-2,4,1,3,0,0`
`-`
`-`
`-\$si=3`
`-\$iteration=1`
`-0,1,2,3,4,3`
`-0,2,4,1,3,3`
`-`
`-`
`-\$si=3`
`-\$iteration=2`
`-0,1,0,2,3,4`
`-2,4,1,3,0,0`
`-`
`-`
`-\$si=3`
`-\$iteration=3`
`-0,1,2,3,4,3`
`-0,2,4,1,3,3`
`-`
`-`
`-\$si=3`
`-\$iteration=4`
`-0,1,0,2,3,4`
`-2,4,1,3,0,0`
`-`
`-`
`-\$si=3`
`-\$iteration=5`
`-0,1,2,3,4,3`
`-0,2,4,1,3,3`
`-`
`-`
`-\$si=4`
`-\$iteration=0`
`-0,1,2,3,4,5`
`-3,5,1,4,0,2`
`-`
`-`
`-\$si=4`
`-\$iteration=1`
`-0,1,2,3,4,5`
`-0,2,4,1,3,5`
`-`
`-`
`-\$si=4`
`-\$iteration=2`
`-0,1,2,3,4,5`
`-3,5,1,4,0,2`
`-`
`-`
`-\$si=4`
`-\$iteration=3`
`-0,1,2,3,4,5`
`-0,2,4,1,3,5`
`-`
`-`
`-\$si=4`
`-\$iteration=4`
`-0,1,2,3,4,5`
`-3,5,1,4,0,2`
`-`
`-`
`-\$si=4`
`-\$iteration=5`
`-0,1,2,3,4,5`
`-0,2,4,1,3,5`
`-`
`-`
`-1`

# File t2/graphs_equal/ge1.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-use Data::Dumper;`
`-`
`-my (\$g1, \$num_nodes, \$g2);`
`-(\$num_nodes, \$g1) = read_graph_from_file("tg0.txt");`
`-(\$num_nodes, \$g2) = read_graph_from_file("tg1.txt");`
`-print (are_graphs_equal(\$num_nodes, \$g1, \$g2), "\n");`
`-`
`-exit(0);`
`-`
`-srand(105);`
`-`
`-my (\$a);`
`-`
`-my \$num_graphs=20;`
`-`
`-my (\$num_nodes, \$graph, @graphs);`
`-`
`-for(\$a=0;\$a<\$num_graphs;\$a++)`
`-{`
`-    (\$num_nodes, \$graphs[\$a]) = read_graph_from_file("test_graph.\$a.txt");`
`-}`
`-`
`-while(1)`
`-{`
`-    my \$a = int(rand(\$num_graphs));`
`-    my \$b = int(rand(\$num_graphs));`
`-`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graphs[\$b]);`
`-`
`-    my \$ret = are_graphs_equal(\$num_nodes, \$graphs[\$a], \$shuffled_graph);`
`-`
`-    if (\$ret)`
`-    {`
`-        print "\$a == \$b.\n";`
`-    }`
`-    else`
`-    {`
`-        print "\$a != \$b.\n";`
`-    }`
`-}`
`-`
`-if (0)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph);`
`-`
`-    my \$a = int(rand(\$num_nodes));`
`-    my \$b = int(rand(\$num_nodes));`
`-`
`-    if (\$a == \$b)`
`-    {`
`-        \$shuffled_graph->[\$a][\$a]++;`
`-    }`
`-    else`
`-    {`
`-        \$shuffled_graph->[\$a][\$b]++;`
`-        \$shuffled_graph->[\$b][\$a]++;`
`-    }`
`-    print (are_graphs_equal(\$num_nodes, \$graph, \$shuffled_graph), "\n");`
`-}`

# File t2/graphs_equal/ge2.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-srand(105);`
`-`
`-my (\$num_nodes, \$graph);`
`-`
`-(\$num_nodes, \$graph) = read_graph_from_file("tg2.txt");`
`-`
`-while (1)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph);`
`-`
`-    my \$g1 = are_graphs_equal_preprocess_graph(\$num_nodes, \$graph);`
`-    my \$g2 = are_graphs_equal_preprocess_graph(\$num_nodes, \$shuffled_graph);`
`-`
`-    my \$safe_ret = are_graphs_equal(\$g1, \$g2, 1);`
`-    my \$non_safe_ret = are_graphs_equal(\$g1, \$g2, 0);`
`-`
`-    print "\$safe_ret   \$non_safe_ret\n";`
`-    if (\$safe_ret != \$non_safe_ret)`
`-    {`
`-        last;`
`-    }`
`-}`

# File t2/graphs_equal/ge3.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-srand(105);`
`-`
`-my (\$a);`
`-`
`-my \$num_graphs=100;`
`-`
`-my (\$num_nodes, \$graph, @graphs);`
`-`
`-for(\$a=0;\$a<\$num_graphs;\$a++)`
`-{`
`-    (\$num_nodes, \$graphs[\$a]) = read_graph_from_file("test_graph.\$a.txt");`
`-}`
`-`
`-my (\$b);`
`-`
`-my \$count = 0;`
`-`
`-for(\$a=0;\$a<\$num_graphs;\$a++)`
`-{`
`-    for(\$b=\$a;\$b<\$num_graphs;\$b++)`
`-    {`
`-        my \$ret = are_graphs_equal(\$num_nodes, \$graphs[\$a], \$graphs[\$b]);`
`-`
`-        if (\$ret)`
`-        {`
`-            #print "\$a == \$b.\n";`
`-            if (\$a != \$b)`
`-            {`
`-                print "\$a == \$b.\n";`
`-                exit(5);`
`-            }`
`-        }`
`-        else`
`-        {`
`-            #print "\$a != \$b.\n";`
`-        }`
`-        if (\$count++ % 100 == 0)`
`-        {`
`-            print "\$count\n";`
`-        }`
`-    }`
`-}`
`-`
`-exit(0);`
`-`
`-if (0)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph);`
`-`
`-    my \$a = int(rand(\$num_nodes));`
`-    my \$b = int(rand(\$num_nodes));`
`-`
`-    if (\$a == \$b)`
`-    {`
`-        \$shuffled_graph->[\$a][\$a]++;`
`-    }`
`-    else`
`-    {`
`-        \$shuffled_graph->[\$a][\$b]++;`
`-        \$shuffled_graph->[\$b][\$a]++;`
`-    }`
`-    print (are_graphs_equal(\$num_nodes, \$graph, \$shuffled_graph), "\n");`
`-}`

# File t2/graphs_equal/ge4.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-srand(105);`
`-`
`-my (\$num_nodes, \$graph1, \$graph2);`
`-`
`-(\$num_nodes, \$graph1) = read_graph_from_file("tg0.txt");`
`-(\$num_nodes, \$graph2) = read_graph_from_file("tg1.txt");`
`-`
`-while (1)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph2);`
`-`
`-    my \$g1 = are_graphs_equal_preprocess_graph(\$num_nodes, \$graph1);`
`-    my \$g2 = are_graphs_equal_preprocess_graph(\$num_nodes, \$shuffled_graph);`
`-`
`-    my \$safe_ret = are_graphs_equal(\$g1, \$g2, 1);`
`-    my \$non_safe_ret = are_graphs_equal(\$g1, \$g2, 0);`
`-`
`-    print "\$safe_ret   \$non_safe_ret\n";`
`-    if (\$safe_ret != \$non_safe_ret)`
`-    {`
`-        last;`
`-    }`
`-}`

# File t2/graphs_equal/ge5.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use GraphIso;`
`-`
`-srand(105);`
`-`
`-my (\$num_nodes, \$graph1, \$graph2);`
`-`
`-(\$num_nodes, \$graph1) = read_graph_from_file("tg6.txt");`
`-(\$num_nodes, \$graph2) = read_graph_from_file("tg6.txt");`
`-`
`-while (1)`
`-{`
`-    my \$shuffled_graph = shuffle_graph(\$num_nodes, \$graph2);`
`-`
`-    my \$g1 = are_graphs_equal_preprocess_graph(\$num_nodes, \$graph1);`
`-    my \$g2 = are_graphs_equal_preprocess_graph(\$num_nodes, \$shuffled_graph);`
`-`
`-    my \$safe_ret = are_graphs_equal(\$g1, \$g2, 1);`
`-    my \$non_safe_ret = are_graphs_equal(\$g1, \$g2, 0);`
`-`
`-    print "\$safe_ret   \$non_safe_ret\n";`
`-    if (\$safe_ret != \$non_safe_ret)`
`-    {`
`-        last;`
`-    }`
`-}`

# File t2/graphs_equal/ge_bare.pl

`-sub numeric_max`
`-{`
`-    my \$max = shift;`
`-    foreach (@_)`
`-    {`
`-        if (\$_ > \$max)`
`-        {`
`-            \$max = \$_;`
`-        }`
`-    }`
`-    return \$max;`
`-}`
`-`
`-sub are_graphs_equal_preprocess_graph`
`-{`
`-    my \$num_nodes = shift;`
`-    my \$graph = shift;`
`-    my \$ret = { 'g' => \$graph, 'num_nodes' => \$num_nodes };`
`-    my (\$node, \$to_node);`
`-`
`-    # Get the maximal link width the graph has`
`-    `
`-    my \$max_link_count = 0;`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        for(\$to_node=0;\$to_node<\$num_nodes;\$to_node++)`
`-        {`
`-            if (\$node != \$to_node)`
`-            {`
`-                \$max_link_count = numeric_max(`
`-                    \$max_link_count,`
`-                    \$graph->[\$node][\$to_node]`
`-                    );`
`-            }`
`-        }`
`-    }`
`-`
`-    \$ret->{'max_link_count'} = \$max_link_count;`
`-`
`-    # Get how many nodes are reachable from every node by means`
`-    # of DFS/BFS.`
`-`
`-    my (%connected_nodes, @num_connected_nodes);`
`-`
`-    @num_connected_nodes = ((-1) x \$num_nodes);`
`-`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        if (\$num_connected_nodes[\$node] == -1)`
`-        {`
`-            %connected_nodes = ();`
`-`
`-            my (@nodes_to_visit, \$n, \$tn);`
`-`
`-            @nodes_to_visit = (\$node);`
`-`
`-            while (scalar(@nodes_to_visit))`
`-            {`
`-                #\$n = shift(@nodes_to_visit);   # For BFS`
`-                \$n = pop(@nodes_to_visit);     # For DFS`
`-                if (!exists(\$connected_nodes{\$n}))`
`-                {`
`-                    \$connected_nodes{\$n} = 1;`
`-                    for(\$tn=0;\$tn<\$num_nodes;\$tn++)`
`-                    {`
`-                        if ( (\$graph->[\$n][\$tn] > 0) &&`
`-                             (!exists(\$connected_nodes{\$n})) )`
`-                        {`
`-                            push @nodes_to_visit, \$tn;`
`-                        }`
`-                    }`
`-                }`
`-            }`
`-`
`-            foreach my \$n (keys(%connected_nodes))`
`-            {`
`-                \$num_connected_nodes[\$n] = scalar(keys(%connected_nodes));`
`-            }`
`-        }`
`-    }`
`-`
`-    \$ret->{'num_connected_nodes'} = [ @num_connected_nodes ] ;`
`-`
`-    return \$ret;    `
`-}`
`-`
`-sub are_graphs_equal`
`-{`
`-    my (@graphs);`
`-    my (@graph_handles);`
`-    `
`-    \$graph_handles[0] = shift;`
`-    \$graph_handles[1] = shift;`
`-`
`-    # If the two graph do not have the same number of nodes then they `
`-    # are certainly not isomorphic.`
`-    if (\$graph_handles[0]->{'num_nodes'} != \$graph_handles[1]->{'num_nodes'})`
`-    {`
`-        return 0;`
`-    }`
`-`
`-    my \$num_nodes = \$graph_handles[0]->{'num_nodes'};`
`-`
`-    @graphs = (map { \$_->{'g'} } @graph_handles);`
`-`
`-    `
`-`
`-    my (@prev_ids, @next_ids, %id_map);`
`-`
`-    # Initial value for the prev_ids: all zeros`
`-    @prev_ids = ([ (0) x \$num_nodes ], [ (0) x \$num_nodes ]);`
`-`
`-    my (\$iteration, \$node, \$g, \$to_node, @link_ids, \$max_link_count, \$new_id);`
`-    my (\$super_iteration);`
`-`
`-    # If the graphs do not have the same maximum for width of link, they`
`-    # are not isomorphic.`
`-`
`-    if (\$graph_handles[0]->{'max_link_count'} != \$graph_handles[1]->{'max_link_count'})`
`-    {`
`-        return 0;`
`-    }`
`-    \$max_link_count = \$graph_handles[0]->{'max_link_count'};`
`-   `
`-    # Retrieve the number of nodes which are reachable from every node in the `
`-    # graph.`
`-    my (@num_connected_nodes);`
`-`
`-    @num_connected_nodes = (map { [ @{\$_->{'num_connected_nodes'}} ] } @graph_handles);`
`-    `
`-    for(\$super_iteration=0;\$super_iteration<\$num_nodes;\$super_iteration++)`
`-    {`
`-        for(\$iteration=0;\$iteration<\$num_nodes;\$iteration++)`
`-        {`
`-            @next_ids = ([], []);`
`-            %id_map = ();`
`-            \$new_id = 0;`
`-`
`-            for(\$g=0;\$g<2;\$g++)`
`-            {`
`-                for(\$node=0;\$node<\$num_nodes;\$node++)`
`-                {`
`-                    # \$link_ids[\$w] contain the list of nodes which have`
`-                    # a \$w-wide link to \$node.`
`-                    @link_ids = (map { [] } ((0) x \$max_link_count));`
`-                    `
`-                    for(\$to_node=0;\$to_node<\$num_nodes;\$to_node++)`
`-                    {`
`-                        if (\$to_node == \$node)`
`-                        {`
`-                            \$link_ids[0] = \$graphs[\$g]->[\$node][\$node];`
`-                        }`
`-                        elsif (\$graphs[\$g]->[\$node][\$to_node] > 0)`
`-                        {`
`-                            push `
`-                                @{\$link_ids[`
`-                                    \$graphs[\$g]->[\$node][\$to_node]`
`-                                ]}, `
`-                                \$prev_ids[\$g]->[\$to_node];`
`-                        }`
`-                    }`
`-`
`-                    # Serialize the node ID`
`-`
`-                    my \$string;`
`-`
`-                    if ((\$iteration == 0) && (\$super_iteration == 0))`
`-                    {`
`-                        # 1. We only need to consider the number of `
`-                        # connected nodes and the number of self-links`
`-                        # in the first iteration.`
`-                        #`
`-                        # Afterwards it is part of the information inside`
`-                        # the link ID.`
`-                        #`
`-                        # 2. I use scalar because all the node IDs are 0 `
`-                        # so we can simply count them.`
`-                        `
`-                        \$string = join(";", `
`-                            \$num_connected_nodes[\$g]->[\$node],`
`-                            \$link_ids[0],`
`-                            (map { scalar(@{\$_}) } @link_ids[1 .. \$#link_ids])`
`-                        );`
`-                        `
`-                    }`
`-                    else`
`-                    {`
`-                        # The identification string is built from the prev ID`
`-                        # of the node and from the IDs of the nodes that are`
`-                        # connected to it grouped by link width.`
`-                        \$string = join(";",`
`-                            \$prev_ids[\$g]->[\$node],`
`-                            (map `
`-                                { join(",", (sort { \$a <=> \$b } @{\$_})); } `
`-                                @link_ids[1 .. \$#link_ids]`
`-                            )`
`-                        );`
`-                    }`
`-`
`-                    if (exists(\$id_map{\$string}))`
`-                    {`
`-                        \$next_ids[\$g]->[\$node] = \$id_map{\$string};`
`-                    }`
`-                    else`
`-                    {`
`-                        if (\$g == 1)`
`-                        {`
`-                            return 0;  # I encountered a string that `
`-                            # wasn't present in the previous graph, so `
`-                            # the graphs cannot be the same.`
`-                        }`
`-                        else`
`-                        {`
`-                            # Allocate a new ID for this template.`
`-                            \$id_map{\$string} = \$new_id;`
`-                            \$next_ids[\$g]->[\$node] = \$new_id;`
`-                            \$new_id++;`
`-                        }`
`-                    }`
`-                }`
`-            }`
`-`
`-            # If there is a different number of nodes from each ID, the `
`-            # two graphs cannot be isomorphic.`
`-            if (join(",", (sort { \$a <=> \$b } @{\$next_ids[0]})) ne `
`-                join(",", (sort { \$a <=> \$b } @{\$next_ids[1]}))   )`
`-            {`
`-                return 0;`
`-            }`
`-            @prev_ids = @next_ids;`
`-        }`
`-        if (\$new_id == \$num_nodes)`
`-        {`
`-            return 1;`
`-        } `
`-        {`
`-            my (@sorted_ids, \$i, \$id_to_change);`
`-            `
`-            # Find an ID that is shared by two or more nodes.`
`-            `
`-            @sorted_ids = (sort {\$a <=> \$b } @{\$prev_ids[0]});`
`-            for(\$i=0;\$i<\$num_nodes;\$i++)`
`-            {`
`-                if (\$sorted_ids[\$i] == \$sorted_ids[\$i+1])`
`-                {`
`-                    \$id_to_change = \$sorted_ids[\$i];`
`-                    last;`
`-                }`
`-            }`
`-            `
`-            # Take one node from each graph that was assigned this ID and`
`-            # modify its ID to a non-existant one.`
`-            `
`-            for(\$g=0;\$g<2;\$g++)`
`-            {`
`-                for(\$i=0;\$i<\$num_nodes;\$i++)`
`-                {`
`-                    if (\$prev_ids[\$g]->[\$i] == \$id_to_change)`
`-                    {`
`-                        \$prev_ids[\$g]->[\$i] = \$new_id;`
`-                        last;`
`-                    }`
`-                }`
`-            }`
`-        }`
`-    }`
`-`
`-    return 1;`
`-}`

# File t2/graphs_equal/gen_graphs.c

`-#include <stdlib.h>`
`-#include <stdio.h>`
`-`
`-#ifdef _MSC_VER`
`-typedef __int64 integer64;`
`-#define INT64_CONSTANT(c) (c##i64)`
`-#elif defined(__GNUC__)`
`-typedef __int64_t integer64;`
`-#define INT64_CONSTANT(c) (c##ll)`
`-#endif`
`-`
`-struct struct_pysol_random_context`
`-{`
`-    integer64 seed;`
`-    double (*random)(struct struct_pysol_random_context *); `
`-    int (*randint)(struct struct_pysol_random_context *, int a, int b);`
`-};`
`-`
`-typedef struct struct_pysol_random_context pysol_random_context;`
`-`
`-int pysol_random64_randint(pysol_random_context * context, int a, int b)`
`-{`
`-    return (a + (int)(context->random(context) * (b+1-a)));`
`-}`
`-`
`-`
`-double pysol_random64(pysol_random_context * context)`
`-{`
`-    context->seed = (context->seed*INT64_CONSTANT(6364136223846793005) + INT64_CONSTANT(1)) & INT64_CONSTANT(0xffffffffffffffff);`
`-    return ((context->seed >> 21) & INT64_CONSTANT(0x7fffffff)) / 2147483648.0;`
`-}`
`-`
`-double pysol_random31(pysol_random_context * context)`
`-{`
`-    context->seed = (context->seed*INT64_CONSTANT(214013) + INT64_CONSTANT(2531011)) &  INT64_CONSTANT(0x7fffffff);`
`-    return (context->seed >> 16) / 32768.0;`
`-}`
`-`
`-int pysol_random31_randint(pysol_random_context * context, int a, int b)`
`-{`
`-    context->seed = (context->seed*INT64_CONSTANT(214013) + INT64_CONSTANT(2531011)) & INT64_CONSTANT(0x7fffffff);`
`-    return a + (((int)(context->seed >> 16)) % (b+1-a));`
`-}`
`-`
`-typedef int node_t;`
`-`
`-typedef node_t * * graph_t;`
`-`
`-graph_t create_graph(int num_nodes)`
`-{`
`-    graph_t ret;`
`-    int a, b;`
`-`
`-    ret = malloc(sizeof(node_t *) * num_nodes);`
`-    for(a=0;a<num_nodes;a++)`
`-    {`
`-        ret[a] = malloc(sizeof(node_t)*num_nodes);`
`-        for(b=0;b<num_nodes;b++)`
`-        {`
`-            ret[a][b] = 0;`
`-        }`
`-    }`
`-    return ret;`
`-}`
`-        `
`-void destroy_graph(int num_nodes, graph_t graph)`
`-{`
`-    int a;`
`-    for(a=0;a<num_nodes;a++)`
`-    {`
`-        free(graph[a]);`
`-    }`
`-    free(graph);`
`-}`
`-`
`-graph_t generate_random_graph(int num_nodes, int num_links, pysol_random_context * r)`
`-{`
`-    graph_t graph;`
`-    int a, node, to_node;`
`-`
`-    graph = create_graph(num_nodes);`
`-`
`-    for(a=0;a<num_links;a++)`
`-    {`
`-        node = (r->randint(r, 0, num_nodes-1));`
`-        to_node = (r->randint(r, 0, num_nodes-1));`
`-        if (node == to_node)`
`-        {`
`-            graph[node][to_node]++;`
`-        }`
`-        else`
`-        {`
`-            graph[node][to_node]++;`
`-            graph[to_node][node]++;`
`-        }`
`-    }`
`-`
`-    return graph;`
`-}`
`-`
`-int write_graph_to_file(char * filename, int num_nodes, graph_t graph)`
`-{`
`-    FILE * o;`
`-    int node, to_node;`
`-    node_t a;`
`-`
`-    o = fopen(filename, "wt");`
`-    if (o == NULL)`
`-    {`
`-        return 1;`
`-    }`
`-`
`-    fprintf(o, "%i\n", num_nodes);`
`-    for(node=0;node<num_nodes;node++)`
`-    {`
`-        for(to_node=node;to_node<num_nodes;to_node++)`
`-        {`
`-            for(a=0;a<graph[node][to_node];a++)`
`-            {`
`-                fprintf(o, "%i -> %i\n", node, to_node);`
`-            }`
`-        }`
`-    }`
`-`
`-    fclose(o);`
`-`
`-    return 0;`
`-}`
`-`
`-int main(int argc, char * argv[])`
`-{`
`-    int seed;`
`-    int num_nodes;`
`-    pysol_random_context r;`
`-    int a;`
`-    graph_t graph;`
`-    char filename[80];`
`-`
`-    if (argc > 1)`
`-    {`
`-        seed = atoi(argv[1]);`
`-    }`
`-    `
`-    num_nodes = 15;`
`-`
`-    r.seed = seed;`
`-    r.random = pysol_random64;`
`-    r.randint = pysol_random64_randint;`
`-`
`-    for(a=0;a<100;a++)`
`-    {`
`-        graph = generate_random_graph(num_nodes, 35, &r);`
`-        sprintf(`
`-            filename, `
`-            "test_graph.%i.txt", `
`-            a);`
`-        write_graph_to_file(filename, num_nodes, graph);`
`-        destroy_graph(num_nodes, graph);`
`-    }`
`-`
`-    return 0;`
`-}`

# File t2/graphs_equal/gen_graphs.pl

`-#!/usr/bin/perl`
`-`
`-use strict;`
`-`
`-use Math::BigInt;`
`-`
`-my \$random_mask1 = ((new Math::BigInt(2)) ** (eval { my @a = ("0xffffffffffffffffL" =~ /f/g); scalar(@a); } * 4));`
`-`
`-my \$random_mask2 = ((new Math::BigInt(2)) ** (eval { my \$num = "0x7fffffffL"; my @a = (\$num =~ /f/g); my @b = (\$num =~ /7/g); (scalar(@a)*4+scalar(@b)*3); }));`
`-`
`-my \$random_mask3 = ((new Math::BigInt(2)) ** 21);`
`-`
`-my \$random_mask4 = (new Math::BigInt("6364136223846793005"));`
`-`
`-sub get_new_random_context`
`-{`
`-    my \$seed = shift;`
`-`
`-    return {`
`-        'seed' => (new Math::BigInt(\$seed))`
`-        };        `
`-}`
`-`
`-sub myrand`
`-{`
`-    my \$random_context = shift;`
`-    my \$rand_max = shift;`
`-`
`-    \$random_context->{'seed'} =  ((\$random_context->{'seed'}*\$random_mask4 + 1) % \$random_mask1);`
`-`
`-    my \$ret = ((\$random_context->{'seed'} / \$random_mask3) % \$random_mask2);`
`-    \$ret = "\$ret";`
`-    return (\$ret / 2147483648.0)*\$rand_max;`
`-}`
`-`
`-sub write_graph_to_file`
`-{`
`-    my \$filename = shift;`
`-    my \$num_nodes = shift;`
`-    my \$graph = shift;`
`-`
`-    open O, ">". \$filename;`
`-    print O \$num_nodes, "\n";`
`-    my (\$node, \$to_node, \$a);`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        for(\$to_node=\$node;\$to_node<\$num_nodes;\$to_node++)`
`-        {`
`-            for(\$a=0;\$a<\$graph->[\$node][\$to_node];\$a++)`
`-            {`
`-                print O \$node, " -> ", \$to_node, "\n";`
`-            }`
`-        }`
`-    }`
`-    close(O);`
`-`
`-    return 1;`
`-}`
`-`
`-sub generate_random_graph`
`-{`
`-    my \$num_nodes = shift;`
`-    my \$num_links = shift;`
`-    my \$random_context = shift;`
`-`
`-    my \$graph = [ (0) x \$num_nodes ];`
`-    my (\$node, \$to_node);`
`-    for(\$node=0;\$node<\$num_nodes;\$node++)`
`-    {`
`-        \$graph->[\$node] = [ (0) x \$num_nodes ];`
`-    }`
`-`
`-    my \$a;`
`-    for(\$a=0;\$a<\$num_links;\$a++)`
`-    {`
`-        \$node = int(myrand(\$random_context, \$num_nodes));`
`-        \$to_node = int(myrand(\$random_context, \$num_nodes));`
`-        if (\$node == \$to_node)`
`-        {`
`-            \$graph->[\$node][\$to_node]++;`
`-        }`
`-        else`
`-        {`
`-            \$graph->[\$node][\$to_node]++;`
`-            \$graph->[\$to_node][\$node]++;`
`-        }`
`-    }`
`-`
`-    return \$graph;`
`-}`
`-`
`-my \$seed = shift || "102";`
`-`
`-my \$num_nodes = 15;`
`-`
`-#my \$random_context = get_new_random_context("57521231279");`
`-#my \$random_context = get_new_random_context("5");`
`-#my \$random_context = get_new_random_context("15");`
`-#my \$random_context = get_new_random_context("789");`
`-#my \$random_context = get_new_random_context("1023090");`
`-my \$random_context = get_new_random_context(\$seed);`
`-my (\$a, \$graph);`
`-for(\$a=0;\$a<100;\$a++)`
`-{`
`-    \$graph = generate_random_graph(\$num_nodes, 35, \$random_context);`
`-    write_graph_to_file("test_graph.".\$a.".txt", \$num_nodes, \$graph);`
`-}`

# File t2/graphs_equal/index.html

`-<html>`
`-<head>`
`-<title>Program to check if two graphs have the same topology</title>`
`-</head>`
`-<body bgcolor="#FFFFFF">`
`-<h1>Program to check if two graphs have the same topology</h1>`
`-`
`-<p>`
`-<a href="GraphIso.pm">GraphIso.pm</a> - This is the main module with the`
`-function that does the comparison.`
`-</p>`
`-`
`-<p>`
`-<a href="Graphs_Equal.pl">Graphs_Equal.pl</a> - a test program that uses`
`-the GraphIso module and runs on several test graphs. They can be generated`
`-by gen_graphs.pl below.`
`-</p>`
`-`
`-<p>`
`-<a href="gen_graphs.pl">gen_graphs.pl</a> - This is the script that`
`-generates some sample graphs for input to the program. It does so in a`
`-platform-independant way.`
`-</p>`
`-`
`-<p>`
`-<a href="test.pl">test.pl</a> - This script runs Graphs_Equal.pl and`
`-gen_graphs.pl consecutively for a series of seeds. To run it type `
`-"echo [initial seed] > seed.txt".`
`-</p>`
`-`
`-<p>`
`-<a href="gen_graphs.c">gen_graphs.c</a> - Same as gen_graphs.pl only in C,`
`-which makes it much faster. I have no intentions on porting the main code to`
`-C until I find that the algorithm is valid.`
`-</p>`
`-`
`-<p>`
`-<a href="Docs/Description.txt">Description.txt</a> - a description of the`
`-algorithm in English, in case the comments and the code are not enough.`
`-Also, some complexity analysis and notes.`
`-</p>`
`-`
`-<div align="right">`
`-<a href="../"><img src="../images/bk2hp.gif" alt="Back to my homepage" border="0"></a>`
`-</div>`
`-`
`-`
`-</body>`

# File t2/graphs_equal/index2.html

`-<html>`
`-<head>`
`-<title>Program to check if two graphs have the same topology</title>`
`-</head>`
`-<body bgcolor="#FFFFFF">`
`-<h1>Program to check if two graphs have the same topology</h1>`
`-`
`-<p>`
`-<a href="GraphIso.pm">GraphIso.pm</a> - This is the main module with the`
`-function that does the comparison.`
`-</p>`
`-`
`-<p>`
`-<a href="Graphs_Equal.pl">Graphs_Equal.pl</a> - a test program that uses`
`-the GraphIso module and runs on several test graphs. They can be generated`
`-by gen_graphs.pl below.`
`-</p>`
`-`
`-<p>`
`-<a href="gen_graphs.pl">gen_graphs.pl</a> - This is the script that`
`-generates some sample graphs for input to the program. It does so in a`
`-platform-independant way.`
`-</p>`
`-`
`-<p>`
`-<a href="test.pl">test.pl</a> - This script runs Graphs_Equal.pl and`
`-gen_graphs.pl consecutively for a series of seeds. To run it type `
`-"echo [initial seed] > seed.txt".`
`-</p>`
`-`
`-<div align="right">`
`-<a href="../"><img src="../images/bk2hp.gif" alt="Back to my homepage" border="0"></a>`
`-</div>`
`-`
`-`
`-</body>`

`-1011`

# File t2/graphs_equal/test.pl

`-#!/usr/bin/perl`
`-`
`-open I, "<seed.txt";`
`-\$seed = <I>;`
`-chomp(\$seed);`
`-close(I);`
`-`
`-for(;;\$seed++)`
`-{`
`-    open O, ">seed.txt";`
`-    print O \$seed, "\n";`
`-    close (O);`
`-`
`-    system("perl gen_graphs.pl \$seed");`
`-    if (system("perl Graphs_Equal.pl") == 5)`
`-    {`
`-        exit(5);`
`-    }`
`-}`

# File t2/graphs_equal/test_graph1.txt

`-6`
`-0 -> 1`
`-0 -> 2`
`-1 -> 2`
`-0 -> 3`
`-2 -> 4`
`-4 -> 5`

# File t2/graphs_equal/test_graph1_vis.txt

`-     1 `
`-   /   \`
`-`
`-0     -  2  - 4 - 5`
`-`
`-`
`-   \`
`-       `
`-      3`

# File t2/graphs_equal/tg0.txt

`-6`
`-0 -> 1`
`-1 -> 2`
`-2 -> 3`
`-3 -> 4`
`-4 -> 5`
`-5 -> 0`

# File t2/graphs_equal/tg1.txt

`-6`
`-0 -> 1`
`-1 -> 2`
`-2 -> 0`
`-3 -> 4`
`-4 -> 5`
`-5 -> 3`

# File t2/graphs_equal/tg2.txt

`-9`
`-0 -> 1`
`-1 -> 2`
`-2 -> 3`
`-3 -> 4`
`-4 -> 5`
`-5 -> 0`
`-6 -> 7`
`-7 -> 8`
`-8 -> 6`

# File t2/graphs_equal/tg3.txt

`-10`
`-0 -> 1`
`-1 -> 2`
`-2 -> 3`
`-3 -> 4`
`-4 -> 5`
`-5 -> 0`
`-6 -> 7`
`-7 -> 8`
`-8 -> 6`
`-0 -> 9`
`-1 -> 9`
`-2 -> 9`
`-3 -> 9`
`-4 -> 9`
`-5 -> 9`
`-6 -> 9`
`-7 -> 9`
`-8 -> 9`

`-26`
`-0 1`
`-1 2`
`-2 3`
`-3 4`
`-4 5`
`-5 0`
`-6 7`
`-7 8`
`-8 9`
`-9 10`
`-10 11`
`-11 6`
`-12 0`
`-12 1`
`-12 2`
`-12 3`
`-12 4`
`-12 5`
`-12 6`
`-12 7`
`-12 8`
`-12 9`
`-12 10`
`-12 11`
`-13 14`
`-14 15`
`-15 16`
`-16 17`
`-17 18`
`-18 13`
`-19 20`
`-20 21`
`-21 19`
`-22 23`
`-23 24`
`-24 22`
`-25 13`
`-25 14`
`-25 15`
`-25 16`
`-25 17`
`-25 18`
`-25 19`
`-25 20`
`-25 21`
`-25 22`
`-25 23`
`-25 24`
`-`
`-`
`-`