cycle basis question

[Trevor Laughlin]

Hello,

I am trying to use NetworkX to determine the cycle basis of an undirected graph and I am having some issues. I'm not an expert in graph theory, but I believe the cycle basis will enable part of an aerospace analysis tool I am developing. I attached a small sample code to demonstrate the problem. I would expect the cycle basis to be a set of 3 and 4 sided cycles, but I get a few cycles with 7 and 9 edges. Am I misunderstanding the cycle_basis algorithm or can anyone spot an error in my code? I've purchased the paper referenced in the algorithm but haven't seen anything that may give me the results I describe. The end goal is to essentially identify all enclosed polygons where the edge will represent the edges of a surface.

Any help or direction would be greatly appreciated. Please let me know if you need any additional information.

Thanks,

Trevor

[Daniel Schult]

The short answer is that a cycle basis just means that you can obtain any cycle in the network by a linear combination of cycles in the cycle basis.  A linear combination of cycles essentially means adding (union of directed edges where opposite direction edges cancel each other) and taking multiples (multiplying by -1 changes direction of each edge, mult by 2 counts each edge twice, etc).

So, its not surprising that you get some cycles that are 7 or 9 edges. Most likely they can be subtracted to find smaller cycles. Or maybe a smaller one can be subtracted to give another smaller one.  There are many choices for basis!

Your desired outcome of identifying enclosed polygons and the edges around them presumes that the network has enclosed polygons and many/most networks don't (I think planar graphs do, but I haven't thought about it much).  Perhaps you should change the whole structure of the graph by making the polygons be "nodes" and connect them if they share an edge. Do it in a way that you can translate back to the original nodes/edges if you need to. But it might be that what you really want to track is the polygons anyway.

# untested--i think it creates the graph of polygons for the example you provided.

import networkx as nx

G=nx.grid_graph([4,4])    # nodes are 2-tuples with coordinates of the grid

G.add_edge(0,(0,0))       # your triangles could be called something more interesting--i just used 0 and 1

G.add_edge(1,(3,3))

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Trevor Laughlin]

Thanks Daniel. As I understand graph theory fundamentals more your explanation appears correct. The cycle basis does not guarantee my desired result. 

If I understand your suggestion correctly, the problem I have with making the polygons the nodes is that I don't know the polygons up front. In my analysis tool I am developing, I am essentially given a set of 3D lines (that are not necessarily planar) and I need to determine the polygons from there. So far I can intersect all the lines where the intersections points become the nodes of the graph, and each line connecting these points becomes an edge of the graph. I was hoping that once I built this connected/undirected graph, there would be a common graph theory algorithm to produce my desired result. 

I have a few ideas I might pursue (based on what I see in my head, not any actual graph theory...):

1) Use the cycle basis to produce a set of subgraphs, and check each subgraph to see if there are any internal edges/paths from the original graph. If so, continue to find the cycle basis of the subgraph and produce more subgraphs until the no internal edges/paths exist. I suppose this will end up being some sort of while loop process. Probably wildly inefficient but I'm just looking for something that is works, is robust, and is enough to show a proof-of-concept type program.

2) Convert my 3D lines to a planar graph. There seems to be some algorithms for finding enclosed polygons of a planar graph.

Thanks again for the tips.

[Trevor Laughlin]

Daniel,

I almost have a working algorithm using a combination of both options 1 and 2 above. Although, it seems that the NetworkX cycle_basis algorithm does not necessarily give the same cycle basis given the same graph. Sometimes I will run my test code and get the result I expected, but others times I will not (without doing anything except re-running the code). 

Any idea on why this is happening? Maybe because the cycle_basis algorithm uses sets and the objects are not ordered the same between executions?

Thanks,

Trevor

[Daniel Schult]

Trevor,

The order can change for Python dicts and sets. They both use hash systems to place the items in the data structure. NetworkX uses dicts in its graph data structure so the order of the nodes and edges is arbitrary. Also, the sets used in the algorithm provide arbitrary order too. 

But my understanding is that while the order is arbitrary, it is deterministic for a given machine architecture. So if you run the same code on the same machine using the same input it will give the same result. Are you sure that nothing changes between runs? If you add an edge and then remove it, the order can change. But if you leave it alone and it is the same data structure it will produce the same order. And if you add items to a set in the same order when constructing it, the order should be the same when reporting from it.

Dan

[Daniel Schult]

Ahhh... If your nodes do not have hash methods the system uses the memory location (id()) to put the entries into the hashtable in the set/dict. So from one run to the next you can get different orders because the memory locations of the objects you use as nodes change from run to run.   See http://stackoverflow.com/questions/3812429/is-pythons-set-stable

[Trevor Laughlin]

Thanks Daniel. I tweaked a few things in my algorithm so now no matter the path it takes to break down the cycles it eventually gets my desired result. My problem now is that the time complexity appears to be O(n^2). I've found another resource claiming their algorithm only requires O(mlog m), where m is the number of edges, so I'm going to implement that and see where that gets me. On a 10x10 grid (100 enclosed cycles), my algorithm takes about 20 seconds. My eventual application could be something on the order of 50x50 grid....so this would be an area where I might convert to C++/Fortran, no matter what algorithm I use.

Thanks for the help.

Trevor