Information processing unit, terminal unit, information processing method, key generation method and program

A terminal unit comprising:

• a key generation section to generate a set key for decrypting encrypted contents or an encrypted contents key based on a directed graph, wherein the directed graph is generated by
• configuring an entire binary tree made up of n-number of leaf nodes, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes and dividing the entire tree into a plurality of base subtrees including ni/y number of leaf nodes to form a y-level (y is a divisor of log(n)) hierarchical structure such that root nodes of the base subtrees at a lower level coincide with leaf nodes of the base subtree at an upper level,
• defining a set of leaf nodes located lower than a node w of the entire tree as Aw,
• defining a leaf node located on i-th left of a certain leaf node v as v(−1) and a leaf node located on i-th right as v(+1) in the leaf nodes of the base subtrees,
• regarding two leaf nodes u and v (v is on right of u) of the base subtrees, defining a set (u→v) as {Au, Au∪Au(+1), . . . , Au∪ . . . ∪Av} and a set (u←v) as {Av, Av∪Av(−1), . . . , Av∪ . . . ∪Au},
• when a leaf node located at a left end is defined as lv′ and a leaf node located at a right end is rv′ in a plurality of leaf nodes located lower than a node v of the base subtrees,
• correlating a set (lroot′→rroot′) and a set (lroot′(+1)←rroot′) with a root node of the base subtree at a top level,
• correlating a set (lv′→rv′(−1)) and a set (lv′(+1)←rv′) with a root node v of the base subtrees at a level other than the top level,
• if an intermediate node v of each subtree is located on left of its parent node, correlating a set (lv′(+1)←rv′) with the intermediate node v,
• if an intermediate node v of each subtree is located on right of its parent node, correlating a set (lv′→rv′(−1)) with the intermediate node v, and
• generating a directed graph where coordinate points corresponding to subsets included in the set (lroot′→rroot′) or the set (lv′→rv′(−1)) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right and a directed edge connecting the coordinate points is set and/or a directed graph where coordinate points corresponding to subsets included in the set (lroot′(+1)←rroot′) or the set (lv′(+1)←rv′) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left and a directed edge connecting the coordinate points is set, for each of the root node and the intermediate node v of the respective base subtrees.

An information processing method comprising:

• a step of configuring an entire binary tree made up of n-number of leaf nodes, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes and dividing the entire tree into a plurality of base subtrees including n1/y number of leaf nodes to form a y-level (y is a divisor of log(n)) hierarchical structure such that root nodes of the base subtrees at a lower level coincide with leaf nodes of the base subtree at an upper level;
• a step of defining a set of leaf nodes located lower than a node w of the entire tree as Aw,
• defining a leaf node located on i-th left of a certain leaf node v as v(−1) and a leaf node located on i-th right as v(+i) in the leaf nodes of the base subtrees,
• regarding two leaf nodes u and v (v is on right of u) of the base subtrees, defining a set (u→v) as {Au, Au∪Au(+1), . . . , Au∪ . . . ∪Av} and a set (u←v) as {Av, Av∪Av(−1), . . . , Av∪ . . . ∪Au},
• when a leaf node located at a left end is defined as lv′ and a leaf node located at a right end is rv′ in a plurality of leaf nodes located lower than a node v of the base subtrees,
• correlating a set (lroot′→rroot′) and a set (lroot′(+1)←rroot′) with a root node root of the base subtree at a top level,
• correlating a set (lv′→rv′(−1)) and a set (lv′(+1)←rv′) with a root node v of the base subtrees at a level other than the top level,
• if an intermediate node v of each subtree is located on left of its parent node, correlating a set (lv′(+1)←rv′) with the intermediate node v, and
• if an intermediate node v of each subtree is located on right of its parent node, correlating a set (lv′→rv′(−1)) with the intermediate node v;
• and
• a step of generating a directed graph where coordinate points corresponding to subsets included in the set (lroot′→rroot′) or the set (lv′→rv′(−1)) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right and a directed edge connecting the coordinate points is set and/or a directed graph where coordinate points corresponding to subsets included in the set (lroot′(+1)←rroot′) or the set (lv′(+1)←rv′) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left and a directed edge connecting the coordinate points is set, for each of the root node and the intermediate node v of the respective base subtrees.

A key generation method to generate a set key for decrypting encrypted contents or an encrypted contents key based on a directed graph, wherein the directed graph is obtained by:

• configuring an entire binary tree made up of n-number of leaf nodes, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes and dividing the entire tree into a plurality of base subtrees including n1/y number of leaf nodes to form a y-level (y is a divisor of log(n)) hierarchical structure such that root nodes of the base subtrees at a lower level coincide with leaf nodes of the base subtree at an upper level,
• defining a set of leaf nodes located lower than a node w of the entire tree as Aw,
• defining a leaf node located on i-th left of a certain leaf node v as v(−i) and a leaf node located on i-th right as v(+1) in the leaf nodes of the base subtrees,
• regarding two leaf nodes u and v (v is on right of u) of the base subtrees, defining a set (u→v) as {Au, Au∪Au(+1), . . . , Au∪ . . . ∪Av} and a set (u←v) as {Av, Av∪Av(−1), . . . , Av∪ . . . ∪Au},
• when a leaf node located at a left end is defined as lv′ and a leaf node located at a right end is rv′ in a plurality of leaf nodes located lower than a node v of the base subtrees,
• correlating a set (lroot′→rroot′) and a set (lroot′(+1)←rroot′) with a root node root of the base subtree at a top level,
• correlating a set (lv′→rv′(−1)) and a set (lv′(+1)←rv′) with a root node v of the base subtrees at a level other than the top level,
• if an intermediate node v of each subtree is located on left of its parent node, correlating a set (lv′(+1)←rv′) with the intermediate node v,
• if an intermediate node v of each subtree is located on right of its parent node, correlating a set (lv′→rv′(−1)) with the intermediate node v, and
• generating a directed graph where coordinate points corresponding to subsets included in the set (lroot′→rroot′) or the set (lv′→rv′(−1)) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right and a directed edge connecting the coordinate points is set and/or a directed graph where coordinate points corresponding to subsets included in the set (lroot′(+1)←rroot′) or the set (lv′(+1)←rv′) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left and a directed edge connecting the coordinate points is set, for each of the root node and the intermediate node v of the respective base subtrees.

A program causing a computer to execute processing comprising:

• a step of configuring an entire binary tree made up of n-number of leaf nodes, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes and dividing the entire tree into a plurality of base subtrees including n1/y number of leaf nodes to form a y-level (y is a divisor of log(n)) hierarchical structure such that root nodes of the base subtrees at a lower level coincide with leaf nodes of the base subtree at an upper level;
• a step of defining a set of leaf nodes located lower than a node w of the entire tree as Aw,
• defining a leaf node located on i-th left of a certain leaf node v as v(−1) and a leaf node located on i-th right as v(+1) in the leaf nodes of the base subtrees,
• regarding two leaf nodes u and v (v is on right of u) of the base subtrees, defining a set (u→v) as {Au, Au∪Au(+1), . . . , Au∪ . . . ∪Av} and a set (u←v) as {Av, Av∪Av(−1), . . . , Av∪ . . . ∪Au},
• when a leaf node located at a left end is defined as lv′ and a leaf node located at a right end is rv′ in a plurality of leaf nodes located lower than a node v of the base subtrees,
• correlating a set (lroot′→rroot′) and a set (lroot′(+1)←rroot′) with a root node root of the base subtree at a top level,
• correlating a set (lv′→rv′(−1)) and a set (lv′(+1)←rv′) with a root node v of the base subtrees at a level other than the top level,
• if an intermediate node v of each subtree is located on left of its parent node, correlating a set (lv′(+1)←rv′) with the intermediate node v, and
• if an intermediate node v of each subtree is located on right of its parent node, correlating a set (lv′→rv′(−1)) with the intermediate node v;
• and
• a step of generating a directed graph where coordinate points corresponding to subsets included in the set (lroot′→rroot′) or the set (lv′→rv′(−1)) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right and a directed edge connecting the coordinate points is set and/or a directed graph where coordinate points corresponding to subsets included in the set (lroot′(+1)←rroot′) or the set (lv′(+1)←rv′) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left and a directed edge connecting the coordinate points is set, for each of the root node and the intermediate node v of the respective base subtrees.

A program causing a computer to execute a step of generating a set key for decrypting encrypted contents or an encrypted contents key based on a directed graph, wherein the directed graph is obtained by:

• configuring an entire binary tree made up of n-number of leaf nodes, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes and dividing the entire tree into a plurality of base subtrees including n1/y number of leaf nodes to form a y-level (y is a divisor of log(n)) hierarchical structure such that root nodes of the base subtrees at a lower level coincide with leaf nodes of the base subtree at an upper level,
• defining a set of leaf nodes located lower than a node w of the entire tree as Aw,
• defining a leaf node located on i-th left of a certain leaf node v as v(−i) and a leaf node located on i-th right as v(+1) in the leaf nodes of the base subtrees,
• regarding two leaf nodes u and v (v is on right of u) of the base subtrees, defining a set (u→v) as {Au, Au∪Au(+1), . . . , Au∪ . . . ∪Av} and a set (u←v) as {Av, Av∪Av(−1), . . . , Av∪ . . . ∪Au},
• when a leaf node located at a left end is defined as lv′ and a leaf node located at a right end is rv′ in a plurality of leaf nodes located lower than a node v of the base subtrees,
• correlating a set (lroot′→rroot′) and a set (lroot′(+1)←rroot′) with a root node root of the base subtree at a top level,
• correlating a set (lv′→rv′(−1)) and a set (lv′(+1)←rv′) with a root node v of the base subtrees at a level other than the top level,
• if an intermediate node v of each subtree is located on left of its parent node, correlating a set (lv′(+1)←rv′) with the intermediate node v,
• if an intermediate node v of each subtree is located on right of its parent node, correlating a set (lv′→rv′(−1)) with the intermediate node v, and
• generating a directed graph where coordinate points corresponding to subsets included in the set (lroot′→rroot′) or the set (lv′→rv′(−1)) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right and a directed edge connecting the coordinate points is set and/or a directed graph where coordinate points corresponding to subsets included in the set (lroot′(+1)←rroot′) or the set (lv′(+1)←rv′) are arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left and a directed edge connecting the coordinate points is set, for each of the root node and the intermediate node v of the respective base subtrees.

An information processing unit to process a temporary directed graph formed by arranging a plurality of directed edges with a length of ni/k (i=0, 1, . . . , x−1) on first to fourth horizontal coordinate axes according to a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k for a given integer k,

• in a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, where a number assigned to a leaf node located at a left end is defined as lv and a number assigned to a leaf node located at a right end is defined as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v,
• for natural numbers i and j (i≦j), it is assumed a set (i→j) is notated as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}}, and a set (i←j) is notated as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}},
• a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set,
• the information processing unit comprising:
• a temporary directed graph acquisition section to acquire the temporary directed graph;
• a directed graph generation section to generate a directed graph by leaving a longer directed edge among a plurality of directed edges constituting the temporary directed graph acquired by the temporary directed graph acquisition section;
• and
• a key generation section to generate a set key for encrypting contents or a contents key based on the directed graph.

An information processing unit comprising:

• a tree structure setting section to configure a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, define a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, . . . , j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers and j (i≦j), and set a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• a coordinate axis setting section to
• set a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• place two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes, and
• set a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and place a second temporary coordinate point on right of the first temporary coordinate point;
• and
• a directed graph generation section to
• generate directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by
• setting a given integer k,
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k, and
• for each of integer i=0 to x−1,
• forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k,
• forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k,
• excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and
• excluding directed edges other than a longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes, and
• generate a directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the directed graph related to the set (1→n−1).

A terminal unit comprising:

• a key generation section to generate a set key for decrypting contents or a contents key based on a directed graph, wherein the directed graph is generated by:
• configuring a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, j−1, . . . , j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), and setting a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v,
• setting a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• placing two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes,
• setting a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and placing a second temporary coordinate point on right of the first temporary coordinate point,
• generating directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by
• setting a given integer k,
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k, and
• for each of integer i=0 to x−1,
• forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k,
• forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k,
• excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and
• excluding directed edges other than a longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes, and
• generating a directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the directed graph related to the set (1→n−1).

An information processing method to process a temporary directed graph formed by arranging a plurality of directed edges with a length of ni/k (i=0, 1, . . . , x−1) on first to fourth horizontal coordinate axes according to a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k for a given integer k,

• in a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, where a number assigned to a leaf node located at a left end is defined as lv and a number assigned to a leaf node located at a right end is defined as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v,
• for natural numbers i and j (i≦j), it is assumed a set (i→j) is notated as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, . . . , j}}, and a set (i←j) is notated as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}},
• a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set,
• the information processing method comprising:
• a temporary directed graph acquisition step of acquiring the temporary directed graph;
• a directed graph generation step of generating a directed graph by leaving a longer directed edge among a plurality of directed edges constituting the temporary directed graph acquired by the temporary directed graph acquisition section;
• and
• a key generation step of generating a set key for encrypting contents or a contents key based on the directed graph.

An information processing method comprising:

• a tree structure setting step of:
• configuring a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), and setting a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• a coordinate axis setting step of:
• setting a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• placing two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes, and
• setting a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and placing a second temporary coordinate point on right of the first temporary coordinate point;
• and
• a directed graph generation step of:
• generating directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv−rv−1) by
• setting a given integer k,
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k, and
• for each of integer i=0 to x−1,
• forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k,
• forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k,
• excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and
• excluding directed edges other than a longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes, and
• generating a directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the directed graph related to the set (1→n−1).

A key generation method comprising:

• a key generation step of generating a set key for decrypting contents or a contents key based on a directed graph, wherein the directed graph is generated by:
• configuring a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, . . . , j}}, and a set (i≦j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), and setting a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v,
• setting a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right,
• a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• for each of the intermediate nodes,
• a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and
• a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left,
• placing two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes,
• setting a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and placing a second temporary coordinate point on right of the first temporary coordinate point,
• generating directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by
• setting a given integer k,
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k, and
• for each of integer i=0 to x−1,
• forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k,
• forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k,
• excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and
• excluding directed edges other than a longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes, and
• generating a directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the directed graph related to the set (1→n−1).