Priorities.h File Reference

Graph algorithms for topological priority assignment and cycle detection. More...

#include <algorithm>
#include <QHash>
#include <QSet>
#include <QStack>
#include <QVector>

Include dependency graph for Priorities.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	PrioritiesInternal

Functions
template<typename T>
void	calculatePriorities (const QVector< T * > &elements, const QHash< T *, QVector< T * > > &successors, QHash< T *, int > &outPriorities)
	Priority calculation for directed graphs.
template<typename T>
QSet< T * >	findFeedbackNodes (const QVector< T * > &elements, const QHash< T *, QVector< T * > > &successors)
	Finds all nodes that participate in feedback loops (cycles).
template<typename T>
void	PrioritiesInternal::legacyCalculatePriorities (const QVector< T * > &elements, const QHash< T *, QVector< T * > > &successors, QHash< T *, int > &outPriorities)
	Legacy iterative DFS priority calculation, used for cyclic graphs only.

Detailed Description

Graph algorithms for topological priority assignment and cycle detection.

Definition in file Priorities.h.

Function Documentation

calculatePriorities()

template<typename T>

void calculatePriorities	(	const QVector< T * > &	elements,
		const QHash< T *, QVector< T * > > &	successors,
		QHash< T *, int > &	outPriorities )

Priority calculation for directed graphs.

Assigns each node a priority equal to its longest path to a sink plus one; higher priority evaluates first (sources before sinks), so every element sees up-to-date predecessor outputs within a single simulation pass.

Cycle-free graphs use an iterative DFS with proper post-order assignment: a node's priority is computed only after all of its successors have theirs, which makes priorities deterministic and independent of the iteration order of elements. (The previous implementation mistook pending DFS siblings for feedback edges and could order a consumer at or above its producer on plain DAGs — and a pure DAG runs the non-settling fast path, so nothing masked the mis-order; an edge-triggered flip-flop could latch a stale value permanently.)

Cyclic graphs keep the legacy ordering (see PrioritiesInternal::legacyCalculatePriorities): their single-pass order is not load-bearing for correctness because the simulation switches to iterative settling over all elements whenever feedback is present, and the legacy order is what the gate-built latch circuits settle correctly under.

Parameters

elements	All nodes to process.
successors	Adjacency list (node -> its successors).
outPriorities	Output map filled with computed priorities.

Definition at line 224 of file Priorities.h.

References findFeedbackNodes(), and PrioritiesInternal::legacyCalculatePriorities().

Referenced by Scene::sortByTopology(), and Simulation::topologicalSort().

findFeedbackNodes()

template<typename T>

QSet< T * > findFeedbackNodes	(	const QVector< T * > &	elements,
		const QHash< T *, QVector< T * > > &	successors )

Finds all nodes that participate in feedback loops (cycles).

Uses Tarjan's iterative SCC algorithm. Every node belonging to a strongly connected component of size > 1 (or with a self-loop) is returned in the output set.

Parameters

elements	All nodes to process.
successors	Adjacency list (node -> its successors).

Returns

Set of all nodes that are part of at least one cycle.

Definition at line 29 of file Priorities.h.

Referenced by calculatePriorities(), and Simulation::topologicalSort().