QuantEcon / QuantEcon/QuantEcon.py

Null DiGraph

Open
#156 0 comments 0 reactions 0 assignees View on GitHub

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.DiGraph allow 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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.