1

I have to get list of all meshes (windows/loops/elementary circuits, shortest cycles that together cover all edges of graph and no one contains other cycles) in unweighted graph representing electrical circuit for mesh analysis of that circuit (I can assume it's a planar graph). The graph (represented as tuples (A,B,R) meaning two vertices and resistance of edge) is loaded from file.

I'm using Python with NetworkX library, but it's cycle_basis function doesn't return meshes (they are apparently not the same as cycle basis). The graph is undirected, so I can't use simple_cycles function. I tried to modify BFS for this task, but I couldn't guarantee that no cycle is contained in other cycle.

I probably need something like this: Algorithm for finding minimal cycles in a graph, but this question doesn't have any proof for algorithm in last comment, and I hope the answer to my problem is simpler than "implement Horton's algorithm".

qalis
  • 1,314
  • 1
  • 16
  • 44
  • You say you can assume that the graph is planar. Do you already have a planar embedding? It can make the job easier. – Matt Timmermans Mar 23 '19 at 16:37
  • @MattTimmermans if you mean planar drawing then no, I didn't see any use in plotting graph in such a way (though I could, of course). I wanted to analyze graph and get meshes from numerical data alone. – qalis Mar 23 '19 at 16:59

1 Answers1

1

The thing you need for mesh analysis is a list of the enclosed areas in any particular planar drawing of the graph.

It's much easier to find than a minimal cycle basis, but which list you get depends on which planar drawing you use.

If you have a planar drawing, and can get each vertex's neighbors in clockwise or counter-clockwise order, then it is very easy just to trace around these enclose areas.

Otherwise, you could do something like:

  1. Generate a spanning tree
  2. For every edge that's not in the tree, make a loop containing only that edge, plus edges that are in the spanning tree.

Since every loop contains one edge that is not in any other loop, it is guaranteed that no loop is contained in any other... depending on what you mean by "contained". The important point is that those loops will work for the analysis as long as you're careful about any current sources. Maybe you want to avoid them in the spanning tree.

Since you will be using these loops to generate a system of equations to solve, in which each edge is a variable, there is probably no advantage in using a more complicated algorithm to find "smaller" loops.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87