d=DiGraph(3)
d.show()
d.add_edge(0,1)
d.show()
d.add_edge(1,2)
d.show()
d.eccentricity?
File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : d.eccentricity(self, v=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True, dist_dict=None, with_labels=False) Docstring : Return the eccentricity of vertex (or vertices) v. The eccentricity of a vertex is the maximum distance to any other vertex. For more information and examples on how to use input variables, see "shortest_paths()" INPUT: * "v" - either a single vertex or a list of vertices. If it is not specified, then it is taken to be all vertices. * "by_weight" - if "True", edge weights are taken into account; if False, all edges have weight 1. * "algorithm" (string) - one of the following algorithms: * "'BFS'" - the computation is done through a BFS centered on each vertex successively. Works only if "by_weight==False". * "'Floyd-Warshall-Cython'" - a Cython implementation of the Floyd-Warshall algorithm. Works only if "by_weight==False" and "v is None". * "'Floyd-Warshall-Python'" - a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, "v" must be "None". * "'Dijkstra_NetworkX'": the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed. * "'Dijkstra_Boost'": the Dijkstra algorithm, implemented in Boost (works only with positive weights). * "'Johnson_Boost'": the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). * "'From_Dictionary'": uses the (already computed) distances, that are provided by input variable "dist_dict". * "None" (default): Sage chooses the best algorithm: "'From_Dictionary'" if "dist_dict" is not None, "'BFS'" for unweighted graphs, "'Dijkstra_Boost'" if all weights are positive, "'Johnson_Boost'" otherwise. * "weight_function" (function) - a function that inputs an edge "(u, v, l)" and outputs its weight. If not "None", "by_weight" is automatically set to "True". If "None" and "by_weight" is "True", we use the edge label "l" as a weight. * "check_weight" (boolean) - if "True", we check that the weight_function outputs a number for each edge. * "dist_dict" - used only if "algorithm=='From_Dictionary'" - a dict of dicts of distances. * "with_labels" - Whether to return a list or a dict. EXAMPLES: sage: G = graphs.KrackhardtKiteGraph() sage: G.eccentricity() [4, 4, 4, 4, 4, 3, 3, 2, 3, 4] sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: G.eccentricity(7) 2 sage: G.eccentricity([7,8,9]) [3, 4, 2] sage: G.eccentricity([7,8,9], with_labels=True) == {8: 3, 9: 4, 7: 2} True sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } ) sage: G.eccentricity() [+Infinity, +Infinity, +Infinity] sage: G = Graph({0:[]}) sage: G.eccentricity(with_labels=True) {0: 0} sage: G = Graph({0:[], 1:[]}) sage: G.eccentricity(with_labels=True) {0: +Infinity, 1: +Infinity} sage: G = Graph([(0,1,1), (1,2,1), (0,2,3)]) sage: G.eccentricity(algorithm = 'BFS') [1, 1, 1] sage: G.eccentricity(algorithm = 'Floyd-Warshall-Cython') [1, 1, 1] sage: G.eccentricity(by_weight = True, algorithm = 'Dijkstra_NetworkX') [2, 1, 2] sage: G.eccentricity(by_weight = True, algorithm = 'Dijkstra_Boost') [2, 1, 2] sage: G.eccentricity(by_weight = True, algorithm = 'Johnson_Boost') [2, 1, 2] sage: G.eccentricity(by_weight = True, algorithm = 'Floyd-Warshall-Python') [2, 1, 2] sage: G.eccentricity(dist_dict = G.shortest_path_all_pairs(by_weight = True)[0]) [2, 1, 2]
d.eccentricity(0)
2
d.eccentricity(2)
+Infinity
d.radius?
File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : d.radius(self, by_weight=False, algorithm=None, weight_function=None, check_weight=True) Docstring : Returns the radius of the (di)graph. The radius is defined to be the minimum eccentricity of any vertex, where the eccentricity is the maximum distance to any other vertex. For more information and examples on how to use input variables, see "shortest_paths()" and "eccentricity()" INPUT: * "by_weight" - if "True", edge weights are taken into account; if False, all edges have weight 1. * "algorithm" (string) - one of the following algorithms: * "'BFS'" - the computation is done through a BFS centered on each vertex successively. Works only if "by_weight==False". * "'Floyd-Warshall-Cython'" - a Cython implementation of the Floyd-Warshall algorithm. Works only if "by_weight==False". * "'Floyd-Warshall-Python'" - a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). * "'Dijkstra_NetworkX'": the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed. * "'Dijkstra_Boost'": the Dijkstra algorithm, implemented in Boost (works only with positive weights). * "'Johnson_Boost'": the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). * "None" (default): Sage chooses the best algorithm: "'BFS'" for unweighted graphs, "'Dijkstra_Boost'" if all weights are positive, "'Johnson_Boost'", otherwise. * "weight_function" (function) - a function that inputs an edge "(u, v, l)" and outputs its weight. If not "None", "by_weight" is automatically set to "True". If "None" and "by_weight" is "True", we use the edge label "l" as a weight. * "check_weight" (boolean) - if "True", we check that the weight_function outputs a number for each edge. EXAMPLES: The more symmetric a graph is, the smaller (diameter - radius) is. sage: G = graphs.BarbellGraph(9, 3) sage: G.radius() 3 sage: G.diameter() 6 sage: G = graphs.OctahedralGraph() sage: G.radius() 2 sage: G.diameter() 2
d.shortest_path_all_pairs()
({0: {0: 0, 1: 1, 2: 2}, 1: {1: 0, 2: 1}, 2: {2: 0}}, {0: {0: None, 1: 0, 2: 1}, 1: {1: None, 2: 1}, 2: {2: None}})
d.shortest_path_length(0,2)
2
d.shortest_path(2,0)
[]
dd=d.strong_product(d)
dd.show()
dd.vertices()
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
dd.eccentricity((2,2))
+Infinity
dd.eccentricity((0,0))
2
dd.radius()
2
c=digraphs.Circuit(3)
c.show()
c.radius()
2
dc=d.strong_product(c)
dc.show()
d2=digraphs.ButterflyGraph(2)
d2.show()
#conjectures about pairs of digraphs load("conjecturing.py") digraphs = [d, d2, c] digraph_pairs = [(d,d), (d,d2), (d,c)] def strong_product_radius((d1,d2)): return d1.strong_product(d2).radius() def max_radius((d1,d2)): return max(d1.radius(),d2.radius()) invariants = [strong_product_radius,max_radius] #conjectures should be interpreted for any *pairs* (d1,d2) of connected digraphs conjecture(digraph_pairs,invariants,invariants.index(strong_product_radius))
[strong_product_radius(x) <= max_radius(x)]