Changeset 5711:28acd710c7ab


Ignore:
Timestamp:
08/12/07 13:28:37 (6 years ago)
Author:
Robert Miller <rlmillster@…>
Branch:
default
Parents:
5707:a93a85420d94 (diff), 5710:20c50f991598 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

local merge

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • sage/graphs/graph.py

    r5704 r5711  
    2424    -- Emily Kirkman (2007-07-21): Genus (including circular planar, all 
    2525        embeddings and all planar embeddings), all paths, interior paths 
     26    -- Bobby Moretti (2007-08-12): fixed up plotting of graphs with 
     27       edge colors differentiated by label 
    2628 
    2729TUTORIAL: 
    … …  
    21652167 
    21662168    ### Visualization 
     2169    def _color_by_label(self, format='hex'): 
     2170        """ 
     2171        Logic for coloring by label (factored out from plot() for use 
     2172        in 3d plots, etc) 
     2173        """ 
     2174        from sage.plot.plot import rainbow 
     2175        edge_labels = [] 
     2176        if self.is_directed(): 
     2177            iterator = self.arc_iterator 
     2178        else: 
     2179            iterator = self.edge_iterator 
     2180        for e in iterator(): 
     2181            i = 0 
     2182            while i < len(edge_labels): 
     2183                if not edge_labels[i][0][2] == e[2]: 
     2184                    i += 1 
     2185                else: 
     2186                    edge_labels[i].append(e) 
     2187                    break 
     2188            if i == len(edge_labels): 
     2189                edge_labels.append([e]) 
     2190        num_labels = len(edge_labels) 
     2191        r = rainbow(num_labels, format=format) 
     2192        edge_colors = {} 
     2193        for i in range(num_labels): 
     2194            edge_colors[r[i]] = edge_labels[i] 
     2195        return edge_colors      
    21672196 
    21682197    def plot(self, pos=None, layout=None, vertex_labels=True, 
    … …  
    22452274 
    22462275        """ 
    2247         from sage.plot.plot import networkx_plot, rainbow 
     2276        from sage.plot.plot import networkx_plot 
    22482277        import networkx 
    22492278        if vertex_colors is None: 
    … …  
    22972326 
    22982327        if color_by_label: 
    2299             edge_labels = [] 
    2300             if self.is_directed(): 
    2301                 iterator = self.arc_iterator 
    2302             else: 
    2303                 iterator = self.edge_iterator 
    2304             for e in iterator(): 
    2305                 i = 0 
    2306                 while i < len(edge_labels): 
    2307                     if not edge_labels[i][0][2] == a[2]: 
    2308                         i += 1 
    2309                     else: 
    2310                         edge_labels[i].append(a) 
    2311                         break 
    2312                 if i == len(edge_labels): 
    2313                     edge_labels.append([a]) 
    2314             num_labels = len(edge_labels) 
    2315             R = rainbow(num_labels) 
    2316             edge_colors = {} 
    2317             for i in range(num_labels): 
    2318                 edge_colors[R[i]] = edge_labels[i] 
    2319                  
     2328            edge_colors = self._color_by_label() 
     2329         
    23202330        G = networkx_plot(self._nxg, pos=pos, vertex_labels=vertex_labels, vertex_size=vertex_size, vertex_colors=vertex_colors, edge_colors=edge_colors, graph_border=graph_border, scaling_term=scaling_term) 
    23212331        if edge_labels: 
    … …  
    40194029               vertex_colors=None, vertex_size=0.06, 
    40204030               edge_colors=None, edge_size=0.02, 
    4021                pos3d=None, iterations=50, **kwds): 
     4031               pos3d=None, iterations=50, color_by_label=False, **kwds): 
    40224032        """ 
    40234033        Plots the graph using Tachyon, and returns a Tachyon object containing 
    … …  
    40614071                                        vertex_size=vertex_size, pos3d=pos3d, iterations=iterations, **kwds) 
    40624072        edges = self.edges() 
     4073 
     4074        if color_by_label: 
     4075            if edge_colors is  None: 
     4076                # do the coloring 
     4077                edge_colors = self._color_by_label(format='rgbtuple') 
     4078 
    40634079        if edge_colors is None: 
    40644080            edge_colors = { (0,0,0) : edges } 
    40654081 
    40664082        i = 0 
     4083                         
    40674084        for color in edge_colors: 
    40684085            i += 1 
    … …  
    40704087            for u, v, l in edge_colors[color]: 
    40714088                TT.fcylinder( (pos3d[u][0],pos3d[u][1],pos3d[u][2]), (pos3d[v][0],pos3d[v][1],pos3d[v][2]), edge_size,'edge_color_%d'%i) 
     4089         
    40724090        return TT 
    40734091 
    … …  
    40754093               vertex_colors=None, vertex_size=0.06, 
    40764094               edge_colors=None, edge_size=0.02, 
    4077                pos3d=None, iterations=50, **kwds): 
     4095               pos3d=None, iterations=50, color_by_label=False, **kwds): 
    40784096        """ 
    40794097        Plots the graph using Tachyon, and shows the resulting plot. 
    … …  
    41134131 
    41144132        """ 
    4115         self.plot3d(bgcolor=bgcolor, vertex_colors=vertex_colors, edge_colors=edge_colors, vertex_size=vertex_size, edge_size=edge_size, iterations=iterations).show(**kwds) 
     4133        self.plot3d(bgcolor=bgcolor, vertex_colors=vertex_colors, 
     4134                    edge_colors=edge_colors, vertex_size=vertex_size, 
     4135                    edge_size=edge_size, iterations=iterations, 
     4136                    color_by_label=color_by_label).show(**kwds) 
    41164137     
    41174138    ### Connected components 
    … …  
    53745395               arc_size=0.02, 
    53755396               arc_size2=0.0325, 
    5376                arc_colors=None, pos3d=None, **kwds): 
     5397               arc_colors=None, pos3d=None, 
     5398               color_by_label=False, **kwds): 
    53775399        """ 
    53785400        Plots the graph using Tachyon, and returns a Tachyon object containing 
    … …  
    54175439                                        vertex_size=vertex_size, pos3d=pos3d, **kwds) 
    54185440        arcs = self.arcs() 
     5441        i = 0 
     5442 
     5443        if color_by_label: 
     5444            if arc_colors is None: 
     5445                arc_colors = self._color_by_label(format='rgbtuple') 
     5446 
    54195447        if arc_colors is None: 
    54205448            arc_colors = { (0,0,0) : arcs } 
    54215449         
    5422         i = 0 
    54235450        for color in arc_colors: 
    54245451            i += 1 
    … …  
    54375464               arc_size=0.02, 
    54385465               arc_size2=0.0325, 
    5439                arc_colors=None, pos3d=None, **kwds): 
     5466               arc_colors=None, 
     5467               pos3d=None, color_by_label=False, **kwds): 
    54405468        """ 
    54415469        Plots the graph using Tachyon, and shows the resulting plot. 
    … …  
    54765504 
    54775505        """ 
    5478         self.plot3d(bgcolor=bgcolor, vertex_colors=vertex_colors, vertex_size=vertex_size, arc_size=arc_size, arc_size2=arc_size2, arc_colors=arc_colors, **kwds).show() 
     5506         
     5507        self.plot3d(bgcolor=bgcolor, vertex_colors=vertex_colors, 
     5508                    vertex_size=vertex_size, arc_size=arc_size, 
     5509                    arc_size2=arc_size2, arc_colors=arc_colors, 
     5510                    color_by_label=color_by_label, **kwds).show() 
    54795511 
    54805512    ### Connected components 

  • sage/graphs/graph.py

    r5710 r5711  
    149149            1/2 
    150150             
    151             sage: L = graphs_query.get_list(num_vertices=7, diameter=5) 
     151            sage: G = GraphDatabase() 
     152            sage: L = G.get_list(num_vertices=7, diameter=5) 
    152153            sage.: graphs_list.show_graphs(L) 
    153154         
    … …  
    191192        and hit tab. 
    192193 
     194            sage: graphs_query = GraphDatabase() 
    193195            sage: L = graphs_query.get_list(num_vertices=7, diameter=5) 
    194196            sage.: graphs_list.show_graphs(L) 
    … …  
    20892091                    u,v = verts[i] 
    20902092                    w,x = verts[j] 
    2091                     if (self.has_arc(u, w) and v == x) or\ 
    2092                        (other.has_arc(v, x) and u == w) or\ 
     2093                    if (self.has_arc(u, w) and v == x) or \ 
     2094                       (other.has_arc(v, x) and u == w) or \ 
    20932095                       (self.has_arc(u, w) and other.has_arc(v, x)): 
    20942096                        D.add_arc((u,v), (w,x)) 
    … …  
    21052107                    u,v = verts[i] 
    21062108                    w,x = verts[j] 
    2107                     if (self.has_edge(u, w) and v == x) or\ 
    2108                        (other.has_edge(v, x) and u == w) or\ 
     2109                    if (self.has_edge(u, w) and v == x) or \ 
     2110                       (other.has_edge(v, x) and u == w) or \ 
    21092111                       (self.has_edge(u, w) and other.has_edge(v, x)): 
    21102112                        G.add_edge((u,v), (w,x)) 
    … …  
    21932195        return edge_colors      
    21942196 
    2195     def plot(self, pos=None, layout=None, vertex_labels=True,\ 
    2196              edge_labels=False, vertex_size=200, graph_border=False,\ 
    2197              vertex_colors=None, partition=None, edge_colors=None,\ 
    2198              scaling_term=0.05, iterations=50,\ 
     2197    def plot(self, pos=None, layout=None, vertex_labels=True, 
     2198             edge_labels=False, vertex_size=200, graph_border=False, 
     2199             vertex_colors=None, partition=None, edge_colors=None, 
     2200             scaling_term=0.05, iterations=50, 
    21992201             color_by_label=False, heights=None): 
    22002202        """ 
    … …  
    23132315                num_xes = len(heights[height]) 
    23142316                if num_xes == 0: continue 
    2315                 j = (mmax - num_xes)/2 
     2317                j = (mmax - num_xes)/2.0 
    23162318                for k in range(num_xes): 
    23172319                    pos[heights[height][k]] = [ dist * (j+k+1), height ] 
    … …  
    23382340        return G 
    23392341 
    2340     def show(self, pos=None, layout=None, vertex_labels=True,\ 
    2341              edge_labels=False, vertex_size=200, graph_border=False,\ 
    2342              vertex_colors=None, edge_colors=None, partition=None,\ 
    2343              scaling_term=0.05, talk=False, iterations=50,\ 
     2342    def show(self, pos=None, layout=None, vertex_labels=True, 
     2343             edge_labels=False, vertex_size=200, graph_border=False, 
     2344             vertex_colors=None, edge_colors=None, partition=None, 
     2345             scaling_term=0.05, talk=False, iterations=50, 
    23442346             color_by_label=False, heights=None, **kwds): 
    23452347        """ 
    … …  
    24222424            if partition is None: 
    24232425                vertex_colors = {'#FFFFFF':self.vertices()} 
    2424         self.plot(pos=pos, layout=layout, vertex_labels=vertex_labels,\ 
    2425                   edge_labels=edge_labels, vertex_size=vertex_size,\ 
    2426                   vertex_colors=vertex_colors, edge_colors=edge_colors,\ 
    2427                   graph_border=graph_border, partition=partition,\ 
    2428                   scaling_term=scaling_term, iterations=iterations,\ 
    2429                   color_by_label=color_by_label,\ 
     2426        self.plot(pos=pos, layout=layout, vertex_labels=vertex_labels, 
     2427                  edge_labels=edge_labels, vertex_size=vertex_size, 
     2428                  vertex_colors=vertex_colors, edge_colors=edge_colors, 
     2429                  graph_border=graph_border, partition=partition, 
     2430                  scaling_term=scaling_term, iterations=iterations, 
     2431                  color_by_label=color_by_label, 
    24302432                  heights=heights).show(**kwds) 
    24312433 
    … …  
    25812583        if format == 'graph6': 
    25822584            if not isinstance(data, str): 
    2583                 raise ValueError, 'If input format is graph6, then data must be a string' 
     2585                raise ValueError, 'If input format is graph6, then data must be a string.' 
    25842586            n = data.find('\n') 
    25852587            if n == -1: 
    … …  
    33403342        return networkx.closeness_centrality(self._nxg, v) 
    33413343     
     3344    ### Spectrum 
     3345     
     3346    def spectrum(self, laplacian=False): 
     3347        """ 
     3348        Returns the spectrum of the graph, the eigenvalues of the adjacency 
     3349        matrix 
     3350         
     3351        INPUT: 
     3352            laplacian -- if True, use the Laplacian matrix instead (see 
     3353                self.kirchhoff_matrix()) 
     3354         
     3355        EXAMPLE: 
     3356            sage: P = graphs.PetersenGraph() 
     3357            sage: P.spectrum() 
     3358            [-2.0, 1.0, 3.0, 1.0, -2.0, -2.0, -2.0, 1.0, 1.0, 1.0] 
     3359            sage: P.spectrum(laplacian=True) 
     3360            [5.0, 2.0, 1.48112136999e-16, 2.0, 5.0, 5.0, 5.0, 2.0, 2.0, 2.0] 
     3361         
     3362        """ 
     3363        from sage.matrix.constructor import matrix 
     3364        from sage.rings.real_double import RDF 
     3365        if laplacian: 
     3366            M = self.kirchhoff_matrix() 
     3367        else: 
     3368            M = self.am() 
     3369        M = matrix(RDF, M.rows()) 
     3370        E = M.eigen()[0] 
     3371        return [e.real() for e in E] 
     3372     
    33423373    ### Representations 
    33433374 
    … …  
    41984229         
    41994230        EXAMPLES: 
     4231            sage: graphs_query = GraphDatabase() 
    42004232            sage: L = graphs_query.get_list(num_vertices=4) 
    42014233            sage.: graphs_list.show_graphs(L) 
    … …  
    42894321        from sage.graphs.graph_isom import search_tree 
    42904322        if proof: 
     4323            if self.order() != other.order(): 
     4324                return False, None 
     4325            if self.size() != other.size(): 
     4326                return False, None 
     4327            if sorted(list(self.degree_iterator())) != sorted(list(other.degree_iterator())): 
     4328                return False, None 
    42914329            b,a = self.canonical_label(proof=True, verbosity=verbosity) 
    42924330            d,c = other.canonical_label(proof=True, verbosity=verbosity) 
    … …  
    43034341                return False, None 
    43044342        else: 
     4343            if self.order() != other.order(): 
     4344                return False 
     4345            if self.size() != other.size(): 
     4346                return False 
     4347            if sorted(list(self.degree_iterator())) != sorted(list(other.degree_iterator())): 
     4348                return False 
    43054349            from sage.graphs.graph_isom import search_tree 
    43064350            b = self.canonical_label(verbosity=verbosity) 
    … …  
    44384482            elif isinstance(data, networkx.XDiGraph): 
    44394483                self._nxg = data 
     4484            elif isinstance(data, str): 
     4485                format = 'dig6' 
    44404486            else: 
    44414487                self._nxg = networkx.XDiGraph(data, selfloops=loops, **kwds) 
    … …  
    44934539                        e.append((k[1],k[0])) 
    44944540                self._nxg.add_edges_from(e) 
     4541        elif format == 'dig6': 
     4542            if not isinstance(data, str): 
     4543                raise ValueError, 'If input format is dig6, then data must be a string.' 
     4544            n = data.find('\n') 
     4545            if n == -1: 
     4546                n = len(data) 
     4547            s = data[:n] 
     4548            n, s = graph_fast.N_inverse(s) 
     4549            m = graph_fast.D_inverse(s, n) 
     4550            d = {} 
     4551            k = 0 
     4552            for i in range(n): 
     4553                d[i] = {} 
     4554                for j in range(n): 
     4555                    if m[k] == '1': 
     4556                        d[i][j] = None 
     4557                    k += 1 
     4558            self._nxg = networkx.XDiGraph(d) 
    44954559        if kwds.has_key('name'): 
    44964560            self._nxg.name = kwds['name'] 
    … …  
    53885452            TT.texture('arc_color_%d'%i, ambient=0.1, diffuse=0.9, specular=0.03, opacity=1.0, color=color) 
    53895453            for u,v,l in arc_colors[color]: 
    5390                 TT.fcylinder( (pos3d[u][0],pos3d[u][1],pos3d[u][2]),\ 
     5454                TT.fcylinder( (pos3d[u][0],pos3d[u][1],pos3d[u][2]), 
    53915455                              (pos3d[v][0],pos3d[v][1],pos3d[v][2]), arc_size,'arc_color_%d'%i) 
    5392                 TT.fcylinder( (0.25*pos3d[u][0] + 0.75*pos3d[v][0],\ 
    5393                                0.25*pos3d[u][1] + 0.75*pos3d[v][1],\ 
     5456                TT.fcylinder( (0.25*pos3d[u][0] + 0.75*pos3d[v][0], 
     5457                               0.25*pos3d[u][1] + 0.75*pos3d[v][1], 
    53945458                               0.25*pos3d[u][2] + 0.75*pos3d[v][2],), 
    53955459                              (pos3d[v][0],pos3d[v][1],pos3d[v][2]), arc_size2,'arc_color_%d'%i) 
    … …  
    55835647        from sage.graphs.graph_isom import search_tree 
    55845648        if proof: 
     5649            if self.order() != other.order(): 
     5650                return False, None 
     5651            if self.size() != other.size(): 
     5652                return False, None 
     5653            if sorted(list(self.in_degree_iterator())) != sorted(list(other.in_degree_iterator())): 
     5654                return False, None 
     5655            if sorted(list(self.out_degree_iterator())) != sorted(list(other.out_degree_iterator())): 
     5656                return False, None 
    55855657            b,a = self.canonical_label(proof=True, verbosity=verbosity) 
    55865658            d,c = other.canonical_label(proof=True, verbosity=verbosity) 
    … …  
    55975669                return False, None 
    55985670        else: 
     5671            if self.order() != other.order(): 
     5672                return False 
     5673            if self.size() != other.size(): 
     5674                return False 
     5675            if sorted(list(self.in_degree_iterator())) != sorted(list(other.in_degree_iterator())): 
     5676                return False 
     5677            if sorted(list(self.out_degree_iterator())) != sorted(list(other.out_degree_iterator())): 
     5678                return False 
    55995679            from sage.graphs.graph_isom import search_tree 
    56005680            b = self.canonical_label(verbosity=verbosity) 
    … …  
    56355715            a,b = search_tree(self, partition, dig=True, verbosity=verbosity) 
    56365716            return b 
     5717     
     5718    ### DIG6 format 
     5719     
     5720    def __bit_vector(self): 
     5721        vertices = self.vertices() 
     5722        n = len(vertices) 
     5723        ns = n*n 
     5724        bit_vector = set() 
     5725        for e,f,g in self.arc_iterator(): 
     5726            c = vertices.index(e) 
     5727            d = vertices.index(f) 
     5728            p = c*n + d 
     5729            bit_vector.add(p) 
     5730        bit_vector = sorted(bit_vector) 
     5731        s = [] 
     5732        j = 0 
     5733        for i in bit_vector: 
     5734            s.append( '0'*(i - j) + '1' ) 
     5735            j = i + 1 
     5736        s = "".join(s) 
     5737        s += '0'*(ns-len(s)) 
     5738        return s 
     5739     
     5740    def dig6_string(self): 
     5741        """ 
     5742        Returns the dig6 representation of the digraph as an ASCII string. 
     5743        Valid for single (no multiple edges) digraphs on 0 to 262143 vertices. 
     5744         
     5745        EXAMPLE: TODO 
     5746 
     5747        """ 
     5748        n = self.order() 
     5749        if n > 262143: 
     5750            raise ValueError, 'dig6 format supports graphs on 0 to 262143 vertices only.' 
     5751        elif self.multiple_arcs(): 
     5752            raise ValueError, 'dig6 format does not support multiple edges.' 
     5753        else: 
     5754            return graph_fast.N(n) + graph_fast.R(self.__bit_vector()) 
    56375755 
    56385756    ### Directed Acyclic Graphs (DAGs) 
Note: See TracChangeset for help on using the changeset viewer.