FOQUS图

(类来自 pyomo.network.foqus_graph)

class pyomo.network.foqus_graph.FOQUSGraph

基础类：object

__init__()

方法

__init__()
adj_lists(G[, excludeEdges, nodes, multi])	返回一个MultiDiGraph的节点索引的邻接列表和反向邻接列表。
all_cycles(G)	此函数查找有向图中的所有循环。
calculation_order(G[, roots, nodes])	依赖tree_order返回节点的计算顺序
check_tear_set(G, tset)	检查指定的撕裂流是否足够。
cycle_edge_matrix(G)	返回一个循环-边关联矩阵，每个循环中的节点列表的列表，以及每个循环中的边索引列表的列表。
scc_calculation_order(sccNodes, ie, oe)	这决定了计算强连通组件的顺序。
scc_collect(G[, excludeEdges])	这是一个用于在图中找到强连通分量（SCCs）的算法。
select_tear_heuristic(G)	这基于两个标准找到了最佳的撕裂边缘集。
solve_tear_direct(G, order, function, tears, ...)	使用直接代入法来解决眼泪。
solve_tear_wegstein(G, order, function, ...)	使用Wegstein方法解决撕裂问题。
sub_graph_edges(G, nodes)	此函数返回包含在由节点列表给出的子图中的边的索引列表。
tear_upper_bound(G)	此函数快速找到一组次优的撕裂边。
tree_order(adj, adjR[, roots])	此函数确定有向树中节点的排序。

成员文档

adj_lists(G, excludeEdges=None, nodes=None, multi=False)

返回一个MultiDiGraph的节点索引的邻接列表和反向邻接列表。

Parameters:

• G – 一个 networkx 的 MultiDiGraph

• excludeEdges – 在考虑邻居时忽略的边索引列表

• nodes – 用于形成邻接关系的节点列表

• multi – 如果为True，邻接列表将包含两个节点之间每条边的（节点，键）元组

Returns:

• i2n – 从索引到节点的映射，包含所有节点

• adj – 后继索引的邻接列表

• adjR – 前驱索引的反向邻接列表

all_cycles(G)

此函数用于查找有向图中的所有循环。 该算法基于Tarjan 1973年的论文《有向图的基本回路枚举》，SIAM J. Comput. v3 n2 1973。

Returns:

• cycleNodes – 每个循环中节点的列表

• cycleEdges – 每个循环中边索引的列表

calculation_order(G, roots=None, nodes=None)

依赖tree_order返回节点的计算顺序

Parameters:

• roots – 被视为树根的节点列表，如果为None，则使用实际的根节点

• nodes – 树中要考虑的节点子集，如果为None，则使用所有节点

check_tear_set(G, tset)

检查指定的撕裂流是否足够。 如果图减去撕裂边后不是一棵树，则 撕裂集不足以解决该图。

cycle_edge_matrix(G)

返回一个循环-边关联矩阵，每个循环中的节点列表，以及每个循环中的边索引列表。

scc_calculation_order(sccNodes, ie, oe)

这决定了强连通分量的计算顺序。它用于帮助确定解决撕裂流的最有效顺序，以防止额外的迭代。这只是将强连通分量作为节点制作一个邻接表，并调用树顺序函数。

Parameters:

• sccNodes – 每个强连通分量（SCC）中的节点列表的列表

• ie – 指向强连通分量（SCCs）的入边索引列表的列表

• oe – 指向强连通分量（SCCs）的外边索引的列表的列表

scc_collect(G, excludeEdges=None)

这是一个用于在图中寻找强连通分量（SCCs）的算法。它基于Tarjan。1972年的深度优先搜索和线性图算法，SIAM J. Comput. v1 no. 2 1972

Returns:

• sccNodes – 每个SCC中节点的列表的列表

• sccEdges – 每个SCC中边索引的列表的列表

• sccOrder – 计算SCC的顺序的列表的列表

• outEdges – 离开SCC的边索引的列表的列表

select_tear_heuristic(G)

这基于两个标准找到最佳的撕裂边集。 主要目标是最小化任何循环被打破的最大次数。 次要标准是最小化撕裂的数量。

此函数使用分支定界类型的方法。

Returns:

• tsets – 撕裂集合的列表的列表。返回的所有撕裂集合都是同样好的。通常有大量同样好的撕裂集合。

• upperbound_loop – 任何单个循环被撕裂的最大次数

• upperbound_total – 循环的总数

未来的改进

我认为我可以提高这个的效率，但目前来说已经足够好了。以下是一些改进的想法：

1. 减少冗余解决方案的数量。可能会找到集合 [1,2] 和 [2,1]。我从结果中消除了冗余解决方案，但它们可能会出现，这会降低效率。

2. 查看强连通组件而不是整个图。这将减少我们正在查看的图的大小。流程图很少是一个强连通组件。

3. 当你向一个撕裂集添加一条边时，你可以通过仅查看移除该边后的强连通组件来减少分支中的问题规模。

4. 这将返回所有同样好的最优撕裂集。这可能并不是真正必要的。对于非常大的流程图，可能存在极大量的最优撕裂边集。

solve_tear_direct(G, order, function, tears, outEdges, iterLim, tol, tol_type, report_diffs)

使用直接代入法来解决眼泪。如果给出了多个眼泪，它们将同时被解决。

Parameters:

• order – 计算节点的顺序列表的列表

• tears – 撕裂边缘索引列表

• iterLim – 运行迭代次数的限制

• tol – 迭代可以停止的容差

Returns:

差异历史记录的列表列表，每次迭代时输入和输出值之间的差异

Return type:

list

solve_tear_wegstein(G, order, function, tears, outEdges, iterLim, tol, tol_type, report_diffs, accel_min, accel_max)

使用Wegstein方法解决撕裂问题。如果给出多个撕裂，它们将同时被解决。

Parameters:

• order – 计算节点的顺序列表的列表

• tears – 撕裂边缘索引列表

• iterLim – 运行迭代次数的限制

• tol – 迭代可以停止的容差

• accel_min – Wegstein加速因子的最小值

• accel_max – Wegstein加速因子的最大值

• tol_type – 容差值的类型，可以是“abs”（绝对）或“rel”（相对于当前值）

Returns:

差异历史记录的列表列表，每次迭代时输入和输出值之间的差异

Return type:

list

sub_graph_edges(G, nodes)

此函数返回由节点列表给出的子图中包含的边索引列表。

Returns:

• edges – 子图中的边索引列表

• inEdges – 从子图外部开始并在子图内部结束的边索引列表

• outEdges – 从子图内部开始并在子图外部结束的边索引列表

tear_upper_bound(G)

此函数快速找到一组次优的撕裂边。这在寻找最优撕裂集时作为初始上限。拥有初始上限可以提高效率。

这是通过构建一个搜索树并仅从所有后边中制作一个撕裂集来实现的。

tree_order(adj, adjR, roots=None)

此函数确定有向树中节点的顺序。这是一个通用函数，可以操作由邻接表和反向邻接列表表示的任何给定树。如果邻接列表不表示树，则结果无效。

在返回的顺序中，有时可以同时计算多个节点。因此，此函数返回一个列表的列表。这些列表表示树的广度优先搜索顺序。按照这个顺序，所有导致特定节点的节点将在它之前被访问。

Parameters:

• adj – 一个有向树的邻接表。这里使用的是通用的整数节点索引，而不是图本身的节点名称。这使得它可以更容易地用于子图和组件的图。

• adjR – 与adj对应的反向邻接表

• roots – 起始节点的索引列表。这些节点不一定是树的根节点，在某些情况下，比如当一个节点发生变化时，变化可能只影响从该节点可达的树中的节点，如果提供了根节点，树中的所有节点可能不会出现在排序中。如果没有提供根节点，则使用树的根节点。