Changeset 7528:f45713981d79

Timestamp:

12/02/07 17:50:47 (6 years ago)

Author:

R. L. Miller <rlmillster@…>

Branch:

default

Tags:

2.8.15.rc0

Message:

generate trees, fix bugs

Location:

sage/graphs

Files:

• graph.py (modified) (3 diffs)
• graph_generators.py (modified) (15 diffs)

sage/graphs/graph.py

@@ -312 +312 @@
         # inputs must be (di)graphs:
         if not isinstance(other, GenericGraph):
-            raise TypeError("Input (%s) must be a graph."%str(other))
+            raise TypeError("Cannot compare graph to non-graph (%s)."%str(other))
         # DiGraphs are "larger" than Graphs:
         g1_is_graph = isinstance(self, Graph)
@@ -4939 +4939 @@
 
         """
+        if self.order() == 0:
+            return True
         import networkx
         return networkx.component.is_connected(self._nxg)
@@ -6636 +6638 @@
 
         """
+        if self.order() == 0:
+            return True
         import networkx
         return networkx.component.is_connected(self._nxg.to_undirected())

sage/graphs/graph_generators.py

@@ -2662 +2662 @@
 
 ################################################################################
-#   Graphs that are representatives of distinct isomorphism classes
+#   Graph Iterators
 ################################################################################
     
@@ -2696 +2696 @@
             sage: for G in graphs(3, augment='vertices'):
             ...    print G
-            ...
             Graph on 0 vertices
             Graph on 1 vertex
@@ -2709 +2708 @@
             sage: for G in graphs(3):
             ...    print G
-            ...
             Graph on 3 vertices
             Graph on 3 vertices
@@ -2718 +2716 @@
             sage: L = list(graphs(5, lambda G: G.size() <= 4))
             sage: len(L)
-            13
+            14
             sage: graphs_list.show_graphs(L)    # long time
         
@@ -2735 +2733 @@
             sage: L = list( graphs(8, lambda G: G.is_bipartite()) )
             sage: len(L)
-            38
-        
+            142
+        
+        Sloane A000088:
+            sage: for i in range(0, 7):
+            ...    print len(list(graphs(i)))
+            1
+            1
+            2
+            4
+            11
+            34
+            156
+
         REFERENCE:
             Brendan D. McKay, Isomorph-Free Exhaustive generation. Journal of
@@ -2758 +2767 @@
         else:
             raise NotImplementedError()
+
+    def trees(self, vertices, augment='edges'):
+        """
+        Accesses the generator of trees (graphs without cycles). Iterates over
+        distinct, exhaustive representatives.
+
+        INPUT:
+            vertices -- natural number
+            augment -- choices:
+                'vertices' -- augments by adding a vertex, and edges incident
+                    to that vertex.
+                    In this case, all trees on up to n=vertices are generated.
+                'edges' -- augments a fixed number of vertices by adding one edge
+                    In this case, all trees on exactly n=vertices are generated.
+
+        EXAMPLES:
+        Sloane A000055:
+            sage: for i in range(0, 10):
+            ...    print len(list(graphs.trees(i)))
+            1
+            1
+            1
+            1
+            2
+            3
+            6
+            11
+            23
+            47
+
+        """
+        is_tree = lambda g: g.transitive_reduction() == g
+        for g in self(vertices=vertices, property=is_tree, augment=augment):
+            if g.is_connected():
+                yield g
 
 def canaug_traverse_vert(g, aut_gens, max_verts, property):
@@ -2846 +2890 @@
             z = g.copy()
             z.add_vertex(n)
-            
+            if not property(z):
+                continue
             index = 0
             while (1 << index) <= i:
@@ -2935 +2980 @@
         sage: L = list(graphs(5, lambda G: G.size() <= 4))
         sage: len(L)
-        13
+        14
         sage: graphs_list.show_graphs(L)              # long time
     
@@ -2941 +2986 @@
         sage: L = list( graphs(7, lambda G: G.is_bipartite()) )
         sage: len(L)
-        23    
+        29
 
     """
@@ -2952 +2997 @@
     n_choose_2 = (n*(n-1))>>1 # >> 1 is just / 2
     if g.size() < n_choose_2:
-        
         # build a list representing C(g) - the edge to be added
         # is one of n*(n-1)/2 choices
@@ -2960 +3004 @@
         # union-find C(g) under Aut(g)
         for gen in aut_gens:
-            for i in xrange(n):
-                for j in xrange(i): # i > j
-                    if children[i][j] == (i,j):
-                        y, x = sorted([gen[i], gen[j]])
+            for iii in xrange(n):
+                for jjj in xrange(iii): # iii > jjj
+                    i, j = iii, jjj
+                    y, x = sorted([gen[i], gen[j]])
+                    if children[i][j] != children[x][y]:
+                        x_val, y_val = x, y
+                        i_val, j_val = i, j
+                        while (x_val, y_val) != children[x_val][y_val]:
+                            y_val, x_val = sorted(children[x_val][y_val])
+                        while (i_val, j_val) != children[i_val][j_val]:
+                            j_val, i_val = sorted(children[i_val][j_val])
+                        while (x, y) != (x_val, y_val):
+                            xx, yy = x, y
+                            x, y = children[x][y]
+                            children[xx][yy] = (x_val, y_val)
+                        while (i, j) != (i_val, j_val):
+                            ii, jj = i, j
+                            i, j = children[i][j]
+                            children[ii][jj] = (i_val, j_val)
                         if x < i:
                             children[i][j] = (x, y)
@@ -2978 +3037 @@
         # find representatives of orbits of C(g)
         roots = []
-        found_roots = 0
-        i = 0; j = 1
-        while found_roots < num_roots:
-            if children[j][i] == (j, i):
-                found_roots += 1
-                roots.append((i, j))
-            if j < n - 1:
-                j += 1
-            elif i < j: # j == n-1
-                i += 1
-                j = i + 1
-        
+        for i in range(n):
+            for j in range(i):
+                if children[i][j] == (i, j):
+                    roots.append((i,j))
         for i, j in roots:
             if g.has_edge(i, j):
@@ -2996 +3047 @@
             z = g.copy()
             z.add_edge(i, j)
-
+            if not property(z):
+                continue
             z_aut_gens, _, canonical_relabeling = search_tree(z, [z.vertices()], certify=True)
             relabel_inverse = [0]*n
-            for i in xrange(n):
-                relabel_inverse[canonical_relabeling[i]] = i
+            for ii in xrange(n):
+                relabel_inverse[canonical_relabeling[ii]] = ii
             z_can = z.relabel(canonical_relabeling, inplace=False)
             cut_edge_can = z_can.edges(labels=False, sort=True)[-1]
@@ -3008 +3060 @@
             m_z = z.copy()
             m_z.delete_edge(cut_edge)
-
             if m_z == g:
                 for a in canaug_traverse_edge(z, z_aut_gens, property):
@@ -3045 +3096 @@
         for gen in aut_gens:
             new_perm = copy(perm)
-            for i in xrange(n):
-                new_perm[i] = gen[perm[i]]
+            for ii in xrange(n):
+                new_perm[ii] = gen[perm[ii]]
             if new_perm not in seen_perms:
                 seen_perms.append(new_perm)