Help with graphs - breadth search

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

Answer 1

[Josh Meyer]

This example should be helpful:

http://www.mathworks.com/help/matlab/math/visualize-breadth-first-and-depth-first-search.html

Answer 2

[Christine Tobler]

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.