Page Menu
Home
Phorge
Search
Configure Global Search
Log In
Files
F3282072
AbstractDirectedGraphTestCase.php
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Award Token
Flag For Later
Advanced/Developer...
View Handle
View Hovercard
Size
4 KB
Referenced Files
None
Subscribers
None
AbstractDirectedGraphTestCase.php
View Options
<?php
final
class
AbstractDirectedGraphTestCase
extends
PhutilTestCase
{
public
function
testTrivialGraph
(
)
{
$graph
=
array
(
'A'
=>
array
(
)
,
)
;
$cycle
=
$this
->
findGraphCycle
(
$graph
)
;
$this
->
assertEqual
(
null
,
$cycle
,
pht
(
'Trivial Graph'
)
)
;
}
public
function
testNoncyclicGraph
(
)
{
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'D'
)
,
'C'
=>
array
(
)
,
'D'
=>
array
(
)
,
)
;
$cycle
=
$this
->
findGraphCycle
(
$graph
)
;
$this
->
assertEqual
(
null
,
$cycle
,
pht
(
'Noncyclic Graph'
)
)
;
}
public
function
testTrivialCyclicGraph
(
)
{
$graph
=
array
(
'A'
=>
array
(
'A'
)
,
)
;
$cycle
=
$this
->
findGraphCycle
(
$graph
)
;
$this
->
assertEqual
(
array
(
'A'
,
'A'
)
,
$cycle
,
pht
(
'Trivial Cycle'
)
)
;
}
public
function
testCyclicGraph
(
)
{
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'D'
)
,
'C'
=>
array
(
'E'
,
'F'
)
,
'D'
=>
array
(
)
,
'E'
=>
array
(
)
,
'F'
=>
array
(
'G'
,
'C'
)
,
'G'
=>
array
(
)
,
)
;
$cycle
=
$this
->
findGraphCycle
(
$graph
)
;
$this
->
assertEqual
(
array
(
'A'
,
'C'
,
'F'
,
'C'
)
,
$cycle
,
pht
(
'Cyclic Graph'
)
)
;
}
public
function
testNonTreeGraph
(
)
{
// This graph is non-cyclic, but C is both a child and a grandchild of A.
// This is permitted.
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'C'
)
,
'C'
=>
array
(
)
,
)
;
$cycle
=
$this
->
findGraphCycle
(
$graph
)
;
$this
->
assertEqual
(
null
,
$cycle
,
pht
(
'Non-tree graph'
)
)
;
}
public
function
testEdgeLoadFailure
(
)
{
$graph
=
array
(
'A'
=>
array
(
'B'
)
,
)
;
$raised
=
null
;
try
{
$this
->
findGraphCycle
(
$graph
)
;
}
catch
(
Exception
$ex
)
{
$raised
=
$ex
;
}
$this
->
assertTrue
(
(bool)
$raised
,
pht
(
'Exception raised by unloadable edges.'
)
)
;
}
public
function
testTopologicalOrder
(
)
{
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'D'
,
'E'
)
,
'C'
=>
array
(
)
,
'D'
=>
array
(
)
,
'E'
=>
array
(
)
,
)
;
$sorted
=
$this
->
getTopologicalOrder
(
$graph
)
;
$this
->
assertEqual
(
array
(
'A'
,
'C'
,
'B'
,
'E'
,
'D'
)
,
$sorted
,
pht
(
'Topologically sorted tree.'
)
)
;
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'C'
)
,
'C'
=>
array
(
'D'
,
'E'
)
,
'D'
=>
array
(
'E'
)
,
'E'
=>
array
(
)
,
)
;
$sorted
=
$this
->
getTopologicalOrder
(
$graph
)
;
$this
->
assertEqual
(
array
(
'A'
,
'B'
,
'C'
,
'D'
,
'E'
)
,
$sorted
,
pht
(
'Topologically sorted tree with nesting.'
)
)
;
}
public
function
testRoughTopologicalOrder
(
)
{
$graph
=
array
(
'A'
=>
array
(
'B'
,
'C'
)
,
'B'
=>
array
(
'D'
,
'E'
)
,
'C'
=>
array
(
)
,
'D'
=>
array
(
)
,
'E'
=>
array
(
)
,
'F'
=>
array
(
'H'
)
,
'G'
=>
array
(
'F'
,
'E'
)
,
'H'
=>
array
(
'G'
)
,
)
;
$sorted
=
$this
->
getRoughTopologicalOrder
(
$graph
)
;
$this
->
assertEqual
(
count
(
$graph
)
,
count
(
$sorted
)
)
;
$this
->
assertEqual
(
'C'
,
$sorted
[
0
]
[
'node'
]
)
;
$this
->
assertEqual
(
'D'
,
$sorted
[
1
]
[
'node'
]
)
;
$this
->
assertEqual
(
'E'
,
$sorted
[
2
]
[
'node'
]
)
;
$this
->
assertEqual
(
'B'
,
$sorted
[
3
]
[
'node'
]
)
;
$this
->
assertEqual
(
'A'
,
$sorted
[
4
]
[
'node'
]
)
;
$this
->
assertEqual
(
'F'
,
$sorted
[
5
]
[
'node'
]
)
;
$this
->
assertEqual
(
'G'
,
$sorted
[
6
]
[
'node'
]
)
;
$this
->
assertEqual
(
'H'
,
$sorted
[
7
]
[
'node'
]
)
;
$this
->
assertEqual
(
0
,
$sorted
[
0
]
[
'depth'
]
)
;
$this
->
assertEqual
(
0
,
$sorted
[
1
]
[
'depth'
]
)
;
$this
->
assertEqual
(
0
,
$sorted
[
2
]
[
'depth'
]
)
;
$this
->
assertEqual
(
1
,
$sorted
[
3
]
[
'depth'
]
)
;
$this
->
assertEqual
(
2
,
$sorted
[
4
]
[
'depth'
]
)
;
$this
->
assertEqual
(
3
,
$sorted
[
5
]
[
'depth'
]
)
;
$this
->
assertEqual
(
3
,
$sorted
[
6
]
[
'depth'
]
)
;
$this
->
assertEqual
(
3
,
$sorted
[
7
]
[
'depth'
]
)
;
$this
->
assertEqual
(
false
,
$sorted
[
0
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
false
,
$sorted
[
1
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
false
,
$sorted
[
2
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
false
,
$sorted
[
3
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
false
,
$sorted
[
4
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
true
,
$sorted
[
5
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
true
,
$sorted
[
6
]
[
'cycle'
]
)
;
$this
->
assertEqual
(
true
,
$sorted
[
7
]
[
'cycle'
]
)
;
}
private
function
findGraphCycle
(
array
$graph
,
$seed
=
'A'
,
$search
=
'A'
)
{
$detector
=
new
TestAbstractDirectedGraph
(
)
;
$detector
->
setTestData
(
$graph
)
;
$detector
->
addNodes
(
array_select_keys
(
$graph
,
array
(
$seed
)
)
)
;
$detector
->
loadGraph
(
)
;
return
$detector
->
detectCycles
(
$search
)
;
}
private
function
getTopologicalOrder
(
array
$graph
,
$seed
=
'A'
)
{
$detector
=
new
TestAbstractDirectedGraph
(
)
;
$detector
->
setTestData
(
$graph
)
;
$detector
->
addNodes
(
array_select_keys
(
$graph
,
array
(
$seed
)
)
)
;
$detector
->
loadGraph
(
)
;
return
$detector
->
getNodesInTopologicalOrder
(
)
;
}
private
function
getRoughTopologicalOrder
(
array
$graph
)
{
$detector
=
new
TestAbstractDirectedGraph
(
)
;
$detector
->
setTestData
(
$graph
)
;
$detector
->
addNodes
(
array_keys
(
$graph
)
)
;
return
$detector
->
getNodesInRoughTopologicalOrder
(
)
;
}
}
File Metadata
Details
Attached
Mime Type
text/x-php
Expires
Mon, Mar 24, 04:09 (1 d, 1 h ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
1119764
Default Alt Text
AbstractDirectedGraphTestCase.php (4 KB)
Attached To
Mode
rARC Arcanist
Attached
Detach File
Event Timeline
Log In to Comment