Help with graphs - breadth search
3 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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
0 comentarios
Respuestas (2)
Christine Tobler
el 1 de Ag. de 2017
Editada: Christine Tobler
el 1 de Ag. de 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.
0 comentarios
Ver también
Categorías
Más información sobre Graph and Network Algorithms en Help Center y File Exchange.
Productos
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!