Search code examples
pythongraphsage

How can I find an SPQR tree using Sage?


I am trying to find SPQR tree of my graph, so I find out that sage can help me. I put my code here https://sagecell.sagemath.org/ (and than in sage programe). Here it is:

H=Graph({"AL":["GR","ME","MK","RS"],"GR":["BG","MK","TR"],"ME":["BA","HR","KO","RS"],"MK":["BG","RS"],"RS":["BA","BG","HR","HU","KO","RO"],"AD":["FR","SP"],"FR":["BE","DE","IT","LU","MC","SP","CH"],"SP":["PT"],"AT":["CZ","DE","HU","IT","LI","SK","SL","CH"],"CZ":["DE","PL","SK"],"DE":["BE","DK","LU","NL","PL","CH"],"HU":["HR","SK","SL","UA"],"IT":["SM","SL","CH","VA"],"LI":["CH"],"SK":["PL","UA"],"SL":["HR"],"BY":["LV","LT","PL","RU","UA"],"LV":["EE","LT","RU"],"LT":["PL","RU"],"PL":["RU","UA"],"RU":["EE","FI","NO","UA"],"UA":["MD","RO"],"BE":["LU","NL"],"BA":["HR"],"BG":["RO","TR"],"RO":["MD"],"FI":["NO","SE"],"NO":["SE"]}
)
H = H.to_undirected()
tree = spqr_tree(H)
plot(tree)

But I got exception and I can't understand, what the problem with my graph and how can I fix it. Log from sage:

ValueError                                Traceback (most recent call last)
<ipython-input-1-5545fd16ab3f> in <module>
      3 )
      4 H = H.to_undirected()
----> 5 tree = spqr_tree(H)
      6 
      7 plot(tree)

/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/graphs/connectivity.pyx in sage.graphs.connectivity.spqr_tree (build/cythonized/sage/graphs/connectivity.c:23494)()
   2318 
   2319     if algorithm == "Hopcroft_Tarjan":
-> 2320         tric = TriconnectivitySPQR(G)
   2321         return tric.get_spqr_tree()
   2322 

/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/graphs/connectivity.pyx in sage.graphs.connectivity.TriconnectivitySPQR.__init__ (build/cythonized/sage/graphs/connectivity.c:30717)()
   3109             # If graph has a cut vertex
   3110             if cut_vertex != -1:
-> 3111                 raise ValueError("graph has a cut vertex")
   3112 
   3113         # Identify reversed edges to reflect the palm tree arcs and fronds

ValueError: graph has a cut vertex

Solution

  • An SPQR tree can only be formed for biconnected graphs. These are connected graphs that stay connected even if any node in the graph is deleted. A graph is not biconnected if it has an articulation vertex (also called a cut vertex), a node that, if removed, leaves the graph disconnected.

    The error you're getting indicates that your graph has at least one cut vertex, so it's not possible to form the SPQR tree.