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

No description provided.

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:

g1 = graph.Union(g1, g2)
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.

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

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

Navigation Menu

Repository navigation

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

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

AkashKumar7902 commented on Feb 9, 2024

AkashKumar7902 commented on Feb 11, 2024

dominikbraun commented on Mar 6, 2024

AkashKumar7902 commented on Mar 6, 2024

dominikbraun commented on Mar 6, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions