Transcript Tree Decomposition

Tree
Decomposition
Benoit Vanalderweireldt
Phan Quoc Trung
Tram Minh Tri
Vu thi Puhong
1
Summary
•
•
•
•
•
•
•
•
•
•
Introduction
Definition
Requirement
Data structure
Graph generators
Algorithm
Example
Benchmark and tests
Interpretation
Conclusion
2
Definition
Tree decomposition
3
Definition
Tree width
1. The width of a bag is the cardinality of the bag.
2. The width of a tree decomposition is defined as maximum width
of all its bags.
3. The treewidth of a graph G is the minimum width among all
possible tree decompositions of G, denoted as tw(G).
Note that trees and forests are precisely the structures with treewidth of 2.
4
Introduction
Graph reachability answering
using tree decomposition ?
Is it profitable to decompose a graph
In order to test reachability ?
5
Requirement
1.
2.
3.
4.
5.
6.
7.
8.
9.
Understand notion of tree decomposition
Develop a data structure for graphs
Develop different graph generators
Implement the 4 parts of the algorithms
Make benchmark
Analyze result
Make conclusion
Write report
Present our work
6
Data structure
• Vertex
• Tree
• Node
7
Graph generators
In order to test the algorithm, we generated
various kind of graphs :
1. Inclusive square graph
2. Circle graph (in Example part)
3. Friendship graph
4. Random graph (in Example part)
8
Algorithm
Algorithm 1 start with a transform a directed graph
into undirected graph, but our work suppose that we
only work on undirected graph then line 1 is skipped
9
Algorithm
10
Example
Random graph
11
Example
Random graph
12
Example
Complete graph
1
2
5
2
5
2
1
4
4
3
3
5
3
4
3
13
Example
Wheel Graph
1
2
6
2
7
3
5
6
7
3
1
4
2
5
4
6
6
7
3
6
7
7
5
5
4
3
5
4
5
4
14
Example
Bipartite Graph
3
1
2
2
3
3
6
6
6
5
4
4
4
1
6
5
5
5
2
3
4
4
15
Example
Circle graph
16
Benchmark
The main goal of benchmark is to reveal in what condition it is gainful
to reduced graph in order to check reachability.
We run multiple series of benchmark :
• Various number of vertices and neighbors
• …..
Every test series have been past at least 2 times (to operating system
accident)
We compare effective results with expected results
Our series (around 20 measures) vary (increase or decrease) numbers
of edges or vertices
17
Benchmark
In order to have workable measure, we have to establish a protocol to
collect data. We quickly realize that to have meaningful results, we
need to apply the algorithm of really large graph (over hundred or
vertices).
Every test series have been past at least 2 times (to operating system
accident)
We compare effective results with expected results
Our series (around 20 measures) vary (increase or decrease) numbers
of edges or vertices
18
Interpretation
From these tests we found that the execution time of this algorithm
is influenced by number of edges not really by number of vertices.
If the density of edges increases then the computing time for
the graph reduction increase. In order to use this algorithm in a good
responding time, the density of edges must be well know.
19
Advantage & Disadvantage
Advantage of Tree Decomposition:
Solving shortest path query answering over undirected large graphs.
Disadvantage of Tree Decomposition:
Calculating the tree width of a graph is hard.
Even if the tree width can be determined, it still cannot be guaranteed that
good performance will be obtained.
It’s impossible to guarantee that good performance will be obtained even
though the tree width can be determined.
To solve really hard problems efficiently by using the tree decomposition based
approaches, we have to require that the underlying graphs have bounded tree
width (less than 10)
20
Conclusion
About the project (individual conclusion)
About the algorithm what do we think about graph reduction
(advantage and disadvantage)
Advantage of Tree Decomposition:
Disadvantage of Tree Decomposition:
Calculating the tree width of a graph is hard.
Even if the tree width can be determined, it still cannot be guaranteed
that good performance will be obtained.
To solve really hard problems efficiently by using the tree decomposition
based approaches, we have to require that the underlying graphs have
bounded tree width (less than 10)
21