public List tsort()

in taverna-provenanceconnector/src/main/java/org/apache/taverna/provenance/lineageservice/EventProcessor.java [1376:1409]

• 24 lines of code
• 10 McCabe index (conditional complexity)

	public List<Pair> tsort(List<String> procList, String dataflowName,
			Map<String, Integer> predecessorsCount,
			Map<String, List<String>> successorsOf, String workflowId,
			String workflowRunId) throws SQLException {
		List<Pair> l = new ArrayList<>();		// holds sorted elements
		List<String> q = new ArrayList<>(); 	// temp queue

		// init queue with procList processors that have no predecessors
		for (String proc:procList)
			if (predecessorsCount.get(proc) == null || predecessorsCount.get(proc) == 0 &&
					!proc.equals(dataflowName))
				q.add(proc);

		while (!q.isEmpty()) {
			String current = q.remove(0);
			l.add(new Pair(current, workflowId));

			List<String> successors = successorsOf.get(current);

			if (successors == null)
				continue;

			// reduce the number of predecessors to each of the successors by one
			// NB we must traverse an additional datalink through a nested workflow input if the successor is a dataflow!!
			for (String succ : successors) {
				// decrease edge count for each successor processor
				predecessorsCount.put(succ, predecessorsCount.get(succ) - 1);

				if (predecessorsCount.get(succ) == 0 && !succ.equals(dataflowName))
					q.add(succ);
			}
		} // end loop on q
		return l;
	}