Graph Connectivity Probability

[84a8d5a7-8b56-4408-8526-3d1eb144bfdc]

This is a new function that computes the probability that vertices in a simple undirected graph are connected.

The input is a (symmetric) probability matrix that assigns a probability to each edge in the graph.

The output is a matrix containing the probability that each pair of vertices will be connected in the graph given the edge probabilities in the input matrix.

See the documentation in the file for more information.

CC: @dimpase

Component: graph theory

Author: James Rudzinski

Branch/Commit: u/jerudzin/graph_connectivity_probability @ d82e9d4

Issue created by migration from https://trac.sagemath.org/ticket/20186

[84a8d5a7-8b56-4408-8526-3d1eb144bfdc]

Description changed:

--- 
+++ 
@@ -1 +1,7 @@
+This is a new function that computes the probability that vertices in a simple undirected graph are connected. 

+The input is a (symmetric) probability matrix that assigns a probability to each edge in the graph. 
+
+The output is a matrix containing the probability that each pair of vertices will be connected in the graph given the edge probabilities in the input matrix. 
+
+See the documentation in the file for more information.

[tscrim]

comment:2

Attachment: connectivity_probability.py.gz

In case nobody has done so, welcome to Sage.

There are a few things that will need to be done before this can be a part of Sage:

• You will need to create git branch of your changes and push it to the trac git server.
• All functions and methods (not just public) need doctests (and documentation if their functionality is not obvious). References would be welcomed.
• I think it would be good to have this was a method for graphs by using edges labeled by the probability.
• Your functions' documentation should have a short one sentence description (which is declarative, i.e., "Return", not "Returns"), then a blank line, then the more detailed description afterwards.

For general conventions and help, see: http://doc.sagemath.org/html/en/developer/index.html. Let me know if you have any questions.

You will also need to fill in your real name in the authors field.

Best, Travis

[84a8d5a7-8b56-4408-8526-3d1eb144bfdc]

Branch: u/jerudzin/graph_connectivity_probability

[84a8d5a7-8b56-4408-8526-3d1eb144bfdc]

Commit: d82e9d4

[84a8d5a7-8b56-4408-8526-3d1eb144bfdc]

New commits:

d82e9d4

Added the file connectivity_probability.py

[dimpase]

Author: James Rudzinski

[dimpase]

comment:5

There are no references provided in docstrings to the algorithms implemented.

[dimpase]

comment:6

I don't understand why this function does not take a weighted Sage graph as an input, but some matrix. E.g. it would be most natural apply it to the weighted adjacency matrix of a graph, e.g.

sage: h.add_edges([[0,1,1/2],[1,2,2/3]])
sage: h
Graph on 3 vertices
sage: h.weighted_adjacency_matrix()

[  0 1/2   0]
[1/2   0 2/3]
[  0 2/3   0]