DAGs from Graph

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:

  1. Which nodes in a graph have no in-nodes? All nodes that in adjacency matrix has in their column a 0 for all positions.
  2. 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)


Posted

in

by