0

I need help with Wriring a program (in any programming language) that gets as

input a positive integer and generates all possible connected sub-graphs of size .

For example: 3 node graphs can have 13 possible combinations which are: https://i.stack.imgur.com/8DVpj.png

The output should be a textual file of the following form:

for example:

n=2

count=2

"#"1:

1 2

"#"2:

1 2

2 1

The first two lines output n and the total number (count) of different sub-graphs of size n.

Then the sub-graphs themselves are given each starting with a line labelled #k for sub-graph number followed by all edges, each line i j means an edge from source i to target j.

Jony Shampaner
  • 1

1 Answers1

0

Think about it in terms of set theory. The nodes can be identified as integers, so the set of nodes for a given n is simply {1, 2, ..., n}. Then the set of possible edges is the Cartesian product {1, 2, ..., n} x {1, 2, ..., n}. Depending on your definition of a directed graph, you may want to subtract the set {(1, 1), (2, 2), ..., (n, n)}. Now you can determine all the subsets of that set of possible edges and then select those that represent connected subgraphs.

Many programming languages have these operations already implemented. For example, with Python you could use the product() function from the itertools module for the Cartesian product. Then you could pick a way to compute the power set from the answers to this question.

Arne
  • 9,990
  • 2
  • 18
  • 28
  • because this is a directed graph the set should include for example both: (1,2) and (2,1) but in this way only one of them will be in the set. – Jony Shampaner May 24 '20 at 10:30
  • In addition, I did not understand from your answer what algorithm I use to find from the set all the possible options for a connected directed graph – Jony Shampaner May 24 '20 at 10:34
  • @Jony Shampaner I understand that (1, 2) and (2, 1) should both be included, and the Cartesian product does deliver this. You are right that my answer is incomplete, in that I did not address the question of how exactly to filter for connectedness. The definition you are using for a connected directed graph is unclear to me. For example, if graph #2 in the picture you give does qualify, why would the graph with the same two edges, but in the opposite directions, not be included? Is that because it would be considered equivalent, since the identity of the nodes does not matter? – Arne May 24 '20 at 18:58