EVOLUTION-MANAGER
Edit File: feedback_arc_set.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: Finding a feedback arc set in a graph</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="R.css" /> </head><body> <table width="100%" summary="page for feedback_arc_set {igraph}"><tr><td>feedback_arc_set {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Finding a feedback arc set in a graph</h2> <h3>Description</h3> <p>A feedback arc set of a graph is a subset of edges whose removal breaks all cycles in the graph. </p> <h3>Usage</h3> <pre> feedback_arc_set(graph, weights = NULL, algo = c("approx_eades", "exact_ip")) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph</p> </td></tr> <tr valign="top"><td><code>weights</code></td> <td> <p>Potential edge weights. If the graph has an edge attribute called ‘<code>weight</code>’, and this argument is <code>NULL</code>, then the edge attribute is used automatically. The goal of the feedback arc set problem is to find a feedback arc set with the smallest total weight.</p> </td></tr> <tr valign="top"><td><code>algo</code></td> <td> <p>Specifies the algorithm to use. “<code>exact_ip</code>” solves the feedback arc set problem with an exact integer programming algorithm that guarantees that the total weight of the removed edges is as small as possible. “<code>approx_eades</code>” uses a fast (linear-time) approximation algorithm from Eades, Lin and Smyth. “<code>exact</code>” is an alias to “<code>exact_ip</code>” while “<code>approx</code>” is an alias to “<code>approx_eades</code>”.</p> </td></tr> </table> <h3>Details</h3> <p>Feedback arc sets are typically used in directed graphs. The removal of a feedback arc set of a directed graph ensures that the remaining graph is a directed acyclic graph (DAG). For undirected graphs, the removal of a feedback arc set ensures that the remaining graph is a forest (i.e. every connected component is a tree). </p> <h3>Value</h3> <p>An edge sequence (by default, but see the <code>return.vs.es</code> option of <code><a href="igraph_options.html">igraph_options</a></code>) containing the feedback arc set. </p> <h3>References</h3> <p>Peter Eades, Xuemin Lin and W.F.Smyth: A fast and effective heuristic for the feedback arc set problem. <em>Information Processing Letters</em> 47:6, pp. 319-323, 1993 </p> <h3>Examples</h3> <pre> g <- sample_gnm(20, 40, directed=TRUE) feedback_arc_set(g) feedback_arc_set(g, algo="approx") </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>