Difference between revisions of "TADM2E 5.17"

From Algorithm Wiki
Jump to: navigation, search
(Created page with "use dfs to find cycle of lenght 3. we maintain an array parent[i]. while processing any backedge u-v we check whether gradparent of u is equal to v .if true we found a cycle...")
 
(Undo revision 1050 by FuckMatt (talk))
 
(13 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
use dfs to find cycle of lenght 3.
+
(a) Compare every possible set of three vertices and test if there is an edge between the three.
  
−
we maintain an array parent[i].
+
(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph
  
−
while processing any backedge u-v we check whether gradparent of u is equal to v .if true we found a cycle of lenght 3.
+
A - B - C - D - A (square)
−
-------1
 
−
|    / \
 
−
|    /  \
 
−
|  2    3
 
−
|  / \
 
−
| /  \
 
−
-4    5
 
  
−
Here u=4 to v=1 has backedge and grandparent of u=4 is 1,so condition satifies parent[parent[u]] == v
+
D - E - F - G - D (another square, connected to the first one through D)
−
hence given graph has cycle of lenght 3.we stop here to futher explore dfs().
 
  
 +
A - G (edge that closes the triangle A - D - G).
  
−
/* java program
 
−
* To change this license header, choose License Headers in Project Properties.
 
−
* To change this template file, choose Tools | Templates
 
−
* and open the template in the editor.
 
−
*/
 
−
package pkg5.pkg9;
 
  
−
import java.util.ArrayList;
+
DFS would produce:
−
import java.util.Scanner;
 
−
import static pkg5.pkg9.TwoColor.nodes;
 
  
−
/**
+
A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)
−
*
 
−
* @author Rahul
 
−
*/
 
−
public class Test5_17 {
 
  
−
    /**
+
At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.
−
    * @param args the command line arguments
+
 
−
    */
+
Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf
−
    static  ArrayList<ArrayList<Integer>> graph ;
+
 
−
    static int nodes;
+
----
−
    static int edges;
+
Alternative solution
−
    static boolean[] disc;
+
 
−
    static boolean[] processed;
+
<pre>
−
    static Integer[] parent;
+
1. O(|V|^3)
−
    static boolean found3_LenCycle = false;
+
- If only adjacency lists are available, convert adjacency lists to the adjacency matrix
−
    public static void main(String[] args) {
+
- If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices
−
        // TODO code application logic here
+
for adjacency with U O(1)
−
       
+
 
−
        Scanner in = new Scanner(System.in);
+
2. O(|V|*|Е|), |V| <= |E|
−
     
+
- Data preparation
−
        nodes = in.nextInt();
+
- - Let's analyze the case with the largest upper bound => assume that |V| = |E|
−
        edges = in.nextInt();
+
- - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)
−
       
+
- - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)
−
        disc = new boolean[nodes];
+
- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix
−
        processed = new boolean[nodes];
+
 
−
        parent = new Integer[nodes];
+
- Algorithm
−
     
+
- - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item
−
     
+
- - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item
−
        graph = new ArrayList<ArrayList<Integer>>(nodes);
+
- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
−
        for(int i=0;i < nodes;i++)
+
- - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|
−
            graph.add(i,new ArrayList<Integer>());
+
</pre>
−
     
+
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 10:16, 5 July 2020 (UTC)
−
        for(int i=0;i < edges;i++){
 
−
            int u = in.nextInt();
 
−
            int v = in.nextInt();
 
−
           
 
−
            graph.get(u).add(v);
 
−
            graph.get(v).add(u);
 
−
        }
 
−
       
 
−
        for(int i=0;i < nodes;i++){
 
−
            if( !disc[i]){
 
−
                parent[i] = null;
 
−
                dfs(i);
 
−
            }
 
−
               
 
−
        }
 
−
       
 
−
        if(found3_LenCycle)
 
−
            System.out.println("found 3-length cycle");
 
−
        else
 
−
            System.out.println("not found 3-length cycle");
 
−
       
 
−
    }
 
−
   
 
−
    public static void dfs(Integer u){
 
−
        //processVertexEarly(node);
 
−
        ArrayList<Integer> adjList = graph.get(u);
 
−
       
 
−
        disc[u] = true;
 
−
       
 
−
        for(Integer v : adjList){
 
−
            if( !disc[v]){//tree edge
 
−
                parent[v]= u;
 
−
              // processEdge(u,v);
 
−
                dfs(v);
 
−
            }else if(!processed[v]){ //back edge
 
−
                processEdge(u,v);
 
−
            }
 
−
           
 
−
            if(found3_LenCycle)
 
−
                break;
 
−
        }
 
−
       
 
−
        processed[u] = true;
 
−
    }
 
−
   
 
−
    public static void processEdge(Integer u,Integer v){
 
−
       
 
−
        if(parent[parent[u]] != null && parent[parent[u]]==v )
 
−
            found3_LenCycle = true;
 
−
    }
 
−
}
 

Latest revision as of 09:31, 31 July 2020

(a) Compare every possible set of three vertices and test if there is an edge between the three.

(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph

A - B - C - D - A (square)

D - E - F - G - D (another square, connected to the first one through D)

A - G (edge that closes the triangle A - D - G).


DFS would produce:

A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)

At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.

Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf

Alternative solution 

1. O(|V|^3)
- If only adjacency lists are available, convert adjacency lists to the adjacency matrix
- If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices
for adjacency with U O(1)

2. O(|V|*|Е|), |V| <= |E|
- Data preparation
- - Let's analyze the case with the largest upper bound => assume that |V| = |E|
- - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)
- - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)
- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix

- Algorithm
- - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item
- - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item
- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
- - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|

--Bkarpov96 (talk) 10:16, 5 July 2020 (UTC)

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_5.17&oldid=1053"