Still ChatGPT. But bad experience this time.

I asked all possible distinct DAGs given an adjacency matrix of a graph (probably not connected). I insisted that the graph is not connected. But “it” pretended to just make a loop over the nodes and build “all possible dags” (it pretends).

I must note that the solution I put above is wrong as well, you notice that if there are common subpath for distinct DAGs those are just skipped, because it has *visited* node in common (and dfs method stop as soon it meets a visited node).

Fortunately the algos I read just yesterday night inspired me. It was a list ranking problem (find the distance of each node from the end, in a linked list), nothing related, but it was just my imagination to think to a linked list as it was a graph, with a single path, and connected. (and I thought also to the adjacency matrix and the algorithm meaning in term of transformation, but then I fall sleep).

Anyway:

- Which nodes in a graph have no in-nodes? All nodes that in adjacency matrix has in their column a 0 for all positions.
- Which nodes in a graph have no out-nodes? All nodes that in adjacency matrix has in their row a 0 for all positions.

So far so easy. I can also say that all nodes *i* which has row *i* and column *i*, all 0, those node are “spare node”, or “single node dag”.

In fact, I was asking for all DAGs, not *almost all*.

Of course I can not have `Vec<Vec<(usize, usize)>>`

as output if I want _all_ dag, but I need something more specific.

I am using `fixedbitset::FixedBitSet`

as adjacency matrix that is exported from petgraph, but I think that `Vec<petgraph::graph::Graph>`

is overkilling here. Also I defined a dedicated struct, so I can define _another_ dedicated struct for that, or better an Enum, why not? so exporting Vec<Mydag> where

```
enum MyDAG {
Path(Vec<(usize,usize)>),
Single(usize),
}
```

In the code above the visited Vec must stay inside the for loop, and it returns a Vec<MyDAG> now

```
fn find_connected_dags(&self) -> Vec<MyDAG> {
// given the adjacency matrix for each column which has no setted bit
// do: dfs(on that node)
let startings = self.select_starting_nodes();
let mut sub_dags = Vec::new();
for node in startings.iter() {
let mut visited = vec![false; self.size];
let mut dag = Vec::new();
self.dfs( *node, &mut visited, &mut dag);
if !dag.is_empty() {
sub_dags.push(MyDAG::Path(dag));
} else {
sub_dags.push(MyDAG::Single(*node));
}
}
sub_dags
}
fn dfs(&self, node: usize, visited: &mut [bool], dag: &mut Vec<(usize, usize)>) {
let len = self.getsize();
visited[node] = true;
for i in 0..len {
if self.contains(node, i) {
dag.push((node, i));
if !visited[i] {
self.dfs(i, visited, dag);
}
}
}
}
```

I just began to know petgraph, and maybe this are already in, but I am exploring staff.

rif. <https://github.com/petgraph/fixedbitset>, <https://docs.rs/petgraph/latest/petgraph/index.html>

UPDATE: fixed range expression `0..len`

(to is not inclusive, and it caused me some headaches)