Skip to content

Handling graphs with flows / weights on nodes

If your graph has flow values or weights associated with the nodes, instead of the edges, we provide a simple way to handle them, via the class NodeExpandedDiGraph, as described below.

See this example on how to correct weights on node-weighted graphs, support subpath constraints, and then apply Minimum Flow Decomposition on them.

NodeExpandedDiGraph 

NodeExpandedDiGraph(
    G: DiGraph,
    node_flow_attr: str,
    try_filling_in_missing_flow_attr: bool = False,
    node_length_attr: str = None,
)

Bases: DiGraph

This class is a subclass of the networkx DiGraph class. It is used to represent a directed graph where all nodes v have been “expanded” or “subdivided” into an edge (v.0, v.1). This is useful for representing graphs where the flow values, or weights, are associated with the nodes, rather than the edges. These expanded edges are then added to the edges_to_ignore list, available as a property of this class.

Using this class

  • Create a NodeExpandedDiGraph object by passing a directed graph G and the attribute name node_flow_attr from where to get the flow values / weights on the nodes.
  • Pass the edges from the edges_to_ignore attribute of this class to the decomposition models, in order to ignore all original edges of the graph, and thus consider in the constraints only the new edges added in the expanded graph (which have flow values).
  • Solve the decomposition model on the expanded graph.
  • Use the condense_paths method to condense the solution paths (which are in the expanded graph) to paths in the original graph.

Parameters

  • G : nx.DiGraph

    The input directed graph, as networkx DiGraph.

  • node_flow_attr : str

    The attribute name from where to get the flow values / weights on the nodes. This attribute for each v is then set to the edge (v.0, v.1) connecting the new expanded nodes. This attribute can be missing from some nodes of the graph, in which case the edge (v.0, v.1) is added to edges_to_ignore.

  • try_filling_in_missing_flow_attr : bool, optional

    If True, try filling in missing flow values in the expanded graph (i.e., if some original edge does not have the attribute specified by node_flow_attr), by setting them to the flow values of a flow between the sources and the sinks of the original graph, such that for every edge where node_flow_attr is present, the demand and capacity are equal to the value specified by node_flow_attr. Default is False.

  • node_length_attr : str, optional

    The attribute name from where to get the length values on the nodes. Default is None. If you specify this attribute, it may be missing from some nodes of the graph.

Example

import flowpaths as fp
import networkx as nx

graph = nx.DiGraph()
graph.add_node("s", flow=13)
graph.add_node("a", flow=6)
graph.add_node("b", flow=9)
graph.add_node("c", flow=13)
graph.add_node("d", flow=6)
graph.add_node("t", flow=13)

# Adding edges
graph.add_edges_from([("s", "a"), ("s", "b"), ("a", "b"), ("a", "c"), ("b", "c"), ("c", "d"), ("c", "t"), ("d", "t")])

# Expand the graph
ne_graph = fp.NodeExpandedDiGraph(graph, node_flow_attr="flow")

# Solve the problem on the expanded graph
mfd_model = fp.MinFlowDecomp(
    ne_graph, 
    flow_attr="flow",
    edges_to_ignore=ne_graph.edges_to_ignore,
    )
mfd_model.solve()

if mfd_model.is_solved():
    # Getting the solution in the expanded graph
    solution = mfd_model.get_solution()
    # Condensing the paths in the expanded graph to paths in the the original graph
    original_paths = ne_graph.get_condensed_paths(solution["paths"])
    print("Original paths:", original_paths)
    print("Weights:", solution["weights"])
Source code in flowpaths/nodeexpandeddigraph.py 
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
def __init__(
        self,
        G: nx.DiGraph,
        node_flow_attr: str,
        try_filling_in_missing_flow_attr: bool = False,
        node_length_attr: str = None,
        ):
    """
    This class is a subclass of the networkx DiGraph class. It is used to represent a directed graph
    where all nodes `v` have been "expanded" or "subdivided" into an edge `(v.0, v.1)`. This is useful for representing
    graphs where the flow values, or weights, are associated with the nodes, rather than the edges. 
    These expanded edges are then added to the `edges_to_ignore` list, available as a property of this class.

    !!! info "Using this class"

        - Create a `NodeExpandedDiGraph` object by passing a directed graph `G` and the attribute name `node_flow_attr` from where to get the flow values / weights on the nodes.
        - Pass the edges from the `edges_to_ignore` attribute of this class to the decomposition models, in order to ignore all original edges of the graph,
          and thus consider in the constraints only the new edges added in the expanded graph (which have flow values).
        - Solve the decomposition model on the expanded graph.
        - Use the `condense_paths` method to condense the solution paths (which are in the expanded graph) to paths in the original graph.

    Parameters
    ----------
    - `G : nx.DiGraph`

        The input directed graph, as networkx DiGraph.

    - `node_flow_attr : str`

        The attribute name from where to get the flow values / weights on the nodes. 
        This attribute for each `v` is then set to the edge `(v.0, v.1)` connecting the new expanded nodes.
        This attribute can be missing from some nodes of the graph, in which case 
        the edge `(v.0, v.1)` is added to `edges_to_ignore`.

    - `try_filling_in_missing_flow_attr : bool`, optional

        If `True`, try filling in missing flow values in the expanded graph (i.e., if some original edge does not have the attribute specified by `node_flow_attr`), 
        by setting them to the flow values of a flow between the sources and the sinks of the original graph, such that for every edge where `node_flow_attr` is present,
        the demand and capacity are equal to the value specified by `node_flow_attr`.
        Default is `False`.

    - `node_length_attr : str`, optional

        The attribute name from where to get the length values on the nodes. Default is `None`. 
        If you specify this attribute, it may be missing from some nodes of the graph.

    !!! example "Example"

        ```python
        import flowpaths as fp
        import networkx as nx

        graph = nx.DiGraph()
        graph.add_node("s", flow=13)
        graph.add_node("a", flow=6)
        graph.add_node("b", flow=9)
        graph.add_node("c", flow=13)
        graph.add_node("d", flow=6)
        graph.add_node("t", flow=13)

        # Adding edges
        graph.add_edges_from([("s", "a"), ("s", "b"), ("a", "b"), ("a", "c"), ("b", "c"), ("c", "d"), ("c", "t"), ("d", "t")])

        # Expand the graph
        ne_graph = fp.NodeExpandedDiGraph(graph, node_flow_attr="flow")

        # Solve the problem on the expanded graph
        mfd_model = fp.MinFlowDecomp(
            ne_graph, 
            flow_attr="flow",
            edges_to_ignore=ne_graph.edges_to_ignore,
            )
        mfd_model.solve()

        if mfd_model.is_solved():
            # Getting the solution in the expanded graph
            solution = mfd_model.get_solution()
            # Condensing the paths in the expanded graph to paths in the the original graph
            original_paths = ne_graph.get_condensed_paths(solution["paths"])
            print("Original paths:", original_paths)
            print("Weights:", solution["weights"])
        ```
    """
    super().__init__()

    if not all(isinstance(node, str) for node in G.nodes()):
        utils.logger.error(f"{__name__}: Graph id {utils.fpid(G)}: every node of the graph must be a string.")
        raise ValueError("Every node of the graph must be a string.")
    # # if not all nodes have the flow attribute, raise an error
    # if not all(node_flow_attr in G.nodes[node] for node in G.nodes()):
    #     raise ValueError(f"Every node must have the flow attribute specified as `node_flow_attr` ({node_flow_attr}).")

    self.original_G = nx.DiGraph(G)

    if "id" in G.graph:
        self.graph["id"] = G.graph["id"]

    self.node_flow_attr = node_flow_attr
    self.__edges_to_ignore = []

    for node in G.nodes:
        node0 = node + '.0'
        node1 = node + '.1'
        self.add_node(node0, **G.nodes[node])
        self.add_node(node1, **G.nodes[node])
        self.add_edge(node0, node1, **G.nodes[node])
        if node_flow_attr in G.nodes[node]:
            self[node0][node1][node_flow_attr] = G.nodes[node][node_flow_attr]
        else:
            self.__edges_to_ignore.append((node0, node1))
        if node_length_attr is not None:
            if node_length_attr in G.nodes[node]:
                self[node0][node1][node_length_attr] = G.nodes[node][node_length_attr]

        # Adding in-coming edges
        for pred in G.predecessors(node):
            pred1 = pred + '.1'
            self.add_edge(pred1, node0, **G.edges[pred, node])
            self.__edges_to_ignore.append((pred1, node0))

            # If the edge (pred,node) does not have the length attribute, set it to 0
            if node_length_attr is not None:
                if node_length_attr not in G.edges[pred, node]:
                    self[pred1][node0][node_length_attr] = 0

        # Adding out-going edges
        for succ in G.successors(node):
            succ0 = succ + '.0'
            self.add_edge(node1, succ0, **G.edges[node, succ])
            # This is not necessary, as the edge (node1, succ0) has already been added above, for succ
            # self.__edges_to_ignore.append((node1, succ0))

    if try_filling_in_missing_flow_attr:
        self.__try_filling_in_missing_flow_values()

    nx.freeze(self)

edges_to_ignore property 

edges_to_ignore

List of edges to ignore when solving the decomposition model on the expanded graph.

These are the edges of the original graph, since only the new edges that have been introduced for every node must considered in the decomposition model, with flow value from the node attribute node_flow_attr.

get_condensed_paths 

get_condensed_paths(paths)

Condense a list of paths from the expanded graph to the original graph.

This assumes that:

  • The nodes in the expanded graph are named as ‘node.0’ and ‘node.1’, where ‘node’ is the name of the node in the original graph.
  • The paths are lists of nodes in the expanded graph, where the nodes are ordered as ‘nodeA.0’, ‘nodeA.1’, ‘nodeB.0’, ‘nodeB.1’, etc. Meaning that we always have two nodes from the same original node in sequence.
Parameters

  • paths : list

    List of paths in the expanded graph.

Returns

  • condensed_paths: list

    List of paths in the original graph.

Raises

  • ValueError

    • If the node names in the expanded_path on even positions (starting from 0) do not end with .0.
    • If these node names (with the suffix .0 removed) are not in the original graph.
Source code in flowpaths/nodeexpandeddigraph.py 
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
def get_condensed_paths(self, paths):
    """
    Condense a list of paths from the expanded graph to the original graph. 

    This assumes that:

    - The nodes in the expanded graph are named as 'node.0' and 'node.1', where 'node' is the name of the node in the
    original graph. 
    - The paths are lists of nodes in the expanded graph, where the nodes are ordered as 'nodeA.0', 'nodeA.1', 'nodeB.0', 'nodeB.1', etc.
    Meaning that we always have two nodes from the same original node in sequence.

    Parameters
    ----------
    - `paths : list`

        List of paths in the expanded graph.

    Returns
    -------
    - `condensed_paths: list`

        List of paths in the original graph.

    Raises
    ------
    - `ValueError`

        - If the node names in the expanded_path on even positions (starting from 0) do not end with `.0`.
        - If these node names (with the suffix `.0` removed) are not in the original graph.
    """

    condensed_paths = []
    for path in paths:
        condensed_path = []
        for i in range(0, len(path) - 1, 2):
            # Raise an error if the last two symbols of path[i] are not '.0'
            if path[i][-2:] != '.0':
                utils.logger.error(f"{__name__}: Invalid node name in path: {path[i]}")
                raise ValueError(f"Invalid node name in path: {path[i]}")
            node = path[i][:-2]
            if node not in self.original_G.nodes:
                utils.logger.error(f"{__name__}: Node {node} not in the original graph.")
                raise ValueError(f"Node {node} not in the original graph.")
            condensed_path.append(node)
        condensed_paths.append(condensed_path)
    return condensed_paths

get_expanded_edge 

get_expanded_edge(node)

Get the the expanded edge ('node.0', 'node.1') for a given node node in the original graph.

Source code in flowpaths/nodeexpandeddigraph.py 
311
312
313
314
315
316
317
318
319
320
def get_expanded_edge(self, node):
    """
    Get the the expanded edge `('node.0', 'node.1')` for a given node `node` in the original graph.
    """

    if node not in self.original_G.nodes:
        utils.logger.error(f"{__name__}: Node {node} not in the original graph.")
        raise ValueError(f"Node {node} not in the original graph.")

    return (node + '.0', node + '.1')

get_expanded_subpath_constraints 

get_expanded_subpath_constraints(
    subpath_constraints,
)

Expand a list of subpath constraints from the original graph (where every constraint is a list nodes or edges in the original graph) to a list of subpath constraints in the expanded graph (where every constraint is a list of edges in the expanded graph).

  • If the constraints are lists of nodes, then the corresponding edges are of type ('node.0', 'node.1')
  • If the constraints are lists of edges of the form (u,v), then the corresponding edges are of type ('u.1', 'v.0')
Parameters

  • subpath_constraints : list

    List of subpath constraints in the original graph.

Returns

  • expanded_constraints : list

    List of subpath constraints in the expanded graph.

Source code in flowpaths/nodeexpandeddigraph.py 
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
def get_expanded_subpath_constraints(self, subpath_constraints):
    """
    Expand a list of subpath constraints from the original graph (where every constraint is a list **nodes** or **edges**
    in the original graph) to a list of subpath constraints in the expanded graph (where every constraint 
    is a list of edges in the expanded graph). 

    - If the constraints are lists of nodes, then the corresponding edges are of type `('node.0', 'node.1')` 
    - If the constraints are lists of edges of the form `(u,v)`, then the corresponding edges are of type `('u.1', 'v.0')`

    Parameters
    ----------
    - `subpath_constraints : list`

        List of subpath constraints in the original graph.

    Returns
    -------
    - `expanded_constraints : list`

        List of subpath constraints in the expanded graph.
    """

    # Check if the subpath constraints are lists of node or lists of edges,
    # and expand them accordingly, using the two functions already implemented.

    if not isinstance(subpath_constraints, list):
        utils.logger.error(f"{__name__}: Subpath constraints must be a list.")
        raise ValueError("Subpath constraints must be a list.")
    if not all(isinstance(constraint, list) for constraint in subpath_constraints):
        utils.logger.error(f"{__name__}: Subpath constraints must be a list of lists.")
        raise ValueError("Subpath constraints must be a list of lists.")

    if len(subpath_constraints) == 0:
        return []

    if isinstance(subpath_constraints[0][0], str):
        return self.__get_expanded_subpath_constraints_nodes(subpath_constraints)
    elif isinstance(subpath_constraints[0][0], tuple):
        return self.__get_expanded_subpath_constraints_edges(subpath_constraints)
    else:
        utils.logger.error(f"{__name__}: Subpath constraints must be a list of lists of nodes or edges.")
        raise ValueError("Subpath constraints must be a list of lists of nodes or edges.")