🌳 Flowchart Campos Algorithm

Minimum Routing Cost Spanning Tree - Detailed Process Flow

Start/End

Process

Decision

Algorithm

Output

📋 Main Flowchart: Campos Algorithm

🚀 START
Input: Graph G = (V, E, W)

STEP 1: Extract Edge Weights
weights[] = [w(e) for all e ∈ E]

STEP 2: Compute Statistics
μ = mean(weights)
σ = std_deviation(weights)
ratio = σ / μ

STEP 3: Adaptive Threshold
threshold = 0.4 + 0.005 × (n - 10)
n = number of nodes

DECISION:
Compare ratio vs threshold
Determine Graph Type

Branch by Heterogeneity

🟢 HOMOGENEOUS
ratio ≤ 0.3

Karakteristik:
• Semua weights hampir sama
• Contoh: {1,1,1,1} atau {5,5,5,5}
• LAN dengan uniform link costs

Parameters: C₁ = 0.2 C₂ = 0.6 C₃ = 0.2 C₄ = 1.0 ← Balanced C₅ = 1.0 ← Balanced

Strategi:
Like ADD Algorithm
Topology Priority

Inspired by ADD:
✓ Focus pada degree nodes
✓ Minimize relay nodes
✓ Ignore weights (semua sama)

🟡 SLIGHTLY HETERO
0.3 < ratio < threshold

Karakteristik:
• Weights bervariasi sedang
• Contoh: {1,2,3,4,5}
• Mixed wired/wireless networks

Parameters: C₁ = 0.2 C₂ = 0.6 C₃ = 0.2 C₄ = 1.0 ← Balanced C₅ = 1.0 ← Balanced

Strategi:
Hybrid Approach
Balanced Priority

Inspired by WONG:
✓ Consider distance to root
✓ Balance weight & topology
✓ Adaptive selection

🔴 HIGHLY HETERO
ratio ≥ threshold

Karakteristik:
• Weights sangat bervariasi
• Contoh: {1,10,100,1000,10000}
• WAN dengan varied link costs

Parameters: C₁ = 0.2 C₂ = 0.6 C₃ = 0.2 C₄ = 0.9 ← HIGH! C₅ = 0.1 ← LOW

Strategi:
Like PRIM Algorithm
Weight Priority

Inspired by PRIM:
✓ Prioritize cheap edges
✓ Minimize edge weights
✓ Like MST approach

All branches converge

STEP 4: Root Selection (Spanning Potential)
For each node v:
sp_v = C₁×d_v + C₂×(d_v/s_v) + C₃×(1/m_v)
Root = argmax(sp_v)

Penjelasan sp_v:
• d_v = degree(v) - jumlah tetangga
• s_v = sum of weights adjacent edges
• m_v = max weight adjacent edge
→ Node dengan high degree + low weights = good root

STEP 5: Initialize Tree
T = {root}
cost_to_root[root] = 0
candidates = neighbors(root)

STEP 6: Compute Selection Criteria
For each candidate v:
• cf_v = cost_to_root[parent] + weight(parent,v)
• wd_v = C₄×weight + C₅×cf_v
• jsp_v = (d_v+d_p) + (d_v+d_p)/(s_v+s_p)

STEP 7: Select Best Candidate
Primary: MIN(wd_v)
Tie-breaker: MAX(jsp_v)

STEP 8: Add to Tree
T.add_edge(parent, v)
Update cost_to_root[v]
Add neighbors(v) to candidates

All nodes in T?

NO → Loop to Step 6

YES ↓

OUTPUT: Minimum Routing Cost Tree
T = spanning tree with n-1 edges
Routing Cost = Σ d_T(u,v) for all pairs

🎯 END
MRCT Computed Successfully

🔄 Algorithm Comparison & Integration

PRIM (MST)

O(E log V)

Fast

MST Only

Used in Campos:

Weight prioritization for highly heterogeneous graphs (C₄=0.9)

ADD

O(V log V)

Fastest

Ignore Weights

Used in Campos:

Spanning potential (sp_v) for root selection & jsp_v metric

WONG

O(V² log V)

Best MRCT

Slow

Used in Campos:

Distance-to-root awareness (cf_v) in selection criteria

CAMPOS

O(E log V)

Fast

Good MRCT

Adaptive

The Hybrid:

Best of all worlds - combines strengths, avoids weaknesses

📊 Decision Tree: Parameter Selection

Compute: ratio = σ/μ
threshold = 0.4 + 0.005×(n-10)

🎯 Key Formulas Reference

Spanning Potential

sp_v = C₁×d_v + C₂×(d_v/s_v) + C₃×(1/m_v) C₁=0.2, C₂=0.6, C₃=0.2

From ADD algorithm
For root selection

Weight-Distance

wd_v = C₄×weight + C₅×cf_v C₄, C₅ = adaptive

From Wong + Prim
For node selection

Joint Spanning Potential

jsp_v = sd_v + (sd_v/sw_v) sd = d_v + d_parent sw = s_v + s_parent

From ADD algorithm
For tie-breaking

Cost to Root

cf_v = cost_to_root[parent] + weight(parent, v) Distance awareness

From Wong algorithm
For path cost tracking

🔀 Integration Points: Where Algorithms Contribute

📈 Execution Example: Step-by-Step Flow

Example Graph: 6 nodes, edges with weights {1,2,3,4,5,6,7}

INPUT: G with 6 nodes
Edges: (1,2,2), (1,3,4), (2,3,1), (2,4,3), (2,5,6), (3,5,5), (3,6,2), (5,6,7)

Step 1-3: Compute Heterogeneity
weights = [1,2,2,3,4,5,6,7]
μ = 3.75, σ = 2.12
ratio = 0.565
threshold = 0.38

ratio (0.565) ≥ threshold (0.38)
→ HIGHLY HETEROGENEOUS

Parameters Set:
C₄ = 0.9 (prioritize weight)
C₅ = 0.1 (minimize distance consideration)

Step 4: Root Selection
sp₁=0.65, sp₂=1.03, sp₃=1.05, sp₄=0.47, sp₅=0.73, sp₆=0.61
Root = Node 3 (highest sp)

Step 5: Initialize
T = {3}
Candidates: {1, 2, 5, 6}

Iteration 1:
Compute wd for candidates:
wd₁=4.0, wd₂=1.0, wd₅=5.0, wd₆=2.0
→ Select Node 2 (min wd)

T = {3, 2}
Edge added: (3,2,1)
New candidates from node 2: {1, 4, 5}

Iteration 2:
All candidates: wd₁=2.1, wd₆=2.0, wd₄=3.1, wd₅=5.0
→ Select Node 6 (min wd)

T = {3, 2, 6}
Edge added: (3,6,2)

Continue iterations...
Add Node 1 → Node 4 → Node 5

FINAL TREE:
Edges: (3,2), (2,1), (3,6), (2,4), (3,5)
MST Cost = 13
Routing Cost = 50

✅ SUCCESS
MRCT optimal untuk graph ini!

🎯 Summary: Decision Points in Campos

Decision Point	Condition	Action	Inspired By
Graph Type	ratio ≤ 0.3	C₄=1.0, C₅=1.0 Balanced approach	ADD
Graph Type	0.3 < ratio < threshold	C₄=1.0, C₅=1.0 Balanced approach	WONG
Graph Type	ratio ≥ threshold	C₄=0.9, C₅=0.1 Prioritize weight	PRIM
Root Selection	Always	Use sp_v formula Select max(sp_v)	ADD
Node Selection	Primary criterion	Select min(wd_v) Uses weight + distance	WONG + PRIM
Tie Breaking	wd_v equal	Select max(jsp_v) Prefers high spanning potential	ADD

🎓 Key Takeaways

✅ Campos is NOT just one algorithm - it's an adaptive framework that switches strategies
✅ Three graph types determine which algorithm inspires the behavior
✅ Parameters C₄ and C₅ are the key to adaptation (0.9/0.1 vs 1.0/1.0)
✅ Root selection ALWAYS uses ADD's approach (spanning potential)
✅ Node selection is hybrid: weight-distance (Wong+Prim) with tie-breaking (ADD)
✅ Time complexity stays O(E log V) like Prim/IEEE - no n² overhead like Wong
✅ Result quality approaches Wong but executes 30× faster

🌟 The Beauty of Campos

Campos Algorithm adalah chef yang master - mengambil teknik terbaik dari ADD, Wong, dan Prim, lalu mencampur dengan proporsi adaptif berdasarkan bahan (graph) yang tersedia. Hasilnya: hidangan optimal dengan waktu memasak minimal! 👨‍🍳