FOQUSGraph

(class from pyomo.network.foqus_graph)

class pyomo.network.foqus_graph.FOQUSGraph

Bases: object

__init__()

Methods

__init__()
adj_lists(G[, excludeEdges, nodes, multi])	Returns an adjacency list and a reverse adjacency list of node indexes for a MultiDiGraph.
all_cycles(G)	This function finds all the cycles in a directed graph.
calculation_order(G[, roots, nodes])	Rely on tree_order to return a calculation order of nodes
check_tear_set(G, tset)	Check whether the specified tear streams are sufficient.
cycle_edge_matrix(G)	Return a cycle-edge incidence matrix, a list of list of nodes in each cycle, and a list of list of edge indexes in each cycle.
scc_calculation_order(sccNodes, ie, oe)	This determines the order in which to do calculations for strongly connected components.
scc_collect(G[, excludeEdges])	This is an algorithm for finding strongly connected components (SCCs) in a graph.
select_tear_heuristic(G)	This finds optimal sets of tear edges based on two criteria.
solve_tear_direct(G, order, function, tears, ...)	Use direct substitution to solve tears.
solve_tear_wegstein(G, order, function, ...)	Use Wegstein to solve tears.
sub_graph_edges(G, nodes)	This function returns a list of edge indexes that are included in a subgraph given by a list of nodes.
tear_upper_bound(G)	This function quickly finds a sub-optimal set of tear edges.
tree_order(adj, adjR[, roots])	This function determines the ordering of nodes in a directed tree.

Member Documentation

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

Returns an adjacency list and a reverse adjacency list of node indexes for a MultiDiGraph.

Parameters:

• G – A networkx MultiDiGraph

• excludeEdges – List of edge indexes to ignore when considering neighbors

• nodes – List of nodes to form the adjacencies from

• multi – If True, adjacency lists will contains tuples of (node, key) for every edge between two nodes

Returns:

• i2n – Map from index to node for all nodes included in nodes

• adj – Adjacency list of successor indexes

• adjR – Reverse adjacency list of predecessor indexes

all_cycles(G)

This function finds all the cycles in a directed graph. The algorithm is based on Tarjan 1973 Enumeration of the elementary circuits of a directed graph, SIAM J. Comput. v3 n2 1973.

Returns:

• cycleNodes – List of lists of nodes in each cycle

• cycleEdges – List of lists of edge indexes in each cycle

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

Rely on tree_order to return a calculation order of nodes

Parameters:

• roots – List of nodes to consider as tree roots, if None then the actual roots are used

• nodes – Subset of nodes to consider in the tree, if None then all nodes are used

check_tear_set(G, tset)

Check whether the specified tear streams are sufficient. If the graph minus the tear edges is not a tree then the tear set is not sufficient to solve the graph.

cycle_edge_matrix(G)

Return a cycle-edge incidence matrix, a list of list of nodes in each cycle, and a list of list of edge indexes in each cycle.

scc_calculation_order(sccNodes, ie, oe)

This determines the order in which to do calculations for strongly connected components. It is used to help determine the most efficient order to solve tear streams to prevent extra iterations. This just makes an adjacency list with the SCCs as nodes and calls the tree order function.

Parameters:

• sccNodes – List of lists of nodes in each SCC

• ie – List of lists of in edge indexes to SCCs

• oe – List of lists of out edge indexes to SCCs

scc_collect(G, excludeEdges=None)

This is an algorithm for finding strongly connected components (SCCs) in a graph. It is based on Tarjan. 1972 Depth-First Search and Linear Graph Algorithms, SIAM J. Comput. v1 no. 2 1972

Returns:

• sccNodes – List of lists of nodes in each SCC

• sccEdges – List of lists of edge indexes in each SCC

• sccOrder – List of lists for order in which to calculate SCCs

• outEdges – List of lists of edge indexes leaving the SCC

select_tear_heuristic(G)

This finds optimal sets of tear edges based on two criteria. The primary objective is to minimize the maximum number of times any cycle is broken. The secondary criteria is to minimize the number of tears.

This function uses a branch and bound type approach.

Returns:

• tsets – List of lists of tear sets. All the tear sets returned are equally good. There are often a very large number of equally good tear sets.

• upperbound_loop – The max number of times any single loop is torn

• upperbound_total – The total number of loops

Improvements for the future

I think I can improve the efficiency of this, but it is good enough for now. Here are some ideas for improvement:

1. Reduce the number of redundant solutions. It is possible to find tears sets [1,2] and [2,1]. I eliminate redundant solutions from the results, but they can occur and it reduces efficiency.

2. Look at strongly connected components instead of whole graph. This would cut back on the size of graph we are looking at. The flowsheets are rarely one strongly connected component.

3. When you add an edge to a tear set you could reduce the size of the problem in the branch by only looking at strongly connected components with that edge removed.

4. This returns all equally good optimal tear sets. That may not really be necessary. For very large flowsheets, there could be an extremely large number of optimal tear edge sets.

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

Use direct substitution to solve tears. If multiple tears are given they are solved simultaneously.

Parameters:

• order – List of lists of order in which to calculate nodes

• tears – List of tear edge indexes

• iterLim – Limit on the number of iterations to run

• tol – Tolerance at which iteration can be stopped

Returns:

List of lists of diff history, differences between input and output values at each iteration

Return type:

list

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

Use Wegstein to solve tears. If multiple tears are given they are solved simultaneously.

Parameters:

• order – List of lists of order in which to calculate nodes

• tears – List of tear edge indexes

• iterLim – Limit on the number of iterations to run

• tol – Tolerance at which iteration can be stopped

• accel_min – Minimum value for Wegstein acceleration factor

• accel_max – Maximum value for Wegstein acceleration factor

• tol_type – Type of tolerance value, either “abs” (absolute) or “rel” (relative to current value)

Returns:

List of lists of diff history, differences between input and output values at each iteration

Return type:

list

sub_graph_edges(G, nodes)

This function returns a list of edge indexes that are included in a subgraph given by a list of nodes.

Returns:

• edges – List of edge indexes in the subgraph

• inEdges – List of edge indexes starting outside the subgraph and ending inside

• outEdges – List of edge indexes starting inside the subgraph and ending outside

tear_upper_bound(G)

This function quickly finds a sub-optimal set of tear edges. This serves as an initial upperbound when looking for an optimal tear set. Having an initial upper bound improves efficiency.

This works by constructing a search tree and just makes a tear set out of all the back edges.

tree_order(adj, adjR, roots=None)

This function determines the ordering of nodes in a directed tree. This is a generic function that can operate on any given tree represented by the adjaceny and reverse adjacency lists. If the adjacency list does not represent a tree the results are not valid.

In the returned order, it is sometimes possible for more than one node to be calculated at once. So a list of lists is returned by this function. These represent a bredth first search order of the tree. Following the order, all nodes that lead to a particular node will be visited before it.

Parameters:

• adj – An adjeceny list for a directed tree. This uses generic integer node indexes, not node names from the graph itself. This allows this to be used on sub-graphs and graps of components more easily.

• adjR – The reverse adjacency list coresponing to adj

• roots – List of node indexes to start from. These do not need to be the root nodes of the tree, in some cases like when a node changes the changes may only affect nodes reachable in the tree from the changed node, in the case that roots are supplied not all the nodes in the tree may appear in the ordering. If no roots are supplied, the roots of the tree are used.