kpetridis24 / networkx Goto Github PK

When checking for Feasibility of a candidate pair, take into consideration the cases of graph monomorphism, subgraph isomorphism and induced graph isomorphism

Use the dfs_edges by networkx and modify it accordingly so that it fits VF2++

All functions returning large structures should be handled with yield statements.

Add documentation including description and examples

Create benchmarks for all features and cases

Ordering crashes if G1 and G2 do not have the same labels. Should we just add a precheck to make sure that all labels in G1 are present in G2 or should we tackle this another way?

Create a class, to store the necessary information of each state of the algorithm, in a stack structure (LIFO)

Finalize every feature and combine them to form the algorithm.

This requires that the structure of the implementation is similar to the already existing isomorphism functions of networkx. Implement a GraphMatcher for VF2++, a VF2++ userfunc that initializes a VF2++ GraphMatcher object. Also create a new is_isomorphic function that will process the graphs based on VF2++ (already exists for VF2)

Create the class containing the most significant entities (like helper functions and the states). The implementation should be object-oriented.

The node ordering crashes when a node of the graph is not connected to any nodes. Figure out what the issue is.

The current implementation computes the neighbors at distance k, by re-evaluating the neighbors at distance k-1. Make sure that every level is only computed once.
see: "d_level_bfs_tree" function

So that the documentation appears on site

The current implementation of the node ordering only takes into consideration, the node degrees. The node labels should be included as well.

Note: Decide how will the labels be represented. For example, we could initialize the algorithm by gathering the labels of each node in a dictionary, which will be used by VF2++. This should be performed during the initialisation of the VF2++ GraphMatcher.

Discuss whether there should be a variable "with_labels" to indicate that we should take labels into consideration as well.

Practical analysis and experimentation indicates the superiority of VF2++ over VF2. Make sure the implementation verifies this.

Adjust VF2++ to handle MultiGraph

Part of the consistency check is being performed by the candidate selection. To pick candidates we take the intersections of neighborhoods in G2, of nodes _v which map back to covered neighbors _u of u (m[_u] = _v) and _u in G[u] and _v in G[v]. This is basically the consistency check.
@dschult

To force the program to test the consistency only we need to write unit tests without the labels (or assign the same labels). In the current unit tests, the labels are different, so when feasibility fails, it's always due to label inconsistencies, so we don't have a clear view on what happens in different cases of degree inconsistencies (this check is second in order).

Full implementation of the VF2++ preprocessing (node ordering) + testing.

Create benchmarking environment to compare the incremental Ti updating vs the brute force Ti computing

Create Unit Tests for every individual functionality

Update Ti/Ti_tilde instead of re-computing them in every function call. When the mapping is extended, just add the neighbors of the two new nodes that are not in the mapping.

Apply optimizations throughout the code. Look for:

• Redundant/repeated operations and iterations
• Things that might be checked by more than one functions (see candidates and feasibility)
• Use profiler IPython %prof to check memory usage

Adjust candidate selection so that it works for all cases including IND, SUB and MONO

The feasibility rules of the VF2++ should be implemented. These rules decide whether a pair of candidate nodes can establish a successful mapping.

Node ordering is only used for inserting and popping from the left end. It would be more efficient to use a deque.

Implement the selecting of candidate nodes, to be checked for feasibility.