1

For a discrete element modelling project I have recently started looking into the graph representation of a collection of particles in contact. The basic idea is this: I have a granular aggregate consisting of a number of particles. Each particle interacts with its neighbours through contact points, which can be represented as edges connecting the particles (nodes). The objective is then to extract the cycle basis, i.e. the set of smallest possible cycles from which larger cycles can be constructed. To this end, I construct a graph using the Python networkx package, and then extract the cycle basis using the networkx.cycle_basis function. A simple example pseudo-code to illustrate my procedure:

import networkx as nx

nodes = [particle IDs]
edges = [pairs of particle IDs]
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)
cycles = nx.cycle_basis(G)

cycles represents a list of lists of the particle IDs participating in each basis cycle. However, when I plot the graph (using the coordinates of the particles in the simulation), I see that cycles contains a number of cycles that are actually a combination of smaller cycles, and are therefore not basis cycles (if I understood correctly). An example is shown below:

enter image description here

Here, the black lines connecting the particles represent the edges in the graph, and the red cycle is one contained in cycles (which is clearly not a basis cycle). In addition, there are occasional duplicates present in the set.

My question: why does networkx.cycle_basis display this behaviour? Is this expected and is my understanding of the cycle basis wrong, or is the output wrong? And is there any way to remove these non-basis cycles?

MPA
  • 1,878
  • 2
  • 26
  • 51
  • 1
    Can you explain why the red cycle cannot be a basis cycle? I believe the definition of a basis here is that any other cycle can be written as a sum of cycles in the basis, and "minimal" means that the basis has a few cycles in it as possible, rather than that the cycles in the basis are as small as possible. – Joel Apr 25 '19 at 09:55
  • @Joel The red cycle contains 6 black cycles: 1 pentagon (top left), 1 heptagon (middle), and 4 triangles (bottom right). The red cycle can be constructed by joining these 6 black cycles. Or am I seeing this the wrong way? – MPA Apr 25 '19 at 10:00
  • 1
    I think what @Joel, ever the diplomat, is trying to say is that the cycle may be a perfectly valid example of a cycle in a cycle basis, and your intuition for a cycle basis is incorrect. A cycle basis is a list of cycles from which all other cycles can be reconstructed. There is absolutely no guarantee that the basis cycles will be small. – Paul Brodersen Apr 25 '19 at 10:00
  • Finding the "holes" in a graph is actually pretty non-trivial. Another user and I have discussed one approach / heuristic [here](https://stackoverflow.com/questions/43633840/detect-rings-circuits-of-connected-voxels). – Paul Brodersen Apr 25 '19 at 10:01
  • Actually, since your graph is planar, it might be a lot easier than in the example I linked above. So take my previous comment with a grain of salt. – Paul Brodersen Apr 25 '19 at 10:04
  • @PaulBrodersen - And I was editing my comment, so an earlier version suggested it couldn't be written as a sum, but then I saw in the documentation that the summation was "exclusive or". So MPA was likely responding to my incorrect comment version. – Joel Apr 25 '19 at 10:04
  • @PaulBrodersen Thanks for your comments. Does the intersection of two cycles in the cycle basis count as a valid way to construct non-basis cycles? So if I have two large basis cycles, I could obtain smaller cycles by taking their intersection? – MPA Apr 25 '19 at 10:06
  • @ Joel Yes I was replying to your original comment. What does "exclusive or" imply? – MPA Apr 25 '19 at 10:07
  • "exclusive or" means that when we "add" two cycles `A` and `B`, we get a new cycle whose edges are those edges in one of `A` or `B`, but not in both. So the cycle sum you describe doesn't include edges that are in multiple of the smaller cycles. – Joel Apr 25 '19 at 10:09
  • A union of two cycles in the cycle basis should contain 2 cycles if they don't share a node or an edge and three (or more) cycles if they do. The symmetric difference between two cycles should give you another cycle. – Paul Brodersen Apr 25 '19 at 10:10
  • Am I correct that the cycles you want to find are those cycles which can't be broken into smaller cycles? – Joel Apr 25 '19 at 10:10
  • @PaulBrodersen Apologies, I meant intersection, not union – MPA Apr 25 '19 at 10:10
  • @Joel Correct, I want the smallest possible ("elementary") polygons in the graph – MPA Apr 25 '19 at 10:11
  • @MPA The intersection between two basis cycles is not guaranteed to give you another cycle. I think it might even be guaranteed to not give a cycle. The symmetric difference is the union - intersection, which is what you need to construct the other cycles from the basis. – Paul Brodersen Apr 25 '19 at 10:15
  • I am not sure that I would use the cycle basis as my starting point. Too many combinations to try. I would do the following: For each node, 1) determine its neighbours, 2) induce a subgraph with all nodes except that node, 3) find the shortest path between all combinations of neighbours, 4) exclude paths between two neighbours if they contain a third neighbour, 5) add the original node back to close the paths to make cycles. 6) Determine the set of all cycles discovered in this way. – Paul Brodersen Apr 25 '19 at 10:36
  • @PaulBrodersen I have tried to follow your instructions, but I can't wrap my head around it. In 2): should the subgraph be induced for only the neighbours? Or all particle minus 1 node?. In 4): with third neighbour, do you mean a node that is not connected to the original node? It would be most helpful if you could provide a (pseudo-)code snippet or an illustration – MPA Apr 25 '19 at 13:31
  • This may help: https://stackoverflow.com/questions/838076/small-cycle-finding-in-a-planar-graph – Joel Apr 25 '19 at 18:39
  • Regarding 2): all particles minus 1 node; regarding 4): nope, I mean another neighbour from the set of neighbours that we detemined in 1). If you post or link to some example data, I will try to make an implementation tonight or tomorrow (pretty busy atm, sorry). – Paul Brodersen Apr 29 '19 at 11:44

0 Answers0