---

Computing the closure of a relation: Floyd-Warshall Algorithm

---

• Using directed graphs to represent binary relations
  • A binary relation "⇒" can naturally be represented by a directed graph

  • Example:

    a ⇒ b b ⇒ e c ⇒ e c ⇒ d d ⇒ f e ⇒ f

    Corresponding directed graph:

    ---

    ---

• Transitive (binary) relations
  • A binary relation "⇒" is transitive if:

    a ⇒ b and b ⇒ c implies: a ⇒ c

    ---

  • Example:   <   is transitive

    a < b and b < c implies: a < c

    ---

    ---

  • Graph representation of an example of the   <   transitive relation:

    ---

  • The transitivity property defines a partial ordering among the elements of a set

  ---

  ---

  ---

  ---

• Transitive closure
  • Definition: transitive closure

    Let R be a binary relation The transitive closure of a binary relation R is the transitive relation R+ such that: R   ⊆   R+ R+ is minimal

    ---

  • Example:

    R = { a ⇒ b,   b ⇒ c } The transitive closure R+ = { a ⇒ b,   b ⇒ c,   a ⇒ c }

  ---

  ---

• Computing the transitive closure of a binary relation
  • Example:

    Initial relation: Find all transitivity relation that uses a node b as intermediary: We look for: Every possible combination (x ⇒ b) (b ⇒ z) If we find (x ⇒ b) (b ⇒ z) in the graph, we add the edge x ⇒ z Result: Repeat: for node c Result: Repeat: for node d Result: Repeat: for node e Result:

    ---

  • Note:

    We must do this for nodes a and f also I skipped those nodes because no new edges were added....

  ---

  ---

• A property that helps us develop an efficient algorithm for transitive closure
  • Property:

    Let G be the original directed graph that represents the binary relation Let {v1, v2, ..., vn} be an arbitrary numbering of the vertices in graph G Let G0 = G Let Gk be the directed graph obtained after iteration k Then: Gk has an edge (vi,vj) if and only if: Graph G has a (directed) path from vi   →   vj The path vi   →   vj = vi   → x1   → x2 ...   → xu   → vj will go through nodes v1, v2, ..., vk I.e.: xi ∈ { v1, v2, ..., vk } (This property follows from the way we include the edges in Gk)

    ---

  • Example:

    After the iteration using nodes b and c we have: The new edges are: (a,e) (a,d)       The paths that caused the inclusion of these edges contains only the nodes b and c: a → b → e a → c → d

    ---

  • Important conclusion from the property:

    The graph Gn of the serie of iteration is equal to the graph of the transitive closure of binary relation represented by graph G

    Proof:

    The property of the graph Gn is: Gn has an edge (vi,vj) if and only if: Graph G has a (directed) path from vi   →   vj The path vi   →   vj = vi   → x1   → x2 ...   → xu   → vj will go through nodes v1, v2, ..., vn I.e.: xi ∈ { v1, v2, ..., vn } (This property follows from the way we include the edges in Gn) Therefore: Edge (vi,vj) is in Gn if and only if there is a directed path from vi to vj using every possible node This is exactly equal to the transitive closure

  ---

  ---

  ---

  ---

• The Floyd-Warshall algorithm
  • The Floyd-Warshall algorithm's correctness is based on the above claim

    ---

  • The Floyd-Warshall Algorithm:

    v1, v2, ..., vn = an arbitrary numbering of the vertices G0 = G; // Initialize for ( k = 1; k <= n; k++ ) { Gk = Gk-1; // Build next graph for ( i = 1; i <= n; i++ ) { for ( j = 1; j <= n; j++ ) { if ( edges (i,k) and (k,j) exists in Gk ) { add edge (i,j) to Gk; } } } }

    ---

  • Example Program: (Demo above code)                                                
    • The Floyd-Warshall algorithm Prog file: click here