[PEP] NetworkX Graph Representation of Pyomo Model

[michaelbynum]

Summary

There are many applications in which it is useful to generate a graph representation of a pyomo model using NetworkX. It would be nice to have a single common function/module in Pyomo with this functionality that can be utilized for multiple applications. However, the desired API is not clear. The purpose of this PEP is to discuss the API.

The problem

The problem is that nodes in a NetworkX graph must be hashable. This motivates two potential solutions:

1. Create hashable wrappers for Pyomo components and use them as nodes in the NetworkX graph.
2. Use a hashable object (probably an int) as nodes and provide some sort of mapping from nodes to Pyomo components.

Solution 1: Hashable Wrappers

What it looks like

class HashableWrapper(object):
    def __init__(self, comp):
        self.comp = comp

    def __eq__(self, other):
        if type(other) is _CompNode:
            return self.comp is other.comp
        return False

    def __hash__(self):
        return hash(id(self.comp))


def graph_from_pyomo(m: _BlockData,
                     include_objective: bool = True,
                     active: bool = True) -> nx.Graph:
    graph = nx.Graph()

    for v in ComponentSet(m.component_data_objects(pe.Var, descend_into=True)):
        graph.add_node(HashableWrapper(v))

    for con in OrderedSet(m.component_data_objects(pe.Constraint, descend_into=True, active=active)):
        graph.add_node(HashableWrapper(con)) # This does not need the wrapper, but consistency is nice
        for v in identify_variables(con.body, include_fixed=True):
            graph.add_edge(HashableWrapper(con), HashableWrapper(v))

    if include_objective:
        for obj in ComponentSet(m.component_data_objects(pe.Objective, descend_into=True, active=active)):
            graph.add_node(HashableWrapper(obj))
            for v in identify_variables(obj.expr, include_fixed=True):
                graph.add_edge(HashableWrapper(obj), HashableWrapper(v))

    return graph

Example Usage

g = graph_from_pyomo(m)
for n1, n2 in graph.edges():
    n1.comp.pprint()

for v in m.component_data_objects(pe.Var):
    g.neighbors(HashableWrapper(v))

Pros

• Easy to use
• Only one object to worry about

Cons

• Needs a new object for every Pyomo component

Solution 2: Provide a mapping from nodes to Pyomo components

What it looks like

def graph_from_pyomo(m: _BlockData, include_objective: bool = True, active: bool = True) -> nx.Graph:
    graph = nx.Graph()

    ndx = 0
    comp_map = dict()
    rev_comp_map = ComponentMap()

    for v in ComponentSet(m.component_data_objects(pe.Var, descend_into=True)):
        graph.add_node(ndx)
        comp_map[ndx] = v
        rev_comp_map[v] = ndx
        ndx += 1

    for con in OrderedSet(m.component_data_objects(pe.Constraint, descend_into=True, active=active)):
        graph.add_node(ndx)
        comp_map[ndx] = con
        rev_comp_map[con] = ndx
        ndx += 1
        for v in identify_variables(con.body, include_fixed=True):
            graph.add_edge(rev_comp_map[con], rev_comp_map[v])

    if include_objective:
        for obj in ComponentSet(m.component_data_objects(pe.Objective, descend_into=True, active=active)):
            graph.add_node(ndx)
            comp_map[ndx] = obj
            rev_comp_map[obj] = ndx
            ndx += 1
            for v in identify_variables(obj.expr, include_fixed=True):
                graph.add_edge(rev_comp_map[obj], rev_comp_map[v])

    return graph, comp_map, rev_comp_map

Example Usage

g, cm, rcm = graph_from_pyomo(m)
for n1, n2 in graph.edges():
    cm[n1].pprint()

for v in m.component_data_objects(pe.Var):
    g.neighbors(rcm[v])

Pros

• Very simple (I like simple)
• Lightweight solution

Cons

• Working with the resulting graph is slightly more cumbersome

[DLWoodruff]

Either one seems like a good idea. My question (which really is a question) is: why is this a pep? Won't this be a utility that users choose to employ? In what ways would it impact anything for users who choose not to employ it?

[michaelbynum]

It is more of a design discussion than a PEP. I probably used the wrong label. It would not impact users who do not choose to employ it.

[bernalde]

Thank you Michael for putting this together. I think it is important to have this discussion based on the fact that both CommunityDetection and IncidenceAnalysis contrib packages are generating graphs from Pyomo models.
My vote between the two alternatives that you proposed would be for the second one, given the simplicity of the code and the fact that one can further work on the generated graph with the maps as a blueprint.

[Robbybp]

I like the second option too. A related question: Should we add all variables to the graph, or only variables that participate in (active) constraints/objectives?

[michaelbynum]

I agree with the second option.

@Robbybp I think that should be an option, but I'm not sure what the default should be.

[Robbybp]

Depends on if you want the model that will be seen by the solver, or the model as written, I guess. I usually want the model that will be seen by the solver, so I went with the variables-in-active-constraints approach for incidence analysis.

[bernalde]

I think there should be an option that defaults for only active components (as sometimes one can have a lot of inactive things in the model).
Alright, I think we have an agreement, so what should be the way forward? Have a single graph_from_pyomo(m) function that we can call from the other packages?