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