Ticket #3983 (assigned defect)

Opened 7 years ago

Last modified 6 years ago

refactor weighted random walks in subgraph isomorphism

Reported by: jberry Owned by: jberry
Priority: normal Milestone: 1.2
Version: 1.0 Severity: normal
Keywords: Cc:

Description

The prototype implementation calls weighted_random_walk for each walk through the colored graph. Each call recomputes the same thing: the distribution of weights across all neighbors of the supersource.

Now that we have greater confidence in the correctness and potential of the code, it should be re-worked. The cumulative weights coming out of each vertex of the colored graph should be pre-computed (XMT could do it with a linear recurrence for the supersource, then parallel for all other nodes). Then the weighted_random_walk can binary search for the correct next step.

This would make weighted_random_walk less general, but if it won't perform in this case, it probably won't perform in others either.

Perhaps we could use a CSR-like structure to hold the weights of incident edges to each vertex. The weighted_random_walk code would then binary search the appropriate sub-array for each step.

Change History

comment:1 Changed 6 years ago by gemacke

  • component Eldorado deleted

comment:2 Changed 6 years ago by gemacke

  • Owner changed from eldorado-graph@… to jberry
  • Status changed from new to assigned

comment:3 Changed 6 years ago by gemacke

  • Version set to 1.0

comment:4 Changed 6 years ago by gemacke

  • Milestone set to 1.2
Note: See TracTickets for help on using tickets.