CODEWITHSUNDEEP
algorithmloopssortinggraph
Elle
Elle

Reputation: 334

Topological sort with loops

I'm writing a simple digital simulator for combinatory and sequential circuits and I've chosen a graph approach for modelling this problem.

If the circuit have no loops, I can represent it as a DAG. In this case, I can think of at least two ways to perform a simulation: recursively, going from the outputs backwards or toposorting the graph.

The problem comes when a loop exists as I can't sort nodes anymore, but since a circuit is a directed graph whose edges go from inputs to outputs in only one direction, loops are the only edges "going back".

Hence, with these restrictions, I was looking for a way to perform topological sort "ignoring loops" given the adjacency list.

Here's my idea: if I menage to sort the components regardless of loops, I can simply evaluate loop drivers first and then simulate like if no loops existed. This approach works fine when I solve logic circuits by hand.

In other words, I'd like to somewhat sort the graph pretending that back edges don't exist (hence I have a DAG). Is there a way to do this?

EDIT: take a look at the following picture. enter image description here Here's the adjacency list corresponding to that circuit:

n -> XNOR
m -> AND
AND -> NOT
NOT -> NAND
NAND -> D-FLIPFLOP
XNOR -> NAND
D-FLIPFLOP-> x, AND, XNOR
x ->

The toposort i'd like to obtain is (for example) this one: 

m AND NOT n XNOR NAND D-FLIPFLOP x

ignoring the two loops

D-FLIPFLOP -> AND
D-FLIPFLOP -> XNOR

Upvotes: 2

Views: 1356

Answers (1)

Magma
Magma

Reputation: 586

It seems you're interested in the problem of finding a small feedback arc set. The problem of finding a smallest such set is NP-hard in general, but there's a fast algorithm with decent approximate results by Eades, Lin and Smyth linked in the answer to this question. I'll repeat it here. The goal of the algorithm is to find an ordering of the edges such that relatively few edges run opposite to that ordering, which is also what you're interested in.

  1. You have your graph, a left stack (initially empty), and a right stack (also initially empty).
  2. While the graph has a source (a vertex without incoming edges):
    • Choose a source, disconnect it from the graph and place it on top of the left stack.
  3. While the graph has a sink (a vertex without outgoing edges):
    • Choose a sink, disconnect it from the graph and place it on top of the right stack.
  4. If the graph is not empty:
    • Choose a vertex of the graph such that the number of outgoing edges minus the number of incoming edges is as large as possible.
    • Disconnect that vertex from the graph and place it on top of the left stack.
    • Go to 1.
  5. Take the left stack, flip it and place it on top of the right stack. The right stack, from top to bottom, is the desired ordering.

Upvotes: 3

Related Questions