common paths in DAG

[ETH11674]

Hello everyone,

my question is how to detect reconvergent paths in graph,
i searched everywhere but there were nothing relevant with this subject.


i implement the Graph structure like this:

  class AdjListNode
{
	int v;
	int weight;
	vector<float> weight_vec;

public:
	AdjListNode(int _v, int _w)
	{
		v = _v;
		weight = _w;
	}
	int vertex()
	{
		return v;
	}
	int getWeight()
	{
		return weight;
	}
	
};

// Class to represent a graph using adjacency list representation
class Graph
{
	int V; // No. of vertices’

	// Pointer to an array containing adjacency lists
	list<AdjListNode> *adj;

	// A function used by longestPath
	void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
	Graph(int V); // Constructor

	// function to add an edge to graph
	void addEdge(int u, int v, int weight);

	// Finds longest distances from given source vertex
	void longestPath(int s);
};

Graph::Graph(int V) // Constructor
{
	this->V = V;
	adj = new list<AdjListNode>[V];
}

void Graph::addEdge(int u, int v, int weight)
{
	AdjListNode node(v, weight);
	adj[u].push_back(node); // Add v to u’s list
}

thanks
regards

[dhayden]

I wasn't able to figure out exactly what a reconvergent path is presentation. It sounds like you're given two paths and the reconvergent path is a part that common between the two. Does it have to be at the beginning of the paths, or can it be in the middle? What if the paths have multiple subpaths in common? Can you be more specific about the problem?

[ETH11674]

yes...any two or more paths which start from one common node and then meet at another node.
it doesn't matter that the starting point is at the beginning or in the middle of the paths.
i just wanna specify such paths as pair of nodes. for instance first reconvergent paths source is node 'a' and sink node is 'z'. and denote it like (a,z). if we have multiple reconvergent paths then we have list of pairs (or paths) e.g. list [(a,d), (a,k), (c,h), (k,w), (a, z), ...].

It is somehow like we want to detect cycle in our Graph... but here we have directed graph and it's complicated for me...

I can write code to clarify the reconvergence concept if you order so.

thank you for your time...regards

[lastchance]

Sledgehammer approach:

For each pair of nodes:
- Find a directed path from first to last (if one exists) - (stack + set?)
- Temporarily remove the edges making up this path (mark as unusable)
- Try again to find a directed path from first to last
End

[ETH11674]

could you please provide me a pseudo code? or a piece of code?
thanks in advance

[dhayden]

Do a depth search search of the graph.
- At each node, mark the edge that got you there. This lets you know that you've visited this node and the path that you took (by working backwards through the marked edges.
- If you get to a node and discover that it has already been visited, then you've discovered the reconvergent path. Tracing backward from the node gives you previously found path. Tracing backward from the current node (the one from which you just discovered the reconvergent path) gives you the other path.

[ETH11674]

@dhayden thanks for help

i did the followings

Graph.h

class AdjListNode
{
	int v;
	int weight;
	vector<float> weight_vec;

public:
	AdjListNode(int _v, int _w)
	{
		v = _v;
		weight = _w;
	}
	int vertex()
	{
		return v;
	}
	int gate_delay()
	{
		return weight;
	}

};

// Class to represent a graph using adjacency list representation
class Graph
{
	int V; // No. of vertices

public:

        Graph(int V); // Constructor
	
       // Pointer to an array containing adjacency lists
	list<AdjListNode> *adj;
	
        int getV() { return V; }
	

				  
	// functions to add an edge to graph
	void addEdge(int u, int v, int weight); // FAN_outs
	void AddEdge(int u, int v, int weight); // FAN_ins
	
	
	stack <int> FO_nodes(int v);
	
	// DFS traversal of the vertices
	// reachable from v
	void DFS(int v);



};

Graph.cpp

Graph::Graph(int V) // Constructor
{
	this->V = V;
	adj = new list<AdjListNode>[V];
}

void Graph::addEdge(int u, int v, int weight)
{
	AdjListNode node(v, weight);
	adj[u].push_back(node); // Add v to u’s list
}

void Graph::AddEdge(int u, int v, int weight)
{
	AdjListNode node(u, weight);
	adj[v].push_back(node); // Add v to u’s list
}

void Graph::DFS(int v)
{
	bool * visited = new bool[V];
	for (int i = 0; i < V; i++)
		visited[i] = false;
	visited[v] = true;

	if (v != 0)
	cout << "" << v << "-> ";

	list <AdjListNode>::iterator it;
	for (it = adj[v].begin(); it != adj[v].end(); ++it)
	{
		

		if (!visited[it->vertex()])
		{
			DFS(it->vertex());

		}

	}
}

and the main function:

int main()
{
Graph k(12);
        k.addEdge(0, 1, 0);
	k.addEdge(0, 2, 0);
	k.addEdge(0, 3, 0);
	k.addEdge(0, 4, 0);
	k.addEdge(0, 5, 0);
	k.addEdge(1, 6, 0);
	k.addEdge(3, 6, 1);
	k.addEdge(3, 7, 2);
	k.addEdge(4, 7, 3);
	k.addEdge(2, 8, 4);
	k.addEdge(7, 8, 5);
	k.addEdge(5, 9, 6);
	k.addEdge(7, 9, 7);
	k.addEdge(6, 10, 8);
	k.addEdge(8, 10, 9);
	k.addEdge(8, 11, 10);
	k.addEdge(9, 11, 11);

        g.DFS(3);

char z;
cin >> z;
return 0;
}

1) i know its a silly question but how to print out all the paths starting from node 3 like below:

        path[1] :V(3)-> V(6)-> V(10)
	path[2] :V(3)-> V(7)-> V(8)-> V(10)
	path[3] :V(3)-> V(7)-> V(8)-> V(11)	
	path[4] :V(3)-> V(7)-> V(9)-> V(11) 
        

so i could easily detect reconvergent paths (e.g. path[1] and path[2] are reconvergent)

the way i implemented shows like this:

DFS from V(3) : 3-> 6-> 10-> 7-> 8-> 10-> 11-> 9-> 11

2) is there any way to show what are the parents of each node with my graph structure
i mean for instance for V(7) the children are V(8), V(9),
and its parents are V(3), V(4)
my problem is when i print the adjacent nodes with V(7) its show the children nodes

this is why i define two methods "AddEdge(int, int, int)" and "addEdge(int, int, int)"
which the former construct the graph with Fan_ins and the latter with Fan_outs

any help would be appreciated...thank you
regards

[icy1]

1) i know its a silly question but how to print out all the paths starting from node 3 like below:

You wrote a recursive function. Come up with a base case, which should be at the start of the recursive function, that, for example, collects working paths once the goal is reached and returns. Perhaps there are also other base cases where you just return.

Later on you can examine what you've collected and print that out (or you can print it out as it's happening).