1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
Mentored Projects
==================
This page maintains a list of mentored project ideas that contributors can work
on if they are interested in contributing to the NetworkX project. Feel free to
suggest any other idea if you are interested on the
`NetworkX GitHub discussions page <https://github.com/networkx/networkx/discussions>`__
These ideas can be used as projects for Google Summer of Code, Outreachy,
NumFOCUS Small Development Grants and university course/project credits (if
your university allows contribution to open source for credit).
Pedagogical Interactive Notebooks for Algorithms Implemented in NetworkX
------------------------------------------------------------------------
- Abstract: NetworkX has a :ref:`wide variety of algorithms <Algorithms>`
implemented. Even though the algorithms are well documented, explanations of
the ideas behind the algorithms are often missing and we would like to
collect these, write Jupyter notebooks to elucidate these ideas and explore
the algorithms experimentally, and publish the notebooks at
https://github.com/networkx/notebooks. The goal is to gives readers a
deeper outlook behind standard network science and graph theory algorithms
and encourage them to delve further into the topic.
- Recommended Skills: Python, Jupyter notebooks, graph algorithms.
- Expected Outcome: A collection of Interactive Jupyter notebooks which
explain and explore network algorithms to readers and users of NetworkX.
For example, see this notebook on
:doc:`Random Geometric Graphs <content/generators/geometric>`
- Complexity: Depending on the algorithms you are interested to work on.
- Interested Mentors: `@dschult <https://github.com/dschult/>`__,
`@MridulS <https://github.com/MridulS/>`__,
`@rossbar <https://github.com/rossbar/>`__
Implement the VF2++ Graph Isomorphism Algorithm
-----------------------------------------------
- Abstract: The `Graph Isomorphism Problem`_ is a famous difficult network problem at
the boundary between P and NP-Complete. The VF2 algorithm is included with NetworkX
in a recursive formulation. There is an improved version of this algorithm called
`VF2++`_ which we intend to implement. We have early attempts at a nonrecursive version
of the main algorithm that also address subgraph isomorphism and subgraph monomorphism.
This project involves fully implementing them and extending to directed and multigraph
settings.
- Recommended Skills: Python, graph algorithms
- Expected Outcome: A new set of functions in NetworkX that implement the VF2++
algorithm for all problem and graph types in a nonrecursive manner.
- Complexity: Moderate
- Interested Mentors: `@dschult <https://github.com/dschult/>`__,
`@MridulS <https://github.com/MridulS/>`__, `@boothby <https://github.com/boothby/>`__,
.. _`Graph Isomorphism Problem`: https://en.wikipedia.org/wiki/Graph_isomorphism_problem
.. _VF2++: https://doi.org/10.1016/j.dam.2018.02.018
Completed Projects
==================
- `Louvain community detection algorithm`_ (GSoC 2021)
- `Asadpour algorithm for directed travelling salesman problem`_ (GSoC 2021)
- Pedagogical notebook: `Directed acyclic graphs and topological sort`_ (GSoC 2021)
- Pedagogical notebook: `Graph assortativity`_ (GSoC 2021)
- Pedagogical notebook: `Network flow analysis and Dinitz algorithm`_ (GSoC 2021)
.. _`Louvain community detection algorithm`: https://github.com/networkx/networkx/pull/4929
.. _`Asadpour algorithm for directed travelling salesman problem`: https://github.com/networkx/networkx/pull/4740
.. _`Directed acyclic graphs and topological sort`: https://github.com/networkx/nx-guides/pull/44
.. _`Graph assortativity`: https://github.com/networkx/nx-guides/pull/42
.. _`Network flow analysis and Dinitz algorithm`: https://github.com/networkx/nx-guides/pull/46
..
Project Idea Template
---------------------
- Abstract:
- Recommended Skills:
- Expected Outcome:
- Complexity;
- Interested Mentors:
|
