Modeling dynamic graphs with binary decision diagrams

摘要

In one embodiment, a dynamic graph having a plurality of nodes is modeled with a Binary Decision Diagram (BDD). Each pair of nodes in the dynamic graph is modeled using a characteristic function, g({right arrow over (t)};{right arrow over (a)};{right arrow over (b)}), where: {right arrow over (t)} denotes a time; {right arrow over (a)} denotes a first node identifier; {right arrow over (b)} denotes a second node identifier; and g evaluates to 1 (or TRUE) if and only if an edge exists and connects nodes {right arrow over (a)} and {right arrow over (b)} at time {right arrow over (t)}. The BDD is a combination of all the characteristic functions corresponding to all unique pairs of nodes in the dynamic graph.

主权项

1. A method, performed by a computing device, comprising:
modeling a dynamic graph having a plurality of nodes with a Binary Decision Diagram (BDD), by modeling each pair of nodes in the dynamic graph using a characteristic function, g({right arrow over (t)}; {right arrow over (a)}; {right arrow over (b)}), where: {right arrow over (t)} denotes a time; {right arrow over (a)} denotes a first node identifier; {right arrow over (b)} denotes a second node identifier; and g evaluates to 1 if and only if an edge exists and connects nodes {right arrow over (a)} and {right arrow over (b)} at time {right arrow over (t)}; and querying the BDD for edges in the dynamic graph that exist between a time ti and a time tj by applying a logical AND operation to the BDD and THti({right arrow over (t)})· THtj+1({right arrow over (t)}), where:
THti({right arrow over (t)})≡1iff[{right arrow over (t)}]≧ti; andTHtj({right arrow over (t)})≡1iff[{right arrow over (t)}]≧tj.