Java: référencer une arête dans un graphe

Question

Je modifie une implémentation de graphe pour calculer la matrice de plus court chemin de toutes les paires en utilisant Floyd's algorithm. Le graphique possède à la fois une liste de liens adjacents et des implémentations matricielles. Pour l'instant j'utilise la matrice d'adjacence car c'est nécessaire pour cet algorithme.

abstract public class GraphMatrix<V,E> extends AbstractStructure<V> implements Graph<V,E>{ 
/** 
* Number of vertices in graph. 
*/ 
protected int size;   // allocation size for graph 
/** 
* The edge data. Every edge appears on one (directed) 
* or two (undirected) locations within graph. 
*/ 
protected Object data[][];  // matrix - array of arrays 
/** 
* Translation between vertex labels and vertex structures. 
*/ 
protected Map<V,GraphMatrixVertex<V>> dict; // labels -> vertices 
/** 
* List of free vertex indices within graph. 
*/ 
protected List<Integer> freeList; // available indices in matrix 
/** 
* Whether or not graph is directed. 
*/ 
protected boolean directed; // graph is directed 

/** 
* Constructor of directed/undirected GraphMatrix. Protected constructor. 
* 
* @param size Maximum size of graph. 
* @param dir True if graph is to be directed. 
*/ 
protected GraphMatrix(int size, boolean dir) 
{ 
    this.size = size; // set maximum size 
    directed = dir; // fix direction of edges 
    // the following constructs a size x size matrix 
    data = new Object[size][size]; 
    // label to index translation table 
    dict = new Hashtable<V,GraphMatrixVertex<V>>(size); 
    // put all indices in the free list 
    freeList = new SinglyLinkedList<Integer>(); 
    for (int row = size-1; row >= 0; row--) 
     freeList.add(new Integer(row)); 
} 

. 
. 
. 

public Object[][] AllPairsShortestPath() 
{ 
    //First, data array needs to be copied to a new array so that it is not corrupted. 
    Object[][] weight_matrix = data.clone(); 
    for(int k = 0; k < size; k++) 
    { 
     for(int i = 0; i < size; i++) 
     { 
      for(int j = 0; j < size; j++) 
      { 
       if((weight_matrix + weight_matrix[k][j])<weight_matrix[i][j]) 
       { 
        //New shorter path is found 
       } 
      } 
     } 
    } 
    return weight_matrix;  
} 

Ma question est comment puis-je référencer les éléments weight_matrix afin qu'ils puissent être comparés? Voici la classe de bord qui est dans la matrice de l'objet:

public class Edge<V,E> 
{ 
/** 
* Two element array of vertex labels. 
* When necessary, first element is source. 
*/ 
protected V here, there; // labels of adjacent vertices 
/** 
* Label associated with edge. May be null. 
*/ 
protected E label;  // edge label 
/** 
* Whether or not this edge has been visited. 
*/ 
protected boolean visited; // this edge visited 
/** 
* Whether or not this edge is directed. 
*/ 
protected boolean directed; // this edge directed 

/** 
* Construct a (possibly directed) edge between two labeled 
* vertices. When edge is directed, vtx1 specifies source. 
* When undirected, order of vertices is unimportant. Label 
* on edge is any type, and may be null. 
* Edge is initially unvisited. 
* 
* @post edge associates vtx1 and vtx2; labeled with label 
*  directed if "directed" set true 
* 
* @param vtx1 The label of a vertex (source if directed). 
* @param vtx2 The label of another vertex (destination if directed). 
* @param label The label associated with the edge. 
* @param directed True iff this edge is directed. 
*/ 
public Edge(V vtx1, V vtx2, E label, 
      boolean directed) 
{ 
    here = vtx1; 
    there = vtx2; 
    this.label = label; 
    visited = false; 
    this.directed = directed; 
} 

/** 
* Returns the first vertex (or source if directed). 
* 
* @post returns first node in edge 
* 
* @return A vertex; if directed, the source. 
*/ 
public V here() 
{ 
    return here; 
} 

/** 
* Returns the second vertex (or source if undirected). 
* 
* @post returns second node in edge 
* 
* @return A vertex; if directed, the destination. 
*/ 
public V there() 
{ 
    return there; 
} 

/** 
* Sets the label associated with the edge. May be null. 
* 
* @post sets label of this edge to label 
* 
* @param label Any object to label edge, or null. 
*/ 
public void setLabel(E label) 
{ 
    this.label = label; 
} 

/** 
* Get label associated with edge. 
* 
* @post returns label associated with this edge 
* 
* @return The label found on the edge. 
*/ 
public E label() 
{ 
    return label; 
} 

/** 
* Test and set visited flag on vertex. 
* 
* @post visits edge, returns whether previously visited 
* 
* @return True iff edge was visited previously. 
*/ 
public boolean visit() 
{ 
    boolean was = visited; 
    visited = true; 
    return was; 
} 

/** 
* Check to see if edge has been visited. 
* 
* @post returns true iff edge has been visited 
* 
* @return True iff the edge has been visited. 
*/ 
public boolean isVisited() 
{ 
    return visited; 
} 

/** 
* Check to see if edge is directed. 
* 
* @post returns true iff edge is directed 
* 
* @return True iff the edge has been visited. 
*/ 
public boolean isDirected() 
{ 
    return directed; 
} 

/** 
* Clear the visited flag associated with edge. 
* 
* @post resets edge's visited flag to initial state 
*/ 
public void reset() 
{ 
    visited = false; 
} 

/** 
* Returns hashcode associated with edge. 
* 
* @post returns suitable hashcode 
* 
* @return An integer code suitable for hashing. 
*/ 
public int hashCode() 
{ 
    if (directed) return here().hashCode()-there().hashCode(); 
    else   return here().hashCode()^there().hashCode(); 
} 

/** 
* Test for equality of edges. Undirected edges are equal if 
* they connect the same vertices. Directed edges must have same 
* direction. 
* 
* @post returns true iff edges connect same vertices 
* 
* @param o The other edge. 
* @return True iff this edge is equal to other edge. 
*/ 
public boolean equals(Object o) 
{ 
    Edge<?,?> e = (Edge<?,?>)o; 
    return ((here().equals(e.here()) && 
      there().equals(e.there())) || 
      (!directed && 
      (here().equals(e.there()) && 
       there().equals(e.here())))); 
} 

/** 
* Construct a string representation of edge. 
* 
* @post returns string representation of edge 
* 
* @return String representing edge. 
*/ 
public String toString() 
{ 
    StringBuffer s = new StringBuffer(); 
    s.append("<Edge:"); 
    if (visited) s.append(" visited"); 
    s.append(" "+here()); 
    if (directed) s.append(" ->"); 
    else s.append(" <->"); 
    s.append(" "+there()+">"); 
    return s.toString(); 
} 
} 

Answer 1

Je suppose que ((weight_matrix + weight_matrix[k][j])<weight_matrix[i][j])

est pas ce que vous voulez. IIRC, Floyd suit est aussi:

((weight_matrix[i][k] + weight_matrix[k][j])<weight_matrix[i][j])

SI VOTRE weight_matrix était une matrice de poids (un coup d'oeil here pour plus floyd). La taille, dans cette implémentation, serait le nombre de sommets que vous avez sur le graphique.

Si chaque bord avait un poids, vous pourriez faire

((((Edge)weight_matrix[i][k]).getValue() + ((Edge)weight_matrix[k][j]).getValue()) < ((Edge)weight_matrix[i][j]).getValue())

Si tous les poids de bord sont égaux, vous pourriez dire getValue() pour revenir 1 toujours, et voilá.