summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-07-14 16:38:34 -0500
committerTara Fife <fi.tara@gmail.com>2016-07-14 16:38:34 -0500
commit5ac863773f4a0582d1db0dc753035131db371979 (patch)
treef4272cf3b754b07fbb18b7dca22f4b2057fdfb04
parentAdded documentation fixed errors (diff)
Updated merge functions
-rw-r--r--src/sage/matroids/cunningham_edmonds_decomposition.pxd5
-rw-r--r--src/sage/matroids/cunningham_edmonds_decomposition.pyx138
2 files changed, 118 insertions, 25 deletions
diff --git a/src/sage/matroids/cunningham_edmonds_decomposition.pxd b/src/sage/matroids/cunningham_edmonds_decomposition.pxd
index 0fa71a5..30a3bcb 100644
--- a/src/sage/matroids/cunningham_edmonds_decomposition.pxd
+++ b/src/sage/matroids/cunningham_edmonds_decomposition.pxd
@@ -16,6 +16,7 @@ cdef class Node(sage.structure.sage_object.SageObject):
# def __init__(self, G, pm, int f):
cpdef get_graph(self)
cpdef get_parent_marker(self) # Took out int so it could be called outside from terminal.
+ cpdef get_named_edge(self, f)
cpdef get_parent_marker_edge(self)
cpdef get_f(self) # Took out int so it could be called outside from terminal.
cpdef set_f(self, int n)
@@ -48,11 +49,11 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
cpdef __update(self, P, C)
cpdef __is_graphic(self)
cpdef merge_with_parent(self, N, N_vertex=*, P_vertex=*)
- cpdef merge_branch(self, N)
+ cpdef merge_branch(self, N, P)
cpdef __add_cycle(self, cycle)
cpdef get_arborescence(self)
cpdef get_nodes(self)
cpdef get_root(self)
cpdef __get_pi(self)
cpdef branch(self, N)
- cdef get_parent(self, N) \ No newline at end of file
+ cpdef get_parent(self, N) \ No newline at end of file
diff --git a/src/sage/matroids/cunningham_edmonds_decomposition.pyx b/src/sage/matroids/cunningham_edmonds_decomposition.pyx
index 5ddd44a..33303e0 100644
--- a/src/sage/matroids/cunningham_edmonds_decomposition.pyx
+++ b/src/sage/matroids/cunningham_edmonds_decomposition.pyx
@@ -306,6 +306,22 @@ cdef class Node(sage.structure.sage_object.SageObject):
return e
+ cpdef get_named_edge(self, f):
+ 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.get_named_edge(4)
+ (1, 2, 4)
+ """
+ for e in self.graph.edges():
+ if e[2] == f:
+ return e
+ return (-1, -1, -1)
+
+
cpdef get_f(self):
r"""
EXAMPLES:
@@ -701,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 = next_vertex
- self.next_edge = next_edge
+ self.next_vertex = self.next_vertex
+ self.next_edge = self.next_edge
self.K_1 = K_1
self.K_2 = K_2
self.u_1 = u_1
@@ -1232,10 +1248,10 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
cpdef merge_with_parent(self, N, N_vertex=-1, P_vertex=-1):
- G_N = self.nodes[N].graph
+ G_N = self.nodes[N].get_graph()
m = self.nodes[N].get_parent_marker_edge()
P = self.get_parent(N)
- G_P = self.nodes[P].graph
+ G_P = self.nodes[P].get_graph()
for e in G_P.edges():
if m[2] == e[2]: # If the lables are the same.
@@ -1243,34 +1259,110 @@ cdef class CunninghamEdmondsDecomposition(sage.structure.sage_object.SageObject)
G = G_N.union(G_P)
if N_vertex == -1:
- u = f[0] # Which vertices we are merging with which makes no difference.
- v = f[1]
- x = m[0]
- y = m[1]
+ u = m[0] # Which vertices we are merging with which makes no difference.
+ v = m[1]
+ x = f[0]
+ y = f[1]
else:
u = N_vertex
- v = {f[0], f[1]}.difference({N_vertex})
+ v = ({m[0], m[1]}.difference({N_vertex})).pop()
x = P_vertex
- y = {f[0], f[1]}.difference({P_vertex})
- G.merge_vertices(u,x) # The order of the vertices determines the name of the resulting vertex.
- G.merge_vertices(v,y)
+ y = ({f[0], f[1]}.difference({P_vertex})).pop()
+
+ G.merge_vertices([x, u]) # The order of the vertices determines the name of the resulting vertex.
+ G.merge_vertices([y, v])
- self.arborescence.merge_vertices(P, N)
- return Node(G, P.parent_marker, P.get(f))
+ return Node(G, self.nodes[P].get_parent_marker(), self.nodes[P].get_f())
return None
- cpdef merge_branch(self, N):
- root = self.root
+ cpdef merge_branch(self, N, P):
+ r'''
+
+ INPUT:
+
+ - ``N`` -- a Node
+ - ``P`` -- a set of edges
+
+ OUTPUT:
+
+ - A Node, with parent marker and orientation equal to ``N``'s and whose graph is a merge of the graphs in the brance starting at ``N`` such that the intersection of ``P`` with this graph is a path if possible
+
+ EXAMPLES:
+ sage: from sage.matroids.cunningham_edmonds_decomposition import *
+ sa