How to add zero-cost pseudonode in a DAG with multiple entry and exit nodes?

Question

For the directed acyclic given by the following python code, I am unable to add a pseudo-entry and pseudo-exit node such that there won't be more than one entry/exit nodes.

import queue 
# A class to represent a graph object
class Graph:
    # Constructor to construct a graph
    def __init__(self, edges, n):
        # A list of lists to represent an adjacency list
        self.adjList = [None] * n
        
        # allocate memory for the adjacency list
        for i in range(n):
            self.adjList[i] = []
        # add edges to the directed graph
        for (src, dest, weight) in edges:
            # allocate node in adjacency list from src to dest
            self.adjList[src].append((dest, weight))

# Function to print adjacency list representation of a graph
def printGraph(graph,n):
    for src in range(len(graph.adjList)):
        # print current vertex and all its neighboring vertices
        for (dest, weight) in graph.adjList[src]:
            new_graph[src].append(dest)
            print(f'({src} —> {dest}, {weight}) ', end='')
        print()
# construct a graph from a given list of edges
graph = Graph(data.edges, data.tasks)
new_graph = [[] for i in range(data.tasks)]

Restating the objective, for the graph having multiple entry and exit nodes how do I add a zero-cost pseudo-entry/exit node such that there is only one entry/exit node in the graph. The following figures shows an example of a graph having multiple entry nodes(T1 and T2) and multiple exit nodes(T9 and T16), Tentry is a zero-cost pseudo-entry node and Texit is a zero-cost pseudo-entry/exit node. Any help would be appreciated!

Answer 1

I would suggest trying networkx. Here's an example of how to create your graph and bit of how to draw it.

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

N = 18

# Create adjacency matrix with edge weigths
# -1 means no edge
A = -1 * np.ones((N, N))
A[ 0,  1] = 0
A[ 0,  2] = 0
A[ 1,  3] = 8
A[ 1,  4] = 5
A[ 1,  5] = 6
A[ 2,  6] = 1
A[ 2,  7] = 1
A[ 2,  8] = 4
A[ 3,  9] = 7
A[ 3, 10] = 8
A[ 4,  9] = 7
A[ 4, 11] = 3
A[ 5,  9] = 9
A[ 5, 12] = 4
A[ 6,  9] = 5
A[ 6, 13] = 8
A[ 7,  9] = 7
A[ 7, 14] = 3
A[ 8,  9] = 6
A[ 8, 15] = 7
A[ 9, 17] = 0
A[10, 16] = 1
A[11, 16] = 2
A[12, 16] = 1
A[13, 16] = 1
A[14, 16] = 3
A[15, 16] = 3
A[16, 17] = 0


# for plotting to see what we're doing
dx = 1
dy = 1

pos = [[0, 0],
       [-2 * dx, -dy],
       [2 * dx, -dy],
       [-3 * dx, -2 * dy],
       [-2 * dx, -2 * dy],
       [-dx, -2 * dy],
       [dx, -2 * dy],
       [2 * dx, -2 * dy],
       [3 * dx, -2 * dy],
       [0, -3 * dy],
       [-3 * dx, - 3 * dy],
       [-2 * dx, - 3 * dy],
       [-1 * dx, - 3 * dy],
       [dx, - 3 * dy],
       [2 * dx, - 3 * dy],
       [3 * dx, - 3 * dy],
       [0, - 4 * dy],
       [0, - 5 * dy]]

colors = ['tan',
          'thistle', 'thistle',
          'lightskyblue', 'lightskyblue', 'lightskyblue',
          'lightskyblue', 'lightskyblue', 'lightskyblue',
          'orchid',
          'orange', 'orange', 'orange',
          'orange', 'orange', 'orange',
          'yellowgreen',
          'tan']


G = nx.DiGraph()
for n in range(N):
    if n == 0:
        l = "$\mathregular{T_{entry}}$"
    elif n == N-1:
        l = "$\mathregular{T_{exit}}$"
    else:
        l = "$\mathregular{T_{" + str(n) + "}}$"
    G.add_node(n, label = l, position = pos[n], color = colors[n])


for i in range(N):
    for j in range(N):
        if A[i,j] >= 0:
            G.add_edge(i, j, weight = int(A[i,j]))
    
edge_labels = nx.get_edge_attributes(G, 'weight')
node_labels = nx.get_node_attributes(G, 'label')
node_colors = nx.get_node_attributes(G, 'color')
node_positions = nx.get_node_attributes(G, 'position')

nx.draw(G, node_positions, node_size = 1000, node_color = colors, labels = node_labels, with_labels = True)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)