Difference between MultiDiGraph and DiGraph

Question

This post was originally posted to stackoverflow (https://stackoverflow.com/questions/57315017/best-way-to-include-weights-in-a-directed-acyclic-graph) sorry for long link, goo.gl was unable to shorten it.

Someone recommended I post it in this forum as it seemed more suitable.

I am working on my thesis, which consists of writing a Tabu Search algorithm to solve a Flexible Job Shop Problem. To solve this problem, I am using graphs as a problem/solution representation (the problem is an Undirected Graph, which must be turned into a Directed Acyclic Graph).

In short, I have a start (0) and end (*) node, which are 'dummy' operations whose weight/duration is 0. Nodes represent operations and paths represent the machines on which operations are processed, so the length of an edge (u,v) is the setup time incurred when swapping between operations u and v on a given machine. The weight of a node should be the processing time of that operation on the machine it's assigned. In a Directed Acyclic Graph, the length of the longest path from 0 to * represents the makespan (maximum production time) of the solution.

To implement this, I am using the networkx library. It's been going well, but I have come across some issues, namely when computing the makespan. First of all, since the functions I found (dag_longest_path() and dag_longest_path_length()) don't account for node weights, I transfered node weights to the edges preceding them. That seemed to solve the problem. However, I just noticed that these functions have different outputs in case the graph is either a DiGraph or a MultiDiGraph, as shown below.

Before presenting the code, forgive my noobness here, first time poster. The instance I am using consists of 30 operations and 8 machines, but for simplicity purposes I am presenting a simple example with 5 operations and 3 machines.

import networkx as nx

operations = (1,2,3,4,5)
G=nx.DiGraph()
G.add_node(0,pos=(0,0)) #starting node
G.add_node('*',pos=(1,0)) #end node

G.add_nodes_from(operations)

G.add_edge(0,1, weight = 500)
G.add_edge(1,2, weight = 200)
#these edges are for one machine

G.add_edge(0,3, weight = 150)
G.add_edge(3,4, weight = 177)

#these are for a second machine

G.add_edge(0,5, weight = 999)
#this edge is for the last machine

G.add_edge(2, '*', weight = 0)
G.add_edge(4, '*', weight = 0)
G.add_edge(5, '*', weight = 0)
#edges connecting final operation of each machine to the end node

print(nx.dag_longest_path(G))
print(nx.dag_longest_path_length(G))
#printing the longest path and corresponding length

The previous code outputs the following:

[0, 5]
999

This is sort of expected, as the path going through node 5 is indeed the longest path. However, it does not show the end node '*'.

If instead of G=nx.DiGraph() I do G=nx.MultiDiGraph(), the output is the following:

[0, 1, 2, '*']
3

Now the '*' node is included, rightfully so, but the path returned is the one with most nodes instead of the one with the longest edges.

What am I missing here? MultiDiGraph() seems to be the correct graph type here, as nodes 0 and '*' both have multiple edges leaving/entering them.

I need a way for the output to be:

[0, 5, '*']
999

Thank you in advance!

PS: feel free to correct any errors in formatting and presentation as this is my first post

Answer 1

The first way (with DiGraphs) is correct, but the two paths [0, 5] and [0, 5, '*'] both have the same (weighted) length, and the method just returns one of them. Which one depends on how your version of python orders dictionaries, but I think since vertex 5 appears first in the topological ordering it's rather likely to appear first.

You could hack it by making the edges into '*' have weight 1, then subtract that from the longest path length.

dag_longest_path doesn't appear to be built to work for MultiDiGraphs. For a vertex's predecessors' .items(), a DiGraph has just the dictionary of attributes, but the MultiDigraph has a dictionary of edge-attributes pairs. dag_longest_path doesn't try to take that into account, so never sees any weight attribute to use.