Opened 5 years ago

Last modified 4 years ago

#20186 needs_work enhancement

Graph Connectivity Probability

Reported by: jerudzin Owned by:
Priority: minor Milestone: sage-7.5
Component: graph theory Keywords:
Cc: dimpase Merged in:
Authors: James Rudzinski Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jerudzin/graph_connectivity_probability (Commits) Commit: d82e9d4e3fd5d5d888303ae8504ac5b7d375f70c
Dependencies: Stopgaps:

Description (last modified by jerudzin)

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.

Attachments (1) (36.0 KB) - added by jerudzin 5 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 5 years ago by jerudzin

  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Priority changed from major to minor
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

Changed 5 years ago by jerudzin

comment:2 Changed 5 years ago by tscrim

  • Status changed from needs_review to needs_work

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: Let me know if you have any questions.

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

Best, Travis

comment:3 Changed 5 years ago by jerudzin

  • Branch set to u/jerudzin/graph_connectivity_probability

comment:4 Changed 4 years ago by jerudzin

  • Cc dimpase added
  • Commit set to d82e9d4e3fd5d5d888303ae8504ac5b7d375f70c
  • Milestone changed from sage-7.1 to sage-7.5

New commits:

d82e9d4Added the file

comment:5 Changed 4 years ago by dimpase

  • Authors set to James Rudzinski

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

comment:6 Changed 4 years ago by dimpase

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]
Note: See TracTickets for help on using tickets.