CODEWITHSUNDEEP
c#recursiondirected-acyclic-graphs
HelloWorld
HelloWorld

Reputation: 4892

Traverse up a directed graph in c# (DAG)

I have a simple graph without cycles/Multiple edges.

Its always pointing down.

enter image description here

I have a list of edge instances and they are sorted top to down according to their appearance in the graph image. I do not know whether that is important for you. I just thought how would you know what is the node at the bottom of the graph?!

class Edge
{
   public string FromNodeId {get; set;}
   public string ToNodeId{get; set;}
}

class Node
{
   public int Id {get; set;}
   public string Name {get; set;}
}

I need to traverse UP the graph due to certain business logic.

  1. What is the algorythm called when I need to visit every node in a recursive way?
  2. What could be a starting point to iterate the list of edges recursively up the graph?

Upvotes: 1

Views: 1603

Answers (1)

Amine Ramoul
Amine Ramoul

Reputation: 134

here is the browsing methode of a graph from bottom to top.

you need to initialize it with your last element.

            class Edge
            {
                public int FromNodeId { get; set; }
                public int ToNodeId { get; set; }
            }
            class Node // nodes from 0 or 1 to infinit
            {
                public int Id { get; set; }
                public string Name { get; set; }
            }

            void fromBottom(List<Edge> Edges,List<Node> Nodes, Node current)  
            {
                var willVisit = Edges.Where(x => x.ToNodeId == current.Id).ToList();
                if (willVisit.FirstOrDefault()==null)
                {
                    // do your stuff for the last node
                }
                else
                {
                    foreach(var nd in willVisit)
                    {
                        fromBottom(Edges, Nodes,Nodes.Where(x=>x.Id==nd.FromNodeId).First());
                    }
                }
            }

here is the browsing methode of a graph from top to bottom.

            void fromTop(List<Edge> Edges,List<Node> Nodes, Node current)  
            {
                var willVisit = Edges.Where(x => x.FromNodeId == current.Id).ToList();
                if (willVisit.FirstOrDefault()==null)
                {
                    // do your stuff for the last node 
                }
                else
                {
                    foreach(var nd in willVisit)
                    {
                        fromTop(Edges, Nodes,Nodes.Where(x=>x.Id==nd.ToNodeId).First());
                    }
                }
            }

note : to avoid visiting a node several times, you can add a boolean variable in your structure to validate the visit and check it later in the foreach loop.

Upvotes: 1

Related Questions