Open AkashKumar7902 opened 5 months ago
To all those who might be looking for a solution:
func FindSource[K comparable, T any](g graph.Graph[K, T]) ([]K, error) {
if !g.Traits().IsDirected {
return nil, fmt.Errorf("cannot find source of a non-DAG graph ")
}
predecessorMap, err := g.PredecessorMap()
if err != nil {
return nil, fmt.Errorf("failed to get predecessor map: %w", err)
}
var sources []K
for vertex, predecessors := range predecessorMap {
if len(predecessors) == 0 {
sources = append(sources, vertex)
}
}
return sources, nil
}
Hi, thanks for the late response! Using PredecessorMap
and then backtrack to the root seems to be the correct approach. Is this issue then clarified for you? 😄
@dominikbraun
Yes. I was wondering will there be a function getSource
in the package itself. I can send a PR for it.
@dominikbraun
Yes. I was wondering will there be a function
getSource
in the package itself. I can send a PR for it.
@AkashKumar7902 Yes, that sounds reasonable. Feel free to submit a PR!
A more wide application for implementing this would be to merge two graphs
doing this will merge DAG into graph g on its vertex v.
UPD: Found a solution for this,
first you must implement
findsource
function, I have provided the implementation just below this comment. To merge two graphs, follow these steps: