forked from RMASBench/jmaxsum
-
Notifications
You must be signed in to change notification settings - Fork 0
/
overview.html
75 lines (62 loc) · 4.51 KB
/
overview.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
<body>
<h2>Implementation of Bounded Max Sum algorithm.</h2>
<p>This JavaDoc is a good place to start.<br/>
You can find an example of use in <i>test.Main</i> (but be careful, it has been used for test, so maybe it looks confusing).<br/>
</p>
<p>The master implementation starts in olimpo.Mercurio, that takes some parameters from command line and start the process.</p>
<p>The execution follows these steps:</p>
<ol>
<li><b>Cerbero</b> takes an input file that represents the instance and create an instance called <i>original_cop</i>:
<p><font face="mono" size="1">COP_Instance original_cop = Cerbero.getInstanceFromFile(filepath, oldformatV);</font></p></li>
<li>the <b>InstanceCloner</b> clones the instance in the new <i>cop</i>:
<p><font face="mono" size="1">InstanceCloner ic = new InstanceCloner(original_cop);<br/>
COP_Instance cop = ic.getClonedInstance();</font></p></li>
<li>the <b>ScrewerUp</b> changes the utility function a little, to make the <i>cop</i> asymmetric:
<p><font face="mono" size="1">screwerup = new ScrewerUp(cop);<br/>
cop = screwerup.screwItUp();</font></p></li>
<li><b>BoundedMaxSum</b> weight the factor graph, compute the maximum spanning tree, removes the edges and turn <i>cop</i>'s factorgraph in a tree:
<p><font face="mono" size="1">BMax = new BoundedMaxSum(cop.getFactorgraph());
<br/>BMax.letsBound();</font></p></li>
<li>the solver called <b>Athena</b> uses Max Sum algorithm to solve the <i>cop</i> and print the result:
<p><font face="mono" size="1">Athena core = new Athena(cop);<br/>
core.solve();<br/>
core.conclude();</font></p></li>
<li>the <b>InstanceCloner</b> copies the variables assignment from the cloned <i>cop</i> to the original:
<p><font face="mono" size="1">ic.setOriginalVariablesValues();</font></p></li>
<li>the <b>BoundMaxSum</b> compute the approximation ratio:
<p><font face="mono" size="1">BMax.getApproximationRatio(original_cop.actualValue(), cop.actualValue())</font></p></li>
<li>the final value for <i>original_cop</i> is retrieved:
<p><font face="mono" size="1">"Conclusion for original cop:\n" + original_cop.status();</font></p></li>
</ol>
<h3>Notes on this implementation</h3>
<p>A lot of work has been done, here.<br/>
I tried to implementat everything in the most easy-to-extend way. That's why you'd find several interfaces and a bounch
of abstract classes here and there.<br/>
Anyway, this code can be improved a lot.
</p>
<p>
This project has been developed on version 6.9.1 of NetBeans IDE.
</p>
<p>
NodeFunction, NodeVariable, and Edge doesn't have a public constructor.<br/>
A public method is used to get a new instance or an already-created instance.<br/>
This happens because we want NodeVariable of id 3 to be unique, like having only one Edge from f to x. This happens because we want NodeVariable of id 3 to be unique, like having only one Edge from f to x.<br/>
The code here implements a sort of Singleton design pattern.
</p>
<p>
For cloning an instance, a method getCloned has been created on classes that needed to be cloned.<br/>
Using the clone() instead caused a bunch of problems, sometimes the default clone() of Object was called and messed up everything.
</p>
<p>
Lower time-complexity has been always preferred rather than space-complexity.<br/>
So there are a lot of supporting data structures to reduce the time taken during execution to access objects or class fields.<br/>
This choice slows down initialization, but the gain obtained during the execution of the algorithm is better.
</p>
<p>
Regarding the possibility to make execution completely distributed, this version could be a good point to start.<br>
The actual implementation can manage more than one agent. An agent required a Post Service that manage the messages, but the Factor Graph representation is not distributed.<br/>
Keep in mind that Maximum Spanning Tree actually is not distributed, too.
</p>
<h4>Need help?</h4>
<p>Do not hesitate, contact me at <a href="mailto:[email protected]">[email protected]</a> <font color="#FFFFFF">58 times thank you.</font> </p>
</body>