Revision history [back]

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\cup \left{ 4 \right}$ is $\left{ 2,3,4 \right}$. 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: http://combinat.sagemath.org/doc/reference/matroids/sage/matroids/linear_matroid.html

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\cup $B \cup \left{ 4 \right}$ is $\left{ 2,3,4 \right}$. 2,3,4\right}$. (I'm not sure if the sets are 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: http://combinat.sagemath.org/doc/reference/matroids/sage/matroids/linear_matroid.html

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 \cup \left{ 4 \right}$ $B$ union {4} is $\left{ 2,3,4\right}$. (I'm not sure if the sets are {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: http://combinat.sagemath.org/doc/reference/matroids/sage/matroids/linear_matroid.html