Pseudocode to walk the tangle?

Question

I would like to pick a random node, call getNodeInfo and see it's latest milestone.

Then I'd like to walk the graph (depth first search? breadth first search?) backwards to the start and map the entire graph.

I.e. this is the "sync" operation a wallet would do when it first starts up and has zero stored transactions.

I've looked at the IRI java code but I'm missing the simple logic to take the milestone value from a node, and call GetTrytes to turn that into a full 2673 length tx, then take the Bundle, and/or TrunkTransaction, BranchTransaction, Address and get the next hop, and the next hop, etc.

When I try to write this logic myself I get a few hops, but then I quickly reached the end of some path and don't walk the entire tangle.

Does anyone have simple Pseudocode to walk the entire tangle?

Answer 1

Basic recursion for every open tip should do it. Just follow everything back to the origin or until you hit something you mapped already. I know that those object notations are very pseudo ;)

foreach(tangle_node open_tip)
{
  follow(parent_a);
  follow(parent_b);
}

follow(tangle_node x)
{     
  add_node_to_map(x); 
  if(root OR (x already_mapped))break;
  follow(x's_parent_a);
  follow(x's_parent_b);
}

Answer 2

I would use a list of "seen" and "unseen" transactions (essentially being a breadth-first search). Don't care about the bundle hashes or address hashes, they will only point you to transactions that are in the tangle elsewhere. The ones you have to follow are trunk transaction hash and branch transaction hash. The very first milestone will have a trunk transaction hash and branch transaction hash of 9999⋯9 (so all zero trytes), so if you treat that one as "seen", your algorithm will terminate eventually.

When confirmed transactions are all you need, start with the latest solid subtangle milestone hash; else you'd also have to query for tips (but I think the node will not give you the full list but only a selection) and add those too.

So in pseudocode:

seen = [999⋯9]
unseen = [latest_solid_subtangle_milestone_hash]
while (unseen is not empty) {
  tofetch = get_and_remove_first(unseen)
  tx = fetch(tofetch)
  process(tx)
  seen.add(tofetch)
  if (not seen.contains(tx.trunk) and not unseen.contains(tx.trunk))
    unseen.add(tx.trunk)
  if (not seen.contains(tx.branch) and not unseen.contains(tx.branch))
    unseen.add(tx.branch)
}