can i find the leader/source vertex of a directed acyclic graph ?

[AkashKumar7902]

[AkashKumar7902]

A more wide application for implementing this would be to merge two graphs

g.addEdge(vertex v, <source vertex of DAG>

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:

1. g1 = graph.Union(g1, g2)
2. g1.addEdge(v, findsource(g2)), where v is a vertex of graph g1 from which we want to add an edge to complete the merge.

[AkashKumar7902]

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
}

[dominikbraun]

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? 😄

[AkashKumar7902]

@dominikbraun

Yes. I was wondering will there be a function getSource in the package itself. I can send a PR for it.

[dominikbraun]

@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!