pythongraph# Minium set of nodes that satisfy the given number of edges

For example, we have the adjacency list like below. If the desired number of edges is 2, then the sets of nodes that suffice are (1,2), (1,3), (1,4), (2,3) and (3,4). If the desired number of edges is 3, then the sets of nodes that suffice are none. If the desired number of edges is 4, then the sets of nodes that suffice are (1, 2, 4) and (2, 3, 4).

```
# Sample adjacency list
adjacency_list = {
1: [2, 3, 4],
2: [1, 3],
3: [1, 2, 4],
4: [1, 3]
}
```

I am fairly new to graph theory and my search with Google or Chat GPT was not successful. I feel like this could be a DP problem but really don't know what's an efficient way to do it. Any advice would be appreciated.

Solution

IIUC, this is a Directed graph problem. If so and if you're tempted to use networkx, try this :

```
import networkx as nx
from itertools import chain, combinations
G = nx.DiGraph(adjacency_list)
def combs(lst):
return chain(*map(lambda x: combinations(lst, x), range(1, len(lst)+1)))
def get_nodes(G, nb_edges):
for c in combs(G.nodes):
if G.subgraph(c).number_of_edges() == nb_edges:
yield c
```

Test/Output :

```
op_vals = [2, 3, 4]
for v in op_vals:
print(f"for {v} edges, {list(get_nodes(G, v))} suffice!")
# for 2 edges, [(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)] suffice!
# for 3 edges, [] suffice!
# for 4 edges, [(1, 2, 4), (2, 3, 4)] suffice!
```

A visualization for the sets of nodes (*yellow*) required for `4`

edges (*blue*) :

- I want to apply an algorithm to different images from a folder and save the new ones in another folder
- installing Brain Scaffold Builder with broken rtree dependency
- Display of music21, musicXML PNG objects using iPython Notebook/Enthought Canopy
- Showing midi pitch numbers from Mid file with music21
- Finding notes sounding at the same time in a different voice in a midi file
- How to replace pitches in a music21 Score
- music21 getElementsByClass not showing any output for class stream.Voice
- Custom Scale using music21's scale class to inherit "deriveAll" function
- reading MIDI file using music21 with partitionByInstrument() to get notes and chords returning empty list
- music21: get the voice/program/instrument of midi voice from a flat score?
- How do I read midi / musicxml files in music21 for solo piano where there can be multiple notes in a voice simultaneously?
- Music21: Strip empty data at end of written midi file
- Is there a way to constrain music21's chord detection to non-slash chords?
- Why is numpy's sine function so inaccurate at some points?
- Try to generate binary file with music21 library
- 10 sites through same codebase django MTI, ABCs or EAV
- Pylint cannot handle abstract subclasses of abstract base classes
- ID generator with python for sqlachamy in API
- Is there a way to persist decorators during inheritance?
- Calculating Euler's number
- Why do I get a "ModuleNotFoundError" when pip says "Requirement already satisfied"?
- Python 'list indices must be integers, not tuple" error
- ValueError on inverse transform using OrdinalEncoder with sklearn
- Pip: unistall ALL pkgs installed during `-e` installation
- Set Flask environment to development mode as default?
- How to tackle a 'str' not callable error message
- Importing pandas and cplex in a conda environment raises an ImportError: libstdc++.so.6: version `GLIBCXX_3.4.29' not found
- How to tell Flatpak-builder / meson to run python with command line options
- Enabling and Validating Bit Parity between C++ and Python
- Compare two lists elementwise with OR