Exemple de Graphe orienté et Tri Topologique Code

Ce que quelqu'un sait où je peux obtenir un échantillon de la mise en œuvre d'un Graphe orienté et un exemple de code pour effectuer un tri topologique sur un graphe orienté? (de préférence en Java)

J'ai codé cette mise en œuvre jusqu'il y a quelques semaines. C'est en Java et utilise un custom graphe orienté de la classe. Nous espérons que les commentaires sont utiles!
la chose drôle est que si la même question était posée maintenant, il aurait été downvoted et fermé. Et les gens ont fait des commentaires demandant what have your tried so far.
fermés que pas constructif. Pour l'instant, cette question n'est pas un bon ajustement pour notre Q&Un format. Nous attendons des réponses à être étayée par des faits, des références, ou de l'expertise, mais cette question sera susceptible de solliciter le débat, les arguments, les bureaux de vote, ou de longues discussions. Si vous sentez que cette question peut être améliorée et, éventuellement, rouvert, visitez le centre d'aide et de conseils. ========================================================== C'est juste une blague. Bien sûr, je l'ai trouvé extrêmement utile.

InformationsquelleAutor | 2010-04-29

Ici est une simple mise en œuvre de la première algorithme de la Page Wikipedia sur le Tri Topologique:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
public class Graph {
static class Node{
public final String name;
public final HashSet<Edge> inEdges;
public final HashSet<Edge> outEdges;
public Node(String name) {
this.name = name;
inEdges = new HashSet<Edge>();
outEdges = new HashSet<Edge>();
}
public Node addEdge(Node node){
Edge e = new Edge(this, node);
outEdges.add(e);
node.inEdges.add(e);
return this;
}
@Override
public String toString() {
return name;
}
}
static class Edge{
public final Node from;
public final Node to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge e = (Edge)obj;
return e.from == from && e.to == to;
}
}
public static void main(String[] args) {
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
seven.addEdge(eleven).addEdge(eight);
five.addEdge(eleven);
three.addEdge(eight).addEdge(ten);
eleven.addEdge(two).addEdge(nine).addEdge(ten);
eight.addEdge(nine).addEdge(ten);
Node[] allNodes = {seven, five, three, eleven, eight, two, nine, ten};
//L <- Empty list that will contain the sorted elements
ArrayList<Node> L = new ArrayList<Node>();
//S <- Set of all nodes with no incoming edges
HashSet<Node> S = new HashSet<Node>(); 
for(Node n : allNodes){
if(n.inEdges.size() == 0){
S.add(n);
}
}
//while S is non-empty do
while(!S.isEmpty()){
//remove a node n from S
Node n = S.iterator().next();
S.remove(n);
//insert n into L
L.add(n);
//for each node m with an edge e from n to m do
for(Iterator<Edge> it = n.outEdges.iterator();it.hasNext();){
//remove edge e from the graph
Edge e = it.next();
Node m = e.to;
it.remove();//Remove edge from n
m.inEdges.remove(e);//Remove edge from m
//if m has no other incoming edges then insert m into S
if(m.inEdges.isEmpty()){
S.add(m);
}
}
}
//Check to see if all edges are removed
boolean cycle = false;
for(Node n : allNodes){
if(!n.inEdges.isEmpty()){
cycle = true;
break;
}
}
if(cycle){
System.out.println("Cycle present, topological sort not possible");
}else{
System.out.println("Topological Sort: "+Arrays.toString(L.toArray()));
}
}
}

M'a sauvé la vie!!! Merci M. Jessup!
Pourquoi avez-vous choisi un hashSet? Sans écraser equals() et hashCode() dans les Bords, c'est pas un ensemble. Essayez d'ajouter le bord même deux fois.

InformationsquelleAutor M. Jessup

Une mise en œuvre que j'ai réalisée sur la deuxième alternative sur la page wikipédia:
http://en.wikipedia.org/wiki/Topological_sorting

public class Graph {
Hashtable<Node, ArrayList<Node>> adjList = new Hashtable<Node, ArrayList<Node>>();
ArrayList<Node> nodes = new ArrayList<Node>();
LinkedList<Node> topoSorted;
public Graph() {}
public void add(Node node) { 
if (adjList.contains(node)) { 
return;
} else { 
adjList.put(node, new ArrayList<Node>());
nodes.add(node);
}
}
public void addNeighbor(Node from, ArrayList<Node> list) { 
for (Node to: list) { 
addNeighbor(from, to);
}
}
public void addNeighbor(Node from, Node to) { 
if (!adjList.containsKey(from)) { 
add(from);
}
if (!adjList.containsKey(to)) { 
add(to);
}
adjList.get(from).add(to);
to.inDegree++;
to.inNodes.add(from);
}
public void remove(Node node) { 
for (Node n: nodes) { 
for (Node x: adjList.get(n)) { 
if (x.equals(node)) removeNeighbor(n, x);
}
}
adjList.remove(node);
nodes.remove(node);
}
public void removeNeighbor(Node from, Node to) { 
adjList.get(from).remove(to);
to.inDegree--;
to.inNodes.remove(from);
}
public void resetVisited() { 
for (Node node: nodes) { 
node.visited = false;
}
}
public boolean hasEdge(Node from, Node to) { 
return adjList.get(from).contains(to) ? true : false;
}
/**
* for DAGS only
* @throws Exception
*/
public void topologicalSort() throws Exception { 
/* L <-- Empty list that will contain the sorted elements */
topoSorted = new LinkedList<Node>();
/* Use set to keep track of permanently visited nodes
* in constant time. Does have pointer overhead */
HashSet<Node> visited = new HashSet<Node>();
/* while there are unmarked nodes do */
for (Node n: nodes) { 
/* select an unmarked node n
* visit(n)
*/
if (!visited.contains(n)) visit(n, visited);
}
}
/* function: visit(node n) */
public void visit(Node node, HashSet<Node> set) throws Exception { 
/* if n has a temporary mark then stop (not a DAG) */
if (node.visited) { 
throw new Exception("graph cyclic");
/* if n is not marked (i.e. has not been visited) then... */
} else { 
/* mark n temporarily [using boolean field in node]*/
node.visited = true;
/* for each node m with an edge n to m do... */
for (Node m: adjList.get(node)) { 
/* visit(m) */
if (!set.contains(m)) visit(m, set);            
}
/* mark n permanently */
set.add(node);
/* unmark n temporarily */
node.visited = false;
/* add n to head of L */
topoSorted.addFirst(node);
}
}
public void printGraph() { 
for (Node node: nodes) { 
System.out.print("from: " + node.value + " |  to: ");
for (Node m: adjList.get(node)) { 
System.out.print(m.value + " ");
}
System.out.println();
}
}
public void instantiateGraph() { 
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
addNeighbor(seven, eleven);
addNeighbor(seven, eight);
addNeighbor(five, eleven);
addNeighbor(three, eight);
addNeighbor(three, ten);
addNeighbor(eleven, two);
addNeighbor(eleven, nine);
addNeighbor(eleven, ten);
addNeighbor(eight, nine);
try {
topologicalSort();
} catch (Exception e) {
//TODO Auto-generated catch block
e.printStackTrace();
}
for (Node node: topoSorted) { 
System.out.print(node.value + " ");
}   
}
public class Node { 
String value; 
boolean visited = false;
int inDegree = 0;
ArrayList<Node> inNodes = new ArrayList<Node>();
public Node (String value) { 
this.value = value;
}
}
public static void main(String[] args) { 
Graph g = new Graph();
g.instantiateGraph();
}
}

InformationsquelleAutor user3267322

2

Vous pouvez également utiliser un tiers des projets open source, comme JGraphT. Il fournit de nombreux simple et compliqué graphique des structures et de leur représentation visuelle. Aussi, vous n'avez pas à traiter avec les problèmes structurels de cette façon.

InformationsquelleAutor tugcem

Voici une mise en œuvre je l'ai fait il y a quelques temps:

/**
* 
* Sorts a directed graph, obtaining a visiting sequence ("sorted" list)
* that respects the "Predecessors" (as in a job/task requirements list).
* (when there is freedom, the original ordering is preferred)
* 
* The behaviour in case of loops (cycles) depends on the "mode":
*    permitLoops == false : loops are detected, but result is UNDEFINED (simpler) 
*    permitLoops == true  :  loops are detected, result a "best effort" try,   original ordering is privileged
*    
* http://en.wikipedia.org/wiki/Topological_sort
*/
public class TopologicalSorter<T extends DirectedGraphNode> {
private final boolean permitLoops;
private final Collection<T> graph; //original graph. this is not touched.
private final List<T> sorted = new ArrayList<T>(); //result
private final Set<T> visited = new HashSet<T>(); //auxiliar list
private final Set<T> withLoops = new HashSet<T>();
//auxiliar: all succesors (also remote) of each node; this is only used if permitLoops==true
private HashMap<T, Set<T>> succesors = null;
public TopologicalSorter(Collection<T> graph, boolean permitLoops) {
this.graph = graph;
this.permitLoops = permitLoops;
}
public void sort() {
init();
for( T n : graph ) {
if( permitLoops ) visitLoopsPermitted(n);
else visitLoopsNoPermitted(n, new HashSet<T>());
}
}
private void init() {
sorted.clear();
visited.clear();
withLoops.clear();
//build succesors map: only it permitLoops == true 
if( permitLoops ) {
succesors = new HashMap<T, Set<T>>();
HashMap<T, Set<T>> addTo = new HashMap();
for( T n : graph ) {
succesors.put(n, new HashSet<T>());
addTo.put(n, new HashSet<T>());
}
for( T n2 : graph ) {
for( DirectedGraphNode n1 : n2.getPredecessors() ) {
succesors.get(n1).add(n2);
}
}
boolean change = false;
do {
change = false;
for( T n : graph ) {
addTo.get(n).clear();
for( T ns : succesors.get(n) ) {
for( T ns2 : succesors.get(ns) ) {
if( !succesors.get(n).contains(ns2) ) {
change = true;
addTo.get(n).add(ns2);
}
}
}
}
for( DirectedGraphNode n : graph ) {
succesors.get(n).addAll(addTo.get(n));
}
} while(change);
}
}
private void visitLoopsNoPermitted(T n, Set<T> visitedInThisCallStack) { //this is simpler than visitLoopsPermitted 
if( visited.contains(n) ) {
if( visitedInThisCallStack.contains(n) ) {
withLoops.add(n); //loop!
}
return;
}
//System.out.println("visiting " + n.toString());
visited.add(n);
visitedInThisCallStack.add(n);
for( DirectedGraphNode n1 : n.getPredecessors() ) {
visitLoopsNoPermitted((T) n1, visitedInThisCallStack);
}
sorted.add(n);
}
private void visitLoopsPermitted(T n) {
if( visited.contains(n) ) return;
//System.out.println("visiting " + n.toString());
visited.add(n);
for( DirectedGraphNode n1 : n.getPredecessors() ) {
if( succesors.get(n).contains(n1) ) {
withLoops.add(n);
withLoops.add((T) n1);
continue;
} //loop!
visitLoopsPermitted((T) n1);
}
sorted.add(n);
}
public boolean hadLoops() {
return withLoops.size() > 0;
}
public List<T> getSorted() {
return sorted;
}
public Set<T> getWithLoops() {
return withLoops;
}
public void showResult() { //for debugging
for( DirectedGraphNode node : sorted ) {
System.out.println(node.toString());
}
if( hadLoops() ) {
System.out.println("LOOPS!:");
for( DirectedGraphNode node : withLoops ) {
System.out.println("  " + node.toString());
}
}
}
}
/**
* Node that conform a DirectedGraph 
* It is used by TopologicalSorter
*/
public interface DirectedGraphNode {
/** 
* empty collection if no predecessors
* @return
*/
public Collection<DirectedGraphNode> getPredecessors();
}

Et voici un exemple d'utilisation:

public class TopologicalSorterExample {
public static class Node implements DirectedGraphNode {
public final String x;
public ArrayList<DirectedGraphNode> antec = new ArrayList<DirectedGraphNode>(); //immediate antecesors
public Node(String x) {this.x= x;}
public Collection<DirectedGraphNode> getPredecessors() {
return antec;
}
public String toString() {
return x;
}
}
public static void main(String[] args) {
List<DirectedGraphNode> graph = new ArrayList<DirectedGraphNode>();
Node na = new Node("A");
Node nb = new Node("B");
Node nc = new Node("C");
Node nd = new Node("D");
Node ne = new Node("E");
nc.antec.add(na);
nc.antec.add(nb);
nd.antec.add(ne);
ne.antec.add(na);
na.antec.add(nd);
graph.add(nc);
graph.add(na);
graph.add(nb);
graph.add(ne);
graph.add(nd);
TopologicalSorter ts = new TopologicalSorter(graph, false);
ts.sort();
ts.showResult();
}
}

Deux fonctionnalités supplémentaires (ou de complications) dans mon code:
J'avais besoin de l'appui des boucles (cycles) dans mon cas, de sorte que si le graphe a boucles il fait quelques "best-effort" de la commande. Ce comportement est contrôlé par un drapeau passé au constructeur. Dans tous les cas, vous pouvez (devez) faire appel hadLoops() pour demander si il y avait des cycles détectés.
En plus, je voulais l'algorithme de tri à préférer l'original de la commande dans le cas de la liberté.

InformationsquelleAutor leonbloy

0

D'accord avec jeremy.

Je pense que c'est ici une mise en œuvre pour obtenir le hashcode basée sur l'efficacité de Java:
http://www.javapractices.com/topic/TopicAction.do?Id=28

Comment ajouter ci-dessous la méthode pour remplacer le hashcode?
```
@Override
public int hashCode(){
if (fHashCode == 0) {
int result = HashCodeUtil.SEED;
result = HashCodeUtil.hash(result, from);
result = HashCodeUtil.hash(result, to);
}
return fHashCode;
}
```
InformationsquelleAutor hart

Juste pour compléter l'excellente solution par @templatetypedef un peu, j'ai ajouté quelques tests unitaires à donner de la confiance pour moi et pour les autres à utiliser. Espérons que cela aide...

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.List;
import org.junit.Test;
public class TestTopologicalSort {
@Test (expected=java.lang.NullPointerException.class)
public void testNullGraph() {
final List<String> orderedLayers = TopologicalSort.sort(null);
}
@Test
public void testEmptyGraph() {
final DirectedGraph<String> dag = new DirectedGraph<String>();        
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(0, orderedLayers.size());
}
@Test
public void testSingleVertex() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(1, orderedLayers.size());
assertTrue(orderedLayers.contains("a"));
}
@Test
public void testMultipleVertices() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addNode("b");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(2, orderedLayers.size());
assertTrue(orderedLayers.contains("a"));
assertTrue(orderedLayers.contains("b"));
}
@Test (expected=java.util.NoSuchElementException.class)
public void testBogusEdge() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addEdge("a", "b");
}
@Test
public void testSimpleDag() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("b");        
dag.addNode("a");
dag.addEdge("a", "b");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(2, orderedLayers.size());
assertTrue(orderedLayers.get(0).equals("a"));
assertTrue(orderedLayers.get(1).equals("b"));
}
@Test
public void testComplexGraph() {
//node b has two incoming edges
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");        
dag.addNode("b");
dag.addNode("c");        
dag.addNode("d");
dag.addNode("e");        
dag.addNode("f");
dag.addNode("g");        
dag.addNode("h");
dag.addEdge("a", "b");
dag.addEdge("a", "c");
dag.addEdge("c", "d");
dag.addEdge("d", "b");
dag.addEdge("c", "e");
dag.addEdge("f", "g");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(8, orderedLayers.size());
assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("b")); 
assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("c"));
assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("d"));
assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("e"));
assertTrue(orderedLayers.indexOf("d") < orderedLayers.indexOf("b"));
assertTrue(orderedLayers.indexOf("f") < orderedLayers.indexOf("g"));
}
@Test (expected=java.lang.IllegalArgumentException.class)
public void testCycle() {
//cycle between a, c, and d
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");        
dag.addNode("b");
dag.addNode("c");        
dag.addNode("d");
dag.addNode("e");        
dag.addNode("f");
dag.addNode("g");        
dag.addNode("h");
dag.addEdge("a", "b");
dag.addEdge("a", "c");
dag.addEdge("c", "d");
dag.addEdge("d", "a");
dag.addEdge("c", "e");
dag.addEdge("f", "g");
final List<String> orderedLayers = TopologicalSort.sort(dag);
}
}

InformationsquelleAutor rimsky

0

Vous avez besoin de remplacer hashCode() de la fonction en tant que bien puisque vous utilisez HashSet dans les bords.

Autrement, il va soulever des bugs.

EXP: Ajouter deux instances à même de et à dans le hashset. Le 2ème ne sera pas overritten sans hashCode() qui il est censé être remplacé.

InformationsquelleAutor Jeremy

Vous devez vous connecter pour publier un commentaire.