QuantEcon / QuantEcon/QuantEcon.py
Null DiGraph
Open
Nobody has claimed this yet.
discuss
question
- Dominant language
- Python
- Stars
- 2.4k
- Forks
- 2.3k
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 3
Description
This is a tiny point, but just for record:
- Should
graph_tools.DiGraphallow a null graph (a graph with no node)? (It is allowed in the current implementation.) - If so, is a null digraph strongly connected? (It is not in the current implementation.)
>>> adj_matrix = np.array([]).reshape(0, 0)
>>> adj_matrix
array([], shape=(0, 0), dtype=float64)
>>> null_digraph = qe.DiGraph(adj_matrix)
>>> null_digraph
Directed Graph:
- n(number of nodes): 0
>>> null_digraph.is_strongly_connected
False
>>> null_digraph.num_strongly_connected_components
0
>>> null_digraph.strongly_connected_components
[]
>>> null_digraph.num_sink_strongly_connected_components
0
>>> null_digraph.sink_strongly_connected_components
[]
In passing, in Networkx whether or not a null digraph is strongly connected is undefined.
>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.number_of_nodes()
0
>>> nx.is_strongly_connected(G)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 2, in is_strongly_connected
File "/usr/local/lib/python2.7/site-packages/networkx/utils/decorators.py", line 68, in _not_implemented_for
return f(*args,**kwargs)
File "/usr/local/lib/python2.7/site-packages/networkx/algorithms/components/strongly_connected.py", line 287, in is_strongly_connected
"""Connectivity is undefined for the null graph.""")
networkx.exception.NetworkXPointlessConcept: Connectivity is undefined for the null graph.
>>> nx.number_strongly_connected_components(G)
0
>>> list(nx.strongly_connected_components(G))
[]
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with graph_tools.DiGraph and the is_strongly_connected, num_strongly_connected_components, strongly_connected_components, and sink-component entry points described in the issue. First establish the intended convention for null digraphs, then verify that the implementation consistently follows that decision. Done means the null-graph policy is decided and its observable behavior is consistent.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- numpy, python
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100