greedy_search: Greedy search for bundled edges

In dSHARP-CMU/pathfinder: Topology Navigation And Manipulation Functions

Description

This strategy uses a greedy search along the original graph. It will navigate to a node tangent to the nearest edge bundle, cross that bundle, then find the next closest bundle, and so on, until at least one edge in each of the specified bundles has been visited.

Usage

greedy_search(graph, edge_bundles, distances, starting_point = 1,
  cheat = TRUE, quiet = !interactive())

Arguments

graph	An igraph object.
edge_bundles	A list of integer vectors. Each list item will be considered one edge bundle, and each vector the edge indices belonging to that bundle.
distances	Double. A vector of length ecount(graph) with the distances of each edge.
starting_point	Integer. Index of the point from which to start the search.
cheat	Boolean. If true, the search algorithm will temporarily treat the graph as undirected if it gets trapped behind a one-way edge, and try to restart its crawl.
quiet	Boolean. Display progress?

Details

The penalty function will make crossing any edge in an already-crossed bundle extremely unattractive to the pathfinding function. By setting the edge distance to a very high, but still finite, number, this will allow the path to cross and already-traversed edge bundle again if there are no other options available.

Value

A pathfinder_path object, which is a list with the following elements:

• epath: A list of integer vectors representing the successive edges crossed by the path

• bpath: A list of integer vectors representing the successive edge bundles crossed by the path

dSHARP-CMU/pathfinder documentation built on Sept. 11, 2019, 8:54 a.m.