Ask Your Question

Graph theory for symbolic electrical circuit analysis?

asked 2016-04-03 14:21:14 -0500

John Paul Morrison gravatar image

Looking for how to go from graph theory directly to solve circuit/nodal analysis. This link has been helpful: (have to google graphsandckts.pdf because I can't post the link) but I seem to be getting lost in the graph theory part. Circuit analysis software like SPICE must do something like this numerically.

I can build a directed graph in Sagemath by adding vertices/edges.

Sagemath will return the incidence matrix. Or you can enter the incidence matrix directly but for something like a circuit netlist it can be a lot easier to enter nodes, ie. vertices of the graph.

Resistances/impedances go into a diagonal matrix R, known voltages/currents go into a vector.

I'm not clear on finding the spanning tree/re-arranging the incidence matrix. Seems like this should be some standard graph theory or linear algebra functions. You eliminate one row/column and should have a matrix A =[ At I ] where At = edges in the graph spanning tree and I = n x n identity matrix.

The rest should be basic linear algebra: transpose, inverse, multiplying it out

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2016-06-01 08:44:49 -0500

JEFLSU gravatar image

updated 2016-06-01 08:50:38 -0500

It looks like you want a matroid here. Using the examples from the paper you mention:

sage: M=Matrix([[0,-1,-1,1,0,0,0,0],[0,0,0,-1,1,1,0,0],[-1,0,1,0,-1,0,-1,0],[1,0,0,0,0,0,0,-1],[0,1,0,0,0,-1,1,1]])
sage: G=DiGraph(M)
sage: mat=Matroid(M)
sage: print mat.representation(reduced=True,labels=True)
([ 0  0  0 -1],[ 0 -1  1  1],[-1  0 -1 -1],[-1 -1  0  0], [0, 1, 2, 3], [4, 5, 6, 7])

The columns of M are of course the edges of the DiGraph G. My output says edges 0,1,2, and 3 are edges of a spanning tree (a basis $B$ of the matroid) and the reduced representation it returns has nonzero entries for the basis elements of the $B$-fundamental circuit for that element. For example, the $B$-fundamental circuit of $4$, the unique undirected cycle among the edges of G contained in $B$ union {4} is {2,3,4}. (Forgive the lack of typesetting; my browser's acting up right now). Note that the standard reduced representation of M is [I | D], where D is the matrix output of the command .representation(reduced=True).

You can tell Sage what basis (collection of edges of a spanning tree) you want to use, which it sounds like you might want. Of course, once you have a matroid, you can have Sage tell you all the bases.

You can get a good feel for what's going on here in the documentation for linear (just means they're representable over some finite field, that is, they have a matrix representation) matroids:

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2016-04-03 14:21:14 -0500

Seen: 704 times

Last updated: Jun 01 '16