summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-07-18 20:27:02 -0500
committerTara Fife <fi.tara@gmail.com>2016-07-18 20:27:02 -0500
commit89e59effa462cec6ebb937dae00d59e291bfd758 (patch)
treeb3c0350f2e3e85dafc48cd4777a8a181578b9c3f
parentUpdated merge functions (diff)
Implamented ``squeeze`` function.
Made minor changes to ``typing`` and ``init`` functions
-rw-r--r--src/sage/matroids/cunningham_edmonds_decomposition.pxd4
-rw-r--r--src/sage/matroids/cunningham_edmonds_decomposition.pyx176
2 files changed, 144 insertions, 36 deletions
diff --git a/src/sage/matroids/cunningham_edmonds_decomposition.pxd b/src/sage/matroids/cunningham_edmonds_decomposition.pxd
index 30a3bcb..49bd05d 100644
--- a/src/sage/matroids/cunningham_edmonds_decomposition.pxd
+++ b/src/sage/matroids/cunningham_edmonds_decomposition.pxd
@@ -23,7 +23,7 @@ cdef class Node(sage.structure.sage_object.SageObject):
cpdef is_polygon(self)
cpdef is_path(self, P)
cpdef is_cycle(self, P)
- cpdef typing(self, P)
+ cpdef T(self, P)
cpdef __relink1(self, Z=*, WQ=*)
cpdef __relink2(self, Z=*, WQ=*)
@@ -45,7 +45,7 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
cpdef __typing(self, P, pi)
cpdef __relink2(Q, Z=*, WQ=*)
cpdef __hypopath(self, P)
- # cpdef __squeeze(self, L)
+ cpdef __squeeze(self, N, L)
cpdef __update(self, P, C)
cpdef __is_graphic(self)
cpdef merge_with_parent(self, N, N_vertex=*, P_vertex=*)
diff --git a/src/sage/matroids/cunningham_edmonds_decomposition.pyx b/src/sage/matroids/cunningham_edmonds_decomposition.pyx
index 33303e0..ba779b1 100644
--- a/src/sage/matroids/cunningham_edmonds_decomposition.pyx
+++ b/src/sage/matroids/cunningham_edmonds_decomposition.pyx
@@ -101,15 +101,15 @@ cdef class Node(sage.structure.sage_object.SageObject):
False
sage: N.is_cycle({1, 2, 4, 6, 8})
True
- sage: N.typing({1, 4, 7, 11})
+ sage: N.T({1, 4, 7, 11})
1
- sage: N.typing({1, 2, 4, 7, 11})
+ sage: N.T({1, 2, 4, 7, 11})
2
- sage: N.typing({1, 4, 6})
+ sage: N.T({1, 4, 6})
3
- sage: N.typing({1, 4, 6, 12})
+ sage: N.T({1, 4, 6, 12})
4
- sage: N.typing({1, 2, 4, 8})
+ sage: N.T({1, 2, 4, 8})
5
@@ -433,22 +433,22 @@ cdef class Node(sage.structure.sage_object.SageObject):
return True
- cpdef typing(self, P):
+ cpdef T(self, P):
r"""
EXAMPLES:
sage: from sage.matroids.cunningham_edmonds_decomposition import *
sage: G= Graph([(0, 1, 1), (0, 4, 2), (0, 5, 3), (1, 2, 4), (1, 6, 5), (2, 3, 6), (2, 7, 7), (3, 4, 8), (3, 8, 9), (4, 9, 10), (5, 7, 11), (5, 8, 12), (6, 8, 13), (6, 9, 14), (7, 9, 15)], multiedges=True)
sage: N = Node(G, 3)
- sage: N.typing({1, 4, 7, 11})
+ sage: N.T({1, 4, 7, 11})
1
- sage: N.typing({1, 2, 4, 7, 11})
+ sage: N.T({1, 2, 4, 7, 11})
2
- sage: N.typing({1, 4, 6})
+ sage: N.T({1, 4, 6})
3
- sage: N.typing({1, 4, 6, 12})
+ sage: N.T({1, 4, 6, 12})
4
- sage: N.typing({1, 2, 4, 8})
+ sage: N.T({1, 2, 4, 8})
5
"""
C = set(P) | {self.get_parent_marker()}
@@ -683,7 +683,7 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
# NECESSARY
# We are assuming that if ``T`` is specified, then so are ``nodes``, ``next_edge``, and ``next_vertex``.
- def __init__(self, T=None, nodes = None, int next_edge=0, next_vertex=None, K_1=-1, K_2=-1, u_1=-1, u_2=-1):
+ def __init__(self, T=None, nodes = None, int next_edge=0, next_vertex=0, K_1=-1, K_2=-1, u_1=-1, u_2=-1):
"""
Initialization of the decomposition.
@@ -717,8 +717,8 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
self.root = self.arborescence.sources()[0] # This should work, because our ``arborescence`` should only have one source. We might want to check for that.
self.next_arborescence_vertex = T.order()
- self.next_vertex = self.next_vertex
- self.next_edge = self.next_edge
+ self.next_vertex = next_vertex
+ self.next_edge = next_edge
self.K_1 = K_1
self.K_2 = K_2
self.u_1 = u_1
@@ -788,12 +788,7 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
sage: from sage.matroids.cunningham_edmonds_decomposition import *
sage: D = CunninghamEdmondsDecomposition(next_edge=17)
sage: Dp = D.__hypopath(set([17]))
- sage: Dp.get_arborescence()
- Digraph on 1 vertex
- sage: Dp.get_nodes()[0].get_graph()
- Multi-graph on 2 vertices
- sage: Dp.get_nodes()[0].get_graph().edges()
- [(0, 1, 0), (0, 1, 17)]
+
"""
D_hat = self
for v in self.arborescence.vertices():
@@ -813,7 +808,7 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
for H in pi(s):
if D_hat.nodes[H].is_polygon():
D_hat.nodes[H].__relink1(P)
- if D_hat.nodes[H].typing == 5:
+ if D_hat.merge(H, P).T == 5:
return False
i = s - 1
#T2
@@ -852,7 +847,7 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
# If `T(H_i) = 1` for all `i` and `T(H) = 2` or 3, either set `K_1 = Q`,
# if ``Q`` hasn't already been assigned, or set `K_2 = Q`.
if len(num