Help with graphs - breadth search

1 view (last 30 days)
Sofia Melo Vasconcellos
Sofia Melo Vasconcellos on 14 May 2017
Edited: Christine Tobler on 1 Aug 2017
Hello I need help to traverse a graph using Breadth-first graph search, so that the following conditions are met:   The vertices are initialized with 1 unit of water and the processing begins at a vertex v whose degree of entry is 0. This vertex is marked as visited and, assuming v directs the flow to vertex u, then the vertex flow v is added to the current stream of vertex u. In addition, the edge connecting vertex v to vertex u is removed thereby reducing the degree of input of vertex u - this vertex u will be processed (visited) when its degree of input becomes 0.
Would anyone help me? Thank you from now

Answers (2)

Josh Meyer
Josh Meyer on 1 Aug 2017

Christine Tobler
Christine Tobler on 1 Aug 2017
Edited: Christine Tobler on 1 Aug 2017
This should be possible using the digraph object. Since you are modifying the graph, it may be best to write a for-loop that will search for a node with indegree 0 (no incoming edges), modify the weight of the succeeding nodes, and so on. Here's a simple example
g = digraph(triu(bucky)); % Example digraph
g.Nodes.Water = ones(numnodes(g), 1);
while any(indegree(g) == 0 & outdegree(g) > 0)
v = find(indegree(g) == 0 & outdegree(g) > 0, 1);
u = successors(g, v); % This could be more than one node.
g.Nodes.Water(u) = g.Nodes.Water(u) + g.Nodes.Water(v) / length(u); % splitting up the water
g = rmedge(g, v, u);
end
This will do what I think you were describing. However, it may not be the most efficient, because removing edges from a graph one at a time in a loop can be very expensive. It may be cheaper to save the vectors outdegree and indegree, and update these vectors when removing the edges instead of actually modifying the graph. This should be considerably faster.
Also, your algorithm is based on the assumption that the digraph does not contain a cycle - otherwise, it will be caught in an endless loop.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!