Algorithmus durch Workflow

[NT2005]

Hallo Community,

Ich hänge an einen sehr ärgerlichen in Sachen Logik und Algorithmen, dass mir eigentlich sonst immer lag.

Ich habe folgenden Workflow:


Der Einfachheit halber habe ich genau ein Klasse welche alle Nodes darstellt:

package de.test.workflow;

import java.util.ArrayList;
import java.util.List;

public class Node {

	private String name;
	private List<Node> outcomingNodes;
	
	public Node(String name) {
		this.name = name;
		outcomingNodes = new ArrayList<Node>();
	}
	
	public String getName() {
		return name;
	}
	
	public void addOutcomingNode(Node node) {
		outcomingNodes.add(node);
	}
	
	public List<Node> getOutcomingNodes() {
		return outcomingNodes;
	}
	
	private static void iterate(Node node, List<Node> nodes) {
		System.out.println(node.getName());
		
		for(Node next : node.getOutcomingNodes()) {
			if(!nodes.contains(next)) {
				nodes.add(next);
				iterate(next, nodes);
			}
		}
	}
	
	public static void main(String[] args) {
		Node start = new Node("Start");
		Node gateSplit = new Node("Gate split");
		Node node1 = new Node("node1");
		Node node2 = new Node("node2");
		Node node3 = new Node("node3");
		Node send = new Node("send");
		Node gateJoin = new Node("Gate join");
		Node end = new Node("End");
		
		start.addOutcomingNode(gateSplit);
		gateSplit.addOutcomingNode(node1);
		gateSplit.addOutcomingNode(node2);
		gateSplit.addOutcomingNode(node3);
		
		node1.addOutcomingNode(send);
		
		node2.addOutcomingNode(gateJoin);
		node3.addOutcomingNode(gateJoin);
		
		gateJoin.addOutcomingNode(end);
		List<Node> nodes = new ArrayList<Node>();
		nodes.add(start);
		iterate(start, nodes);
	}
}

Ergebnis:

Start
Gate split
node1
send
node2
Gate join
End
node3

Ziel ist es, durch alle Nodes genau einmal zu iterieren ohne das welche doppelt aufgerufen werden. Auch die Reihenfolge sollte beachtet werden:

Start
Gate split
node1
send
node2
node3
Gate join
End

Besser wäre jedoch, wenn jeder Node nach einem Zweig wie Ebenen aufgerufen wird. Ungefähr so:
Nach Gate Split folgt der nächste Aufruf node1, node2, node3 (Ebene beendet) danach erst send und gateJoin (Ebene beended)

Somit wäre das optimale und von mir auch gesuchte Ergebnis dieses:

Start
Gate split
node1
node2
node3
send
Gate join
End

 

[Mujahiddin]

Du kannst in der Methode iterate einen weiteren Parameter hinzufügen, also statt

iterate(Node start)

sowas wie

iterate(Node start, List<Node> visited

und dann mit

visited.contains(this)

überprüfen, ob der Knoten bereits besucht wurde.

 

[NT2005]

Danke, bringt mich ein Stück weiter.
Gesucht ist aber das Optimale Ergebnis am Ende.

Habe oben mal den aktuellen Stand korrigiert.

 

[Flown]

Man muss bei so einem join-Node warten bis alle Nodes ankommen und erst dann kannst du weiter visiten.

 

[Mujahiddin]

    private static void iterate(Node node, List<Node> nodes) {
        System.out.println(node.getName());
        
        for(Node next : node.getOutcomingNodes()) {
            if(!nodes.contains(next)) {
                nodes.add(next);
                iterate(next, nodes);
            }
        }
    }

Ich hatte mir eher sowas vorgestellt:

    private static void iterate(Node node, List<Node> nodes) {
        nodes.add(this);
        System.out.println(node.getName());
        
        for(Node next : node.getOutcomingNodes())
            if(!nodes.contains(next))
                iterate(next, nodes);
    }

Bei der Variante ist der erste Knoten nicht drin und wird evtl. 2x aufgerufen.

 

[Mujahiddin]

Das, was du erreichen willst, wäre durch eine Queue möglich. Allerdings arbeitest du mit Listen, also ist das auch mit einer Liste sehr leicht machbar.

private static void iterate(Node node, List<Node> nodes) {
        List<Node> outgoing = node.getOutcomingNodes(); // outcoming hört sich ja echt doof an
	
	Node curr = node;
	while(outcoming.size() > 0) {
		curr = outgoing.remove(0);
		nodes.add(curr);
		System.out.println(curr);
		for(Node n : curr.getOutComingNodes())
			if(!nodes.contains(n))
				outgoing.add(n);
	}
    }

So ungefähr.

Ja, ist eine ganz normale Breitensuche!

private static void iterate(Node node) {
	if(node == null)
		throw new IllegalArgumentException();
	List<Node> outgoing = new ArrayList<>();
	Set<Node> visited = new HashSet<>();
	visited.add( node );
	do {
		System.out.println( node );
		for( Node n : node.getOutgoingNodes() )
			if( !visited.contains( n ) ) {
				visited.add( n );
				outgoing.add( n );
			}
	} while( outgoing.size() > 0 && ( node = outgoing.remove( 0 ) ) != null );
}

 

[Marco13]

Das ist eine ganz normale Breitensuche ? Wikipedia

 

[NT2005]

Vielen Dank! Dachte mir schon das es das "Problem" schon einmal gibt. Kannte nur den Namen nicht.