2

I have a requirement where I have to label each node in a graph with a number. So that when I reach a leaf node traversing a path in that graph I can use the sum of all the node labels in that path to identify the path.

I know powers of two work. But it has a limitation that I cannot use any number that is greater than $2^{64}$ value. So the maximum number of nodes I can label with powers of $2$ is $64$. I am trying to find ways to remove this limitation.

Let's say the problem is like this:

There is a manual job process that involves 3 stages. Each stage has a set of employees to perform their tasks at that stage. If an employee is working in one stage he cannot be in another stage.

Let's say for the purpose of making it easy to understand, I labeled each employee with powers of 2.

Stage A: 2^1, 2^2, 2^3

Stage B: 2^4, 2^5, 2^6, 2^7, 2^8

Stage C: 2^9, 2^10, 2^11, 2^12, 2^13

So at the end of the process, I want to identify these different paths of moving the job from from Stage A to Stage B to Stage C with numbers.

Example: For a job:

Stage A: 2^2 worked

Stage B: 2^7 worked

Stace C: 2^11 worked

Sum of 2^2, 2^7 and 2^11 is the number that I use to identify this path with. Because I know these sums of powers of twos are always unique if you avoid duplicate powers.

But I can only use it for maximum of 64 employees. Because in Java programming language the integer limit is 2^64. I am trying to remove this limitation. Labelling each employee with text is easy but it is expensive with regards to cpu processing.

Any suggestions would be really helpful.

I am open to any set of numbers with no limitation like this, any mathematical operation between them, can be addition, multiplication, subtraction etc.

Thank you.

Ruby9191
  • 21
  • you can use only natural numbers? The sum of binary numbers of the kind $1000\ldots0$ is equivalent to sum powers of two, maybe you dont have limitation to simulate binary numbers longer than $64$ bits, using $n$-tuples of $64$ bits each position, by example. – Masacroso May 18 '17 at 16:30
  • Is there a limit on how many children a node can have int the tree? – M. Winter May 18 '17 at 16:30
  • 1
    A set of $65$ nodes has $2^{65}$ subsets (one of which is empty) and if it is a complete graph rather more possible paths. So you cannot identify each potential path uniquely by number if you are limited to $2^{64}$ numbers. But you mention leaf nodes: are you actually talking about trees? – Henry May 18 '17 at 16:31
  • Suppose your graph is a square ABCD with one more node V connected to D. No matter how you assign numbers to the nodes, you cannot, by sum alone, distinguish the path ABCDV from CBADV. – Barry Cipra May 18 '17 at 16:46
  • @M.Winter There is no limitation. – Ruby9191 May 18 '17 at 21:38
  • @Henry, By leaf node I mean the boundary node of the graph. In a directional graph. A node that has no outgoing connections/edges. – Ruby9191 May 18 '17 at 21:39
  • @BarryCipra The order of the nodes in the path is not important in the problem. Nodes can be in any order in the path. – Ruby9191 May 18 '17 at 21:45
  • @Masacroso That is interesting. I use 64 bits to label the first 64 nodes in the graph. After that keep extending the 64bits to 65, 66, 67 .... infinity? Could you please refer me to any texts/websites where it is explained? Thank you. – Ruby9191 May 18 '17 at 21:48
  • @Ruby9191 it was just an arbitrary idea that come to my mind. Instead of use only one number of $64$ bits to label each node you can try to use a list of numbers of $64$ bits to label each node... a list long enough to cover all possible labels for your graph. – Masacroso May 18 '17 at 22:11

0 Answers0