[go: up one dir, main page]

WO2021111606A1 - グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体 - Google Patents

グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体 Download PDF

Info

Publication number
WO2021111606A1
WO2021111606A1 PCT/JP2019/047708 JP2019047708W WO2021111606A1 WO 2021111606 A1 WO2021111606 A1 WO 2021111606A1 JP 2019047708 W JP2019047708 W JP 2019047708W WO 2021111606 A1 WO2021111606 A1 WO 2021111606A1
Authority
WO
WIPO (PCT)
Prior art keywords
vertices
matrix
graph
frontier
adjacency
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2019/047708
Other languages
English (en)
French (fr)
Inventor
晴道 横山
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Priority to JP2021562409A priority Critical patent/JP7497734B2/ja
Priority to PCT/JP2019/047708 priority patent/WO2021111606A1/ja
Priority to US17/779,653 priority patent/US20220414077A1/en
Publication of WO2021111606A1 publication Critical patent/WO2021111606A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G06Q10/40—
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • G06F16/285—Clustering or classification
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00—Subject matter not provided for in other groups of this subclass

Definitions

  • the present invention relates to a graph search device for executing graph search, a graph search method, and a computer-readable recording medium for recording a program for realizing these.
  • Graph search is an important technology for performing SNS (Social Networking Service) analysis (clustering relationships between users, etc.) and road analysis connecting points on an electronic map (shortest path search between points, etc.). Is. Further, in the graph search, it is known that the structure of the graph is represented by using an adjacency matrix.
  • SNS Social Networking Service
  • Patent Document 1 discloses a pattern extraction device capable of efficiently obtaining the number of connected components of a graph.
  • the connection relationship of patterns is expressed by using an adjacency matrix of vertices, and the number of connected components of the graph is obtained by counting the number of diagonalized blocks of the adjacency matrix of vertices. ..
  • An example of an object of the present invention is to provide a graph search device, a graph search method, and a computer-readable recording medium that shortens the time required for graph search.
  • the graph search device in one aspect of the present invention is used.
  • a generation means that selects a plurality of vertices based on the adjacency of vertices included in the graph and generates a frontier matrix in which different labels are set for each element corresponding to the selected vertices.
  • a classification means for classifying vertices using an adjacency matrix representing the adjacency relationship of vertices included in the graph and the frontier matrix. It is characterized by having.
  • the graph search method in one aspect of the present invention is used.
  • a plurality of vertices are selected based on the adjacency of the vertices included in the graph, and a frontier matrix in which different labels are set for each element corresponding to the selected vertices is generated.
  • B The vertices are classified by using the adjacency matrix representing the adjacency relationship of the vertices included in the graph and the frontier matrix.
  • a computer-readable recording medium on which a program according to one aspect of the present invention is recorded may be used.
  • B A step of classifying vertices using an adjacency matrix representing the adjacency relationship of vertices included in the graph and the frontier matrix. It is characterized in that it records a program containing an instruction to execute.
  • the time required for graph search can be shortened.
  • FIG. 1 is a diagram for explaining an example of a graph search device.
  • FIG. 2 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 3 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 4 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 5 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 6 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 7 is a diagram for explaining an example of a system having a graph search device.
  • FIG. 8 is a diagram for explaining an example of selecting vertices.
  • FIG. 1 is a diagram for explaining an example of a graph search device.
  • FIG. 2 is a diagram for explaining an example of an adjacency matrix and a frontier matrix.
  • FIG. 3 is a diagram for explaining an example of an adj
  • FIG. 9 is a diagram for explaining the operation of the modified example 1.
  • FIG. 10 is a diagram for explaining the operation of the modified example 1.
  • FIG. 11 is a diagram for explaining the operation of the modified example 1.
  • FIG. 12 is a diagram for explaining the operation of the modified example 2.
  • FIG. 13 is a diagram for explaining the operation of the modified example 2.
  • FIG. 14 is a diagram for explaining the operation of the modified example 2.
  • FIG. 15 is a diagram for explaining an example of the operation of the graph search device.
  • FIG. 16 is a diagram showing an example of a computer that realizes a graph search device.
  • FIG. 1 is a diagram for explaining an example of a graph search device.
  • the graph search device 10 shown in FIG. 1 is a device that shortens the time required for graph search. Further, as shown in FIG. 1, the graph search device 10 has a generation unit 11 and a classification unit 12.
  • the generation unit 11 selects a plurality of vertices based on the adjacency of the vertices included in the graph, and generates a frontier matrix in which different labels are set for each element corresponding to the selected vertices.
  • the classification unit 12 classifies the vertices by using the adjacency matrix and the frontier matrix that represent the adjacency relationship of the vertices included in the graph.
  • FIG. 2 is diagrams for explaining an example of an adjacency matrix and a frontier matrix.
  • the graph shown in FIG. 2 has vertices 0 to 9.
  • the adjacency matrix is a matrix for representing vertices adjacent to the target vertices.
  • the frontier matrix is a matrix used to classify the vertices of a graph into concatenated sets.
  • a concatenated set is a set that classifies reachable vertices.
  • the adjacency matrix (R) in FIG. 2 is an adjacency matrix corresponding to the graph in FIG.
  • the adjacency relationship of vertex 0 will be described. Since the vertices adjacent to the vertices 0 of the graph are the vertices 1 and 2, in the adjacency matrix of FIG. 2, "1" is set for the elements corresponding to the vertices 1 and 2 of the row and the column corresponding to the vertex 0. Since the vertices other than the vertices 1 and 2 are not adjacent to the vertices 0, "0" is set for the element corresponding to the vertices other than the vertices 1 and 2. For each of the vertices existing in the graph other than the vertex 0, the adjacency relationship is expressed in the adjacency matrix in the same manner as the vertex 0.
  • the frontier matrix (F1) in FIG. 2 is a frontier matrix used at the start of classification.
  • the label "01” is assigned to the element of the frontier matrix (F1) corresponding to the vertex 0 which is the starting point.
  • the label "10” is assigned to the element of the frontier matrix (F1) corresponding to the vertex 5 which is the starting point.
  • "00" is assigned as an initial value to vertices other than vertices 0 and 5 that are not start points.
  • the bit width of the label is determined based on the number of vertices that serve as the starting point. In the frontier matrix of FIG. 2, since there are two vertices as starting points, the bit width is 2 bits. When there are three starting point vertices, the bit width is 3 bits. When the bit width is 3 bits, it is set to, for example, "100".
  • the matrix of FIG. 3 (first matrix) is the result (M1) of the product of the adjacency matrix (R) and the frontier matrix (F1) of FIG.
  • the product result (M1) shows that the elements corresponding to the vertices 1 and 2 are connected to the vertices 0.
  • the label "01" is attached.
  • the product result (M1) shows the label "10” indicating that the elements corresponding to the vertices 4 and 7 are connected to the vertices 5.
  • the logical product is used to calculate the product of the elements, and the logical sum is used to calculate the sum of the elements.
  • the product result (M1) in FIG. 3 be the frontier matrix (F2).
  • the product result (M1) since the product result (M1) does not have an element corresponding to the searched vertices, the product result (M1) is used as a new frontier matrix (F2). However, if the product result (M1) already has an element corresponding to the searched vertices (classified vertices), the element corresponding to the searched vertices is excluded from the product result (M1).
  • the sum result (S1) is a matrix for representing the searched vertices. Therefore, in the sum result (S1) of FIG. 3, the elements corresponding to the vertices 0, 1, 2, 4, 5, and 7 already searched are labeled.
  • the logical sum is used to calculate the sum of the elements.
  • the matrix of FIG. 4 (first matrix) is the result (M2) of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F2) of FIG.
  • the product result (M2) shows that the elements corresponding to the vertices 0 and 3 are connected to the vertices 0.
  • the label "01" is attached.
  • the product result (M2) shows that the elements corresponding to the vertices 5, 6 and 8 are connected to the vertices 5.
  • "10" is added.
  • the frontier matrix (F3) is generated using the product result (M2) of FIG. 4 and the sum result (S1).
  • the product result (M2) since the product result (M2) has labels for the elements corresponding to the searched vertices 0, 1, 2, 4, 5, and 7, the searched vertices are found from the product result (M2). Exclude the element corresponding to.
  • a new frontier matrix (F3) is generated in which the elements corresponding to the labeled vertices 3, 6 and 8 remain and "00" is assigned to the other vertices. Label.
  • the sum result (S2) is the sum result of the product result (M2) of FIG. 4 and the frontier matrix (F2) of FIG. Since the sum result (S2) is a matrix representing the already searched vertices, the elements corresponding to the vertices 0, 1, 2, 3, 4, 5, 6, 7, and 8 are labeled.
  • the matrix of FIG. 5 (first matrix) is the result (M3) of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F3) of FIG.
  • the element corresponding to the vertex 1 of the product result (M3) is labeled with the label “01” indicating that it is connected to the vertex 0.
  • the start points are the vertices 6 and 8
  • the frontier matrix (F4) is generated using the product result (M3) and the sum result (S2) of FIG.
  • the product result (M3) since the product result (M3) has labels for the elements corresponding to the searched vertices 0 to 8, the elements corresponding to the searched vertices are excluded from the product result (M3).
  • a new frontier matrix (F4) is generated in which the elements corresponding to the labeled vertices 9 remain and "00" is assigned to the other vertices.
  • the sum result (S3) is the result of the sum of the product result (M3) of FIG. 5 and the frontier matrix (F3) of FIG.
  • the elements corresponding to vertices 0 to 3 are labeled with the label "01", and the elements corresponding to the vertices 4 to 9 are labeled with the level "10". That is, the elements corresponding to the vertices are classified by labels in the same manner as the concatenated set of vertices shown in the graph.
  • the time required for graph search can be shortened.
  • FIG. 7 is a diagram for explaining an example of a system having a graph search device.
  • the system in this embodiment includes a graph search device 10, an external device 20, and an output device 30.
  • the graph search device 10 includes an acquisition unit 13, an adjacency matrix generation unit 14, and an output information generation unit 15 in addition to the generation unit 11 and the classification unit 12.
  • the graph search device 10 is, for example, a vector processor, a CPU (Central Processing Unit), an FPGA (Field-Programmable Gate Array), or an information processing device such as a server computer, a personal computer, or a mobile terminal equipped with the same.
  • a vector processor Central Processing Unit
  • FPGA Field-Programmable Gate Array
  • information processing device such as a server computer, a personal computer, or a mobile terminal equipped with the same.
  • the external device 20 is a device having data necessary for graph search.
  • the external device 20 may be a storage device such as a database that stores data used for SNS analysis, analysis of roads connecting points on an electronic map, a server computer, a personal computer, a mobile terminal, or the like.
  • the external device 20 communicates with the graph search device 10 by wire or wirelessly, and transmits data to the graph search device 10.
  • the output device 30 acquires the output information converted into an outputable format by the output information generation unit 15, and outputs the generated image, sound, and the like based on the output information.
  • the output device 30 is, for example, an image display device using a liquid crystal, an organic EL (Electro Luminescence), or a CRT (Cathode Ray Tube). Further, the image display device may include an audio output device such as a speaker.
  • the output device 30 may be a printing device such as a printer.
  • the graph search device will be described.
  • the acquisition unit 13 acquires data necessary for performing a graph search for the target graph. Specifically, the acquisition unit 13 receives the data transmitted from the external device 20 and outputs the data to the adjacency matrix generation unit 14. The acquisition unit 13 receives data by communicating with the external device 20 by wire or wirelessly, for example.
  • the adjacency matrix generation unit 14 generates an adjacency matrix representing the adjacency relationship of vertices for the target graph by using the data required for the graph search. Specifically, the adjacency matrix generation unit 14 first acquires data necessary for graph search. Subsequently, the adjacency matrix generation unit 14 generates an adjacency matrix corresponding to the target graph by using the plurality of vertices included in the target graph and the adjacency relations of the vertices. The adjacency matrix generation unit 14 generates, for example, the adjacency matrix (R) as shown in FIG. 2 described above.
  • the generation unit 11 selects a plurality of vertices based on the adjacency of the vertices included in the graph, and generates a frontier matrix in which different labels are set for each element corresponding to the selected vertices. Specifically, first, the generation unit 11 selects a plurality of vertices from the vertices included in the graph.
  • the user may arbitrarily select a plurality of vertices, or the generation unit 11 may select a plurality of vertices.
  • the generation unit 11 may select preset vertices or may select based on the number of vertices.
  • the generation unit 11 sets different labels for the elements corresponding to the selected vertices in the frontier matrix having the same number of rows as the number of vertices.
  • the generation unit 11 generates, for example, the frontier matrix (F1) as shown in FIG. 2 described above. Further, the generation unit 11 determines the bit width of the label based on the number of selected vertices.
  • the classification unit 12 refers to the result of the sum representing the vertices that have been searched for the graph (second matrix) from the result of the product of the adjacency matrix and the frontier matrix (first matrix), and the element corresponding to the searched vertices. Is excluded to generate a new frontier matrix. After that, the classification unit 12 calculates the sum of the product result and the sum result, generates a new sum result (second matrix), and classifies the vertices.
  • the classification unit 12 acquires the adjacency matrix and the frontier matrix. Subsequently, the classification unit 12 calculates the result of the product of the adjacency matrix and the frontier matrix. Subsequently, the classification unit 12 refers to the sum result, and if the product result has a searched vertex, the classification unit 12 excludes the element corresponding to the searched vertex from the product result and generates a new frontier matrix.
  • the generation unit 11 generates new frontier matrices (F3) and (F4), for example, as described above with reference to FIGS. 4 and 5.
  • the classification unit 12 calculates the sum of the product result and the sum result, generates a new sum result, and classifies the vertices.
  • the generation unit 11 generates new sum results (S1), (S2), and (S3), for example, as described above with reference to FIGS. 3 to 6.
  • the output information generation unit 15 generates output information used to output one or more of a graph, an adjacency matrix, a frontier matrix, a product result, a sum result, and the like to an output device. After that, the output information generation unit 15 transmits the generated output information to the output device.
  • the labels of the vertices in the same concatenated set are unified to the same label so that the same classification as the actual graph can be performed.
  • FIG. 8 is a diagram for explaining an example of selecting vertices.
  • 9, 10, and 11 are diagrams for explaining the operation of the first modification.
  • FIG. 8 is an example in which the generation unit 11 generates a frontier matrix (F1') when vertices 4 and 7 are selected as start points.
  • F1' frontier matrix
  • FIG. 9 is an example in which the classification unit 12 generates the result (M1') of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F1') of FIG.
  • the classification unit 12 sets the elements corresponding to the overlapping vertices 5 and 6 with a label representing the logical sum of the label "01" set at the vertex 4 and the label "10" set at the vertex 7. Add "11".
  • the product result (M1') in FIG. 9 be the frontier matrix (F2').
  • the product result (M1') since the product result (M1') does not have an element corresponding to the searched vertices, the product result (M1') is used as a new frontier matrix (F2').
  • the sum result (S1') is a matrix for representing the searched vertices. Therefore, the sum result (S1') of FIG. 9 is labeled with the elements corresponding to the already searched vertices 4, 5, 6, 7, and 8.
  • FIG. 10 is an example in which the classification unit 12 generates the result (M2') of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F2') of FIG.
  • the classification unit 12 attaches the label “11” to the element corresponding to the overlapping vertices 4 and 7.
  • the classification unit 12 generates a frontier matrix (F3') using the product result (M2') of FIG. 10 and the sum result (S1').
  • the product result (M2') since the product result (M2') has labels for the elements corresponding to the searched vertices 4, 7, and 9, the elements corresponding to the searched vertices from the product result (M2'). Exclude.
  • a new frontier matrix (F3') is generated in which the elements corresponding to the labeled vertices 9 remain and "00" is assigned to the other vertices.
  • the classification unit 12 calculates the result of the sum of the product result (M2') of FIG. 10 and the frontier matrix (F3') of FIG. 2 (S2': second matrix).
  • the sum result (S2') of FIG. 11 the elements corresponding to the vertices 4 to 9 already searched are labeled. In this way, it continues until all the elements corresponding to vertices 4 to 9 are labeled "11".
  • the levels of the same concatenated set can be set to the same label, so that the vertices can be classified.
  • the labels of the vertices in the same concatenated set are unified to the same label so that the same classification as the actual graph can be performed.
  • the classification unit 12 when the classification unit 12 detects overlapping vertices, it generates connection information indicating that the vertices that are the start points of the overlapping vertices are in the same connection set and stores them in the storage unit. Further, the classification unit 12 selects a label corresponding to any of the start points of the overlapping vertices and sets it as a corresponding element of the second matrix. After that, the classification unit 12 unifies the labels of the elements corresponding to the vertices in the same concatenation set based on the concatenation information after the labels are set for all the elements of the second matrix.
  • FIG. 13, and FIG. 14 are diagrams for explaining an example of the operation of the modified example 2.
  • the generation unit 11 since the vertices 4 and 7 are selected as the starting points, the generation unit 11 generates the frontier matrix (F1').
  • FIG. 12 is an example in which the classification unit 12 generates the result (M1') of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F1') of FIG.
  • the vertices adjacent to the vertices 4 are the vertices 5 and 6
  • the vertices adjacent to the vertices 7 are the vertices 5, 6 and 8, so that the vertices 5 and 6 overlap. That is, vertices 4 to 7 are in the same concatenated set.
  • the classification unit 12 since "11" is added to the element corresponding to the vertices 5 and 6 of the product result (M1'), the classification unit 12 has the vertices 4, 5, 6 and 7 in the same concatenated set.
  • the classification unit 12 may store the connection information indicating that the vertices with the label “01” and the label “10” are in the same connection set in the storage unit.
  • the classification unit 12 assigns the label "01" set at the vertex 4 or the label "10” set at the vertex 7 to the elements corresponding to the overlapping vertices 5 and 6 of the product result (M1'). Set.
  • the product result (M1') in FIG. 12 is defined as the frontier matrix (F2 ′′).
  • the product result (M1 ′) does not have an element corresponding to the searched vertices.
  • the product result (M1') is used as a new frontier matrix (F2 ′′).
  • the classification unit 12 calculates the sum result (S1 ′′: second matrix) of the product result (M1 ′) of FIG. 12 and the frontier matrix (F1 ′) of FIG.
  • the elements corresponding to the already searched vertices 4, 5, 6, 7, and 8 are labeled.
  • the example of FIG. 13 is an example in which the classification unit 12 generates the result (M2 ′′) of the product of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F2 ′′) of FIG.
  • the product result (M2 ′′) has labels for the elements corresponding to the searched vertices 4, 7, 9, the elements corresponding to the searched vertices from the product result (M2 ′′).
  • a new frontier matrix (F3 ′′) is generated in which the elements corresponding to the labeled vertices 9 remain and “00” is assigned to the other vertices.
  • the classification unit 12 calculates the sum result (S2 ′′: second matrix) of the product result (M2 ′′) of FIG. 13 and the frontier matrix (F3 ′′) of FIG.
  • the result (S2 ′′) of the elements corresponding to the vertices 4 to 9 already searched are labeled.
  • the classification unit 12 unifies the labels corresponding to the vertices of the same concatenated set to the same label based on the concatenation information. For example, as shown in FIG. 13, the label "01" corresponding to the vertex 4 and the "10" corresponding to the vertex 7 are set to "11".
  • the levels of the same concatenated set can be set to the same label, so that the vertices can be classified.
  • FIG. 15 is a diagram for explaining an example of the operation of the graph search device.
  • FIG. 1 will be referred to as appropriate.
  • Modifications 1 and 2 the graph search method is implemented by operating the graph search device. Therefore, the description of the graph search method in the present embodiment, Modifications 1 and 2, will be replaced with the following description of the operation of the graph search device.
  • the acquisition unit 13 acquires data necessary for performing a graph search for the target graph (step A1). Specifically, in step A1, the acquisition unit 13 receives the data transmitted from the external device 20 and outputs it to the adjacency matrix generation unit 14.
  • the adjacency matrix generation unit 14 generates an adjacency matrix representing the adjacency relationship of the vertices for the target graph by using the data required for the graph search (step A2). Specifically, in step A2, the adjacency matrix generation unit 14 first acquires data necessary for graph search. Subsequently, in step A2, the adjacency matrix generation unit 14 generates an adjacency matrix corresponding to the target graph by using the plurality of vertices included in the target graph and the adjacency relations of the vertices. The adjacency matrix generation unit 14 generates, for example, the adjacency matrix (R) as shown in FIG. 2 described above.
  • the generation unit 11 selects a plurality of vertices based on the adjacency of the vertices included in the graph, and generates a frontier matrix in which different labels are set for each element corresponding to the selected vertices (step A3). Specifically, in step A3, the generation unit 11 first selects a plurality of vertices from the vertices included in the graph.
  • the user may arbitrarily select a plurality of vertices, or the generation unit 11 may select a plurality of vertices.
  • the generation unit 11 may select preset vertices or may select based on the number of vertices.
  • step A3 the generation unit 11 sets different labels for the elements corresponding to the selected vertices in the frontier matrix having the same number of rows as the number of vertices.
  • the generation unit 11 generates, for example, the frontier matrix (F1) as shown in FIG. 2 described above. Further, the generation unit 11 determines the bit width of the label based on the number of selected vertices.
  • the classification unit 12 refers to the result of the sum representing the vertices for which the graph has been searched (second matrix) from the result of the product of the adjacency matrix and the frontier matrix (first matrix), and sets the searched vertices.
  • a new frontier matrix is generated by excluding the corresponding elements (step A4).
  • the classification unit 12 calculates the sum of the product result and the sum result, generates a new sum result (second matrix), and classifies the vertices.
  • step A4 the classification unit 12 first acquires the adjacency matrix and the frontier matrix. Subsequently, in step A4, the classification unit 12 calculates the result of the product of the adjacency matrix and the frontier matrix.
  • step A4 the classification unit 12 refers to the sum result, and if the product result has a searched vertex, the classification unit 12 excludes the element corresponding to the searched vertex from the product result and a new frontier matrix. To generate.
  • the generation unit 11 generates new frontier matrices (F3) and (F4), for example, as described above with reference to FIGS. 4 and 5.
  • step A4 the classification unit 12 calculates the sum of the product result and the sum result, generates a new sum result, and classifies the vertices.
  • the generation unit 11 generates new sum results (S1), (S2), and (S3), for example, as described above with reference to FIGS. 3 to 6.
  • the output information generation unit 15 generates output information used to output one or more of the graph, the adjacency matrix, the frontier matrix, the product result, the sum result, and the like to the output device (step A5). After that, the output information generation unit 15 transmits the generated output information to the output device (step A6).
  • step A3 when the vertices 4 and 7 shown in FIG. 8 are selected as the starting points, the generation unit 11 generates the frontier matrix (F1').
  • step A4 the classification unit 12 generates a product result (M1') of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F1') of FIG.
  • the classification unit 12 sets the elements corresponding to the overlapping vertices 5 and 6 with a label representing the logical sum of the label "01" set at the vertex 4 and the label "10" set at the vertex 7. Add "11".
  • step A4 the classification unit 12 sets the product result (M1') of FIG. 9 as the frontier matrix (F2').
  • the product result (M1') since the product result (M1') does not have an element corresponding to the searched vertices, the product result (M1') is used as a new frontier matrix (F2').
  • step A4 the classification unit 12 calculates the result of the sum of the product result (M1') of FIG. 9 and the frontier matrix (F1') of FIG. 8 (S1': second matrix).
  • the sum result (S1') is a matrix for representing the searched vertices. Therefore, the sum result (S1') of FIG. 9 is labeled with the elements corresponding to the already searched vertices 4, 5, 6, 7, and 8.
  • step A4 the classification unit 12 generates a product result (M2') of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F2') of FIG.
  • M2' product result of the adjacency matrix
  • F2' frontier matrix
  • step A4 the classification unit 12 generates a frontier matrix (F3') using the product result (M2') of FIG. 10 and the sum result (S1').
  • the product result (M2') since the product result (M2') has labels for the elements corresponding to the searched vertices 4, 7, and 9, the elements corresponding to the searched vertices from the product result (M2'). Exclude.
  • a new frontier matrix (F3') is generated in which the elements corresponding to the labeled vertices 9 remain and "00" is assigned to the other vertices.
  • step A4 the classification unit 12 calculates the result of the sum of the product result (M2') of FIG. 10 and the frontier matrix (F3') of FIG. 2 (S2': second matrix).
  • the elements corresponding to the vertices 4 to 9 already searched are labeled.
  • step A3 when the vertices 4 and 7 shown in FIG. 8 are selected as the starting points, the generation unit 11 generates the frontier matrix (F1').
  • step 4 when the classification unit 12 detects overlapping vertices, it generates connection information indicating that the vertices that are the start points of the overlapping vertices are in the same connection set and stores them in the storage unit. Further, the classification unit 12 selects a label corresponding to any of the start points of the overlapping vertices and sets it as a corresponding element of the second matrix. After that, the classification unit 12 unifies the labels of the elements corresponding to the vertices in the same concatenation set based on the concatenation information after the labels are set for all the elements of the second matrix.
  • step A4 the classification unit 12 first generates a product result (M1') of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F1') of FIG.
  • the vertices adjacent to the vertices 4 are the vertices 5 and 6, and the vertices adjacent to the vertices 7 are the vertices 5, 6 and 8, so that the vertices 5 and 6 overlap. That is, vertices 4 to 7 are in the same concatenated set.
  • step A4 since "11" is added to the element corresponding to the vertices 5 and 6 of the product result (M1'), in step A4, the classification unit 12 has the same vertices 4, 5, 6 and 7.
  • the concatenation information indicating that it is in the concatenation set is stored in the storage unit.
  • the classification unit 12 may store the connection information indicating that the vertices labeled “01” and the label “10” are in the same connection set in the storage unit.
  • step A4 the classification unit 12 sets the label "01" set at the vertex 4 or the label set at the vertex 7 for the elements corresponding to the overlapping vertices 5 and 6 of the product result (M1'). Set "10".
  • step A4 the classification unit 12 sets the product result (M1 ′) of FIG. 12 as the frontier matrix (F2 ′′).
  • the product result (M1 ′) has already been searched. Since there is no element corresponding to the vertex, the product result (M1') is used as a new frontier matrix (F2 ′′).
  • step A4 the classification unit 12 calculates the result (S1 ′′: second matrix) of the sum of the product result (M1 ′) of FIG. 12 and the frontier matrix (F1 ′) of FIG.
  • the sum result (S1 ′′) of FIG. 12 is labeled with the elements corresponding to the already searched vertices 4, 5, 6, 7, 8.
  • step A4 the classification unit 12 generates a product result (M2 ′′) of the adjacency matrix (R) of FIG. 2 and the frontier matrix (F2 ′′) of FIG.
  • the product result (M2 ′′) has labels for the elements corresponding to the searched vertices 4, 7, 9, the elements corresponding to the searched vertices from the product result (M2 ′′).
  • a new frontier matrix (F3 ′′) is generated in which the elements corresponding to the labeled vertices 9 remain and “00” is assigned to the other vertices.
  • step A4 the classification unit 12 calculates the result of the sum of the product result (M2 ′′) of FIG. 13 and the frontier matrix (F3 ′′) of FIG. 2 (S2 ′′: second matrix).
  • the sum result (S2 ′′) of FIG. 14 is labeled with the elements corresponding to the already searched vertices 4 to 9.
  • step A4 when the vertices 4 to 9 of the sum result (S2 ′′) are labeled, the classification unit 12 labels the vertices of the same concatenated set based on the concatenation information.
  • the same label is used. For example, as shown in FIG. 13, the label "01" corresponding to the vertex 4 and the "10" corresponding to the vertex 7 are logically summed to "11".
  • the levels of the same concatenated set can be set to the same label, so that the vertices can be classified.
  • the program according to the embodiment of the present invention may be any program that causes a computer to execute steps A1 to A6 shown in FIG. By installing this program on a computer and executing it, the graph search device and the graph search method in the present embodiment can be realized.
  • the computer processor functions as an acquisition unit 13, an adjacency matrix generation unit 14, a generation unit 11, a classification unit 12, and an output information generation unit 15 to perform processing.
  • each computer may function as one of the acquisition unit 13, the adjacency matrix generation unit 14, the generation unit 11, the classification unit 12, and the output information generation unit 15, respectively.
  • FIG. 16 is a block diagram showing an example of a computer that realizes the graph search device according to the first and second modifications of the embodiment of the present invention.
  • the computer 110 includes a CPU 111, a main memory 112, a storage device 113, an input interface 114, a display controller 115, a data reader / writer 116, and a communication interface 117. Each of these parts is connected to each other via a bus 121 so as to be capable of data communication.
  • the computer 110 may include a GPU (Graphics Processing Unit) or an FPGA (Field-Programmable Gate Array) in addition to the CPU 111 or in place of the CPU 111.
  • the CPU 111 expands the programs (codes) of the present embodiment stored in the storage device 113 into the main memory 112 and executes them in a predetermined order to perform various operations.
  • the main memory 112 is typically a volatile storage device such as a DRAM (Dynamic Random Access Memory).
  • the program in the present embodiment is provided in a state of being stored in a computer-readable recording medium 120.
  • the program in this embodiment may be distributed on the Internet connected via the communication interface 117.
  • the recording medium 120 is a non-volatile recording medium.
  • the storage device 113 in addition to a hard disk drive, a semiconductor storage device such as a flash memory can be mentioned.
  • the input interface 114 mediates data transmission between the CPU 111 and an input device 118 such as a keyboard and mouse.
  • the display controller 115 is connected to the display device 119 and controls the display on the display device 119.
  • the data reader / writer 116 mediates data transmission between the CPU 111 and the recording medium 120, reads a program from the recording medium 120, and writes a processing result in the computer 110 to the recording medium 120.
  • the communication interface 117 mediates data transmission between the CPU 111 and another computer.
  • the recording medium 120 include a general-purpose semiconductor storage device such as CF (CompactFlash (registered trademark)) and SD (SecureDigital), a magnetic recording medium such as a flexible disk, or a CD-.
  • CF CompactFlash (registered trademark)
  • SD Secure Digital
  • magnetic recording medium such as a flexible disk
  • CD- CompactDiskReadOnlyMemory
  • optical recording media such as ROM (CompactDiskReadOnlyMemory).
  • the graph search device 10 in the present embodiment can also be realized by using hardware corresponding to each part instead of the computer in which the program is installed. Further, the graph search device 10 may be partially realized by a program and the rest may be realized by hardware.
  • a generator that selects multiple vertices based on the adjacency of vertices included in the graph and generates a frontier matrix with different labels for each element corresponding to the selected vertices.
  • a classification unit that classifies vertices using an adjacency matrix that represents the adjacency relationship of vertices included in the graph and the frontier matrix.
  • a graph search device characterized by having.
  • Appendix 2 The graph search device according to Appendix 1.
  • the classification unit From the first matrix, which is the product of the adjacency matrix and the frontier matrix, the second matrix for representing the graph-searched vertices is referred to, the elements corresponding to the searched vertices are excluded, and a new frontier is created.
  • Generate a matrix A graph search device characterized in that the sum of the first matrix and the second matrix is calculated, a new second matrix is generated, and the vertices are classified.
  • Appendix 3 The graph search device according to Appendix 1 or 2.
  • the label is a graph search device characterized in that the bit width is determined based on the number of vertices as a starting point.
  • Appendix 4 The graph search device according to any one of Appendix 1 to 3.
  • Appendix 7 The graph search method according to Appendix 5 or 6, wherein the graph search method is used.
  • the label is a graph search method characterized in that the bit width is determined based on the number of vertices that serve as starting points.
  • step (Appendix 9) The computer-readable recording medium according to Appendix 8, which is a computer-readable recording medium.
  • step (b) above From the first matrix, which is the product of the adjacency matrix and the frontier matrix, the second matrix for representing the graph-searched vertices is referred to, the elements corresponding to the searched vertices are excluded, and a new frontier is created.
  • Generate a matrix A computer-readable recording medium characterized in that the sum of the first matrix and the second matrix is calculated to generate a new second matrix to classify vertices.
  • Appendix 10 A computer-readable recording medium according to Appendix 8 or 9.
  • the label is a computer-readable recording medium characterized in that the bit width is determined based on the number of vertices as a starting point.
  • the time required for graph search can be shortened.
  • the present invention is useful in fields where graph search is required. For example, it can be used for SNS analysis, analysis of roads connecting points on an electronic map, and the like.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

グラフ探索装置１０は、グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、生成部１１と、グラフに含まれる頂点の隣接関係を表す隣接行列とフロンティア行列とを用いて頂点を分類する、分類部１２と、を有する。

Description

グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体
　本発明は、グラフ探索を実行するグラフ探索装置、グラフ探索方法に関し、更には、これらを実現するためのプログラムを記録しているコンピュータ読み取り可能な記録媒体に関する。
　グラフ探索は、ＳＮＳ（Social Networking Service）の分析（利用者間の関係をクラスタリングなど）、電子地図上の地点をつなぐ道路の分析（地点間の最短経路探索など）を実行する場合に重要な技術である。また、グラフ探索では、グラフの構造を、隣接行列を用いて表すことが知られている。
　関連する技術として特許文献１には、グラフの連結成分数を効率よく求めることができるパターン抽出装置が開示されている。特許文献１のパターン抽出装置によれば、パターンの接続関係を、頂点隣接行列を用いて表し、頂点隣接行列の対角化ブロック数をカウントすることにより、グラフの連結成分数を求めるものである。
特開２０００－３２２５１４号公報
　しかしながら、グラフ探索において、頂点の数が多くなると、行列の要素の数が増えるため隣接行列が大きくなる。そのため、グラフ探索にかかる時間が増えてしまう。そこで、グラフ探索に要する時間を短縮したいという要望がある。
　本発明の目的の一例は、グラフ探索に要する時間を短縮するグラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
　上記目的を達成するため、本発明の一側面におけるグラフ探索装置は、
　グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、生成手段と、
　前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、分類手段と、
　を有することを特徴とする。
　また、上記目的を達成するため、本発明の一側面におけるグラフ探索方法は、
（ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成し、
（ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する
　ことを特徴とする。
　さらに、上記目的を達成するため、本発明の一側面におけるプログラムを記録したコンピュータ読み取り可能な記録媒体は、
　コンピュータに、
（ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、ステップと、
（ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、ステップと、
　を実行させる命令を含むプログラムを記録していることを特徴とする。
　以上のように本発明によれば、グラフ探索に要する時間を短縮することができる。
図１は、グラフ探索装置の一例を説明するための図である。 図２は、隣接行列とフロンティア行列の一例を説明するための図である。 図３は、隣接行列とフロンティア行列の一例を説明するための図である。 図４は、隣接行列とフロンティア行列の一例を説明するための図である。 図５は、隣接行列とフロンティア行列の一例を説明するための図である。 図６は、隣接行列とフロンティア行列の一例を説明するための図である。 図７は、グラフ探索装置を有するシステムの一例を説明するための図である。 図８は、頂点の選択の一例について説明するための図である。 図９は、変形例１の動作について説明するための図である。 図１０は、変形例１の動作について説明するための図である。 図１１は、変形例１の動作について説明するための図である。 図１２は、変形例２の動作について説明するための図である。 図１３は、変形例２の動作について説明するための図である。 図１４は、変形例２の動作について説明するための図である。 図１５は、グラフ探索装置の動作の一例を説明するための図である。 図１６は、グラフ探索装置を実現するコンピュータの一例を示す図である。
（実施形態）
　以下、本発明の実施形態について、図１から図１６を参照しながら説明する。
［装置構成］
　最初に、図１を用いて、本実施形態におけるグラフ探索装置１０の構成について説明する。図１は、グラフ探索装置の一例を説明するための図である。
　図１に示すグラフ探索装置１０は、グラフ探索に要する時間を短縮する装置である。また、図１に示すように、グラフ探索装置１０は、生成部１１と、分類部１２とを有する。
　このうち、生成部１１は、グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する。分類部１２は、グラフに含まれる頂点の隣接関係を表す隣接行列とフロンティア行列とを用いて、頂点を分類する。
　図２、図３、図４、図５、図６は、隣接行列とフロンティア行列の一例を説明するための図である。図２に示すグラフは、頂点０から頂点９を有する。隣接行列は、対象とする頂点に隣接する頂点を表すための行列である。フロンティア行列は、グラフが有する頂点を、連結集合ごとに分類するために用いる行列である。連結集合とは、到達可能な頂点を分類した集合である。
　図２の隣接行列（Ｒ）は、図２のグラフに対応する隣接行列である。頂点０の隣接関係について説明をする。グラフの頂点０に隣接する頂点は頂点１、２であるので、図２の隣接行列においては、頂点０に対応する行及び列の頂点１、２に対応する要素に「１」を設定する。頂点１、２以外の頂点については、頂点０に隣接していないので、頂点１、２以外の頂点に対応する要素に「０」を設定する。なお、頂点０以外のグラフに存在する頂点それぞれについても、頂点０と同じようにして隣接関係を隣接行列に表す。
　図２のフロンティア行列（Ｆ１）は、分類開始時に用いるフロンティア行列である。図２の例では、分類開始時の始点となる頂点としてグラフの頂点０、５が選択された場合を表している。始点となる頂点０に対応するフロンティア行列（Ｆ１）の要素には、ラベル「０１」が割り当てられる。また、始点となる頂点５に対応するフロンティア行列（Ｆ１）の要素には、ラベル「１０」が割り当てられる。なお、始点でない頂点０、５以外の頂点には、初期値として「００」が割り当てられる。
　ラベルは、始点となる頂点の数に基づいてビット幅が決まる。図２のフロンティア行列では、始点となる頂点が二つなので、ビット幅が２ビットとなる。始点となる頂点が三つの場合には、ビット幅は３ビットとなる。ビット幅が３ビットの場合には、例えば、「１００」などとする。
　図３の行列（第一の行列）は、図２の隣接行列（Ｒ）とフロンティア行列（Ｆ１）との積の結果（Ｍ１）である。図３の例では、始点である頂点０に隣接する頂点が頂点１、２なので、積の結果（Ｍ１）には、頂点１、２に対応する要素に、頂点０と連結していることを表すラベル「０１」が付される。また、始点である頂点５に隣接する頂点が頂点４、７なので、積の結果（Ｍ１）には、頂点４、７に対応する要素に、頂点５と連結していることを表すラベル「１０」が付される。
　なお、行列の積を算出する場合、要素の積を算出するには論理積を用い、要素の和を算出するには論理和を用いるものとする。
　次に、図３の積の結果（Ｍ１）をフロンティア行列（Ｆ２）とする。図３の例では、積の結果（Ｍ１）には探索済みの頂点に対応する要素がないので、積の結果（Ｍ１）を新たなフロンティア行列（Ｆ２）として用いる。ただし、すでに積の結果（Ｍ１）に探索済みの頂点（分類済みの頂点）に対応する要素がある場合、積の結果（Ｍ１）から探索済みの頂点に対応する要素を除外する。
　次に、図３の積の結果（Ｍ１）と図２のフロンティア行列（Ｆ１）との和の結果（Ｓ１：第二の行列）を算出する。和の結果（Ｓ１）は、探索済みの頂点を表すための行列である。したがって、図３の和の結果（Ｓ１）において、すでに探索した頂点０、１、２、４、５、７に対応する要素には、ラベルが付されている。
　なお、行列の和を算出する場合、要素の和を算出するには論理和を用いるものとする。
　図４の行列（第一の行列）は、図２の隣接行列（Ｒ）と図３のフロンティア行列（Ｆ２）との積の結果（Ｍ２）である。図４の例では、始点が頂点０に隣接する頂点１、２になったので、積の結果（Ｍ２）には、頂点０、３に対応する要素に、頂点０と連結していることを表すラベル「０１」が付される。また、始点が頂点５に隣接する頂点４、７になったので、積の結果（Ｍ２）には、頂点５、６、８に対応する要素に、頂点５と連結していることを表すラベル「１０」が付される。
　次に、図４の積の結果（Ｍ２）と和の結果（Ｓ１）とを用いてフロンティア行列（Ｆ３）を生成する。図４の例では、積の結果（Ｍ２）には探索済みの頂点０、１、２、４、５、７に対応する要素にラベルがあるので、積の結果（Ｍ２）から探索済みの頂点に対応する要素を除外する。そうすると、図４に示すように、ラベルが付された頂点３、６、８に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ３）が生成される。
　次に、図５に示す和の結果（Ｓ２：第二の行列）を算出する。和の結果（Ｓ２）は、図４の積の結果（Ｍ２）と図３のフロンティア行列（Ｆ２）との和の結果である。和の結果（Ｓ２）は、すでに探索した頂点を表す行列であるので、頂点０、１、２、３、４、５、６、７、８に対応する要素にラベルが付される。
　図５の行列（第一の行列）は、図２の隣接行列（Ｒ）と図４のフロンティア行列（Ｆ３）との積の結果（Ｍ３）である。図５の例では、始点が頂点３になったので、積の結果（Ｍ３）の頂点１に対応する要素に、頂点０と連結していることを表すラベル「０１」が付される。また、図５の例では、始点が頂点６、８になったので、積の結果（Ｍ３）の頂点４、７、９に対応する要素に、頂点５と連結していることを表すラベル「１０」が付される。
　次に、図５の積の結果（Ｍ３）と和の結果（Ｓ２）とを用いてフロンティア行列（Ｆ４）を生成する。図５の例では、積の結果（Ｍ３）には探索済みの頂点０から８に対応する要素にラベルがあるので、積の結果（Ｍ３）から探索済みの頂点に対応する要素を除外する。そうすると、図５に示すように、ラベルが付された頂点９に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ４）が生成される。
　次に、図６に示す和の結果（Ｓ３：第二の行列）を算出する。和の結果（Ｓ３）は、図５の積の結果（Ｍ３）と図４のフロンティア行列（Ｆ３）との和の結果である。和の結果（Ｓ３）には、頂点０から３に対応する要素にラベル「０１」が付され、頂点４から９に対応する要素にレベル「１０」が付される。すなわち、グラフに示されている頂点の連結集合と同じように、頂点に対応する要素がラベルにより分類される。
　なお、和の結果（第二の行列）すべての頂点に対応する要素にラベルが付された場合、頂点を分類する処理を終了する。
　このように、本実施形態においては、隣接行列とフロンティア行列とを用いて、複数の頂点を用いて分類するので、グラフ探索に要する時間を短縮することができる。
　また、従来は、プロセッサなどを用いてグラフ探索をする場合、一つの頂点を選択し、一つの選択した頂点に対してグラフ探索が終了してから、次の頂点を一つ選択して、順次グラフ探索をしていた。しかし、本実施形態においては、複数の頂点を選択して、並列にグラフ探索を実行するので、従来よりも、グラフ探索において必要とするステップ数を削減することができる。
［システム構成］
　続いて、図７を用いて、本実施形態におけるグラフ探索装置１０の構成をより具体的に説明する。図７は、グラフ探索装置を有するシステムの一例を説明するための図である。
　図７に示すように、本実施形態におけるシステムは、グラフ探索装置１０、外部装置２０、出力装置３０を有する。グラフ探索装置１０は、生成部１１、分類部１２に加えて、取得部１３と、隣接行列生成部１４と、出力情報生成部１５とを有する。
　システムについて説明をする。
　グラフ探索装置１０は、例えば、ベクトルプロセッサ、又はＣＰＵ（Central Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）、又はそれらを搭載したサーバコンピュータ、パーソナルコンピュータ、モバイル端末などの情報処理装置である。
　外部装置２０は、グラフ探索に必要なデータを有する装置である。具体的には、外部装置２０は、ＳＮＳの分析、電子地図上の地点をつなぐ道路の分析などに用いるデータを記憶したデータベースなどの記憶装置、サーバコンピュータ、パーソナルコンピュータ、モバイル端末などが考えられる。なお、外部装置２０は、グラフ探索装置１０と有線又は無線により通信をして、データをグラフ探索装置１０に送信する。
　出力装置３０は、出力情報生成部１５により、出力可能な形式に変換された、出力情報を取得し、その出力情報に基づいて、生成した画像及び音声などを出力する。出力装置３０は、例えば、液晶、有機ＥＬ（Electro Luminescence）、ＣＲＴ（Cathode Ray Tube）を用いた画像表示装置などである。さらに、画像表示装置は、スピーカなどの音声出力装置などを備えていてもよい。なお、出力装置３０は、プリンタなどの印刷装置でもよい。
　グラフ探索装置について説明をする。
　取得部１３は、対象となるグラフに対して、グラフ探索をするために必要なデータを取得する。具体的には、取得部１３は、外部装置２０から送信されたデータを受信して、隣接行列生成部１４へと出力する。取得部１３は、例えば、外部装置２０と有線又は無線により通信をして、データを受信する。
　隣接行列生成部１４は、対象となるグラフに対して、グラフ探索に必要なデータを用いて、頂点の隣接関係を表す隣接行列を生成する。具体的には、隣接行列生成部１４は、まず、グラフ探索に必要なデータを取得する。続いて、隣接行列生成部１４は、対象とするグラフに含まれる複数の頂点と、頂点それぞれの隣接関係とを用いて、対象とするグラフに対応する隣接行列を生成する。隣接行列生成部１４は、例えば、上述した図２に示すような隣接行列（Ｒ）を生成する。
　生成部１１は、グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する。具体的には、まず、生成部１１は、グラフに含まれる頂点から複数の頂点を選択する。
　頂点の選択は、例えば、利用者が任意に複数の頂点を選択してもよいし、生成部１１が複数の頂点を選択してもよい。なお、生成部１１が複数の頂点を選択する場合、生成部１１は、あらかじめ設定された頂点を選択してもよいし、頂点の数に基づいて選択してもよい。
　続いて、生成部１１は、頂点の数と同じ行数のフロンティア行列の、選択された頂点に対応する要素に異なるラベルを設定する。生成部１１は、例えば、上述した図２に示すようなフロンティア行列（Ｆ１）を生成する。また、生成部１１は、選択された頂点の数に基づいて、ラベルのビット幅を決める。
　分類部１２は、隣接行列とフロンティア行列との積の結果（第一の行列）から、グラフ探索済みの頂点を表す和の結果（第二の行列）を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成する。その後、分類部１２は、積の結果と和の結果との和を算出し、新たな和の結果（第二の行列）を生成して頂点を分類する。
　具体的には、まず、分類部１２は、隣接行列とフロンティア行列とを取得する。続いて、分類部１２は、隣接行列とフロンティア行列との積の結果を算出する。続いて、分類部１２は、和の結果を参照し、積の結果に探索済みの頂点がある場合、積の結果から探索済み頂点に対応する要素を除外して新たなフロンティア行列を生成する。生成部１１は、例えば、図４、図５を用いて上述したようにして、新たなフロンティア行列（Ｆ３）（Ｆ４）を生成する。
　続いて、分類部１２は、積の結果と、和の結果との和を算出し、新たな和の結果を生成して頂点を分類する。生成部１１は、例えば、図３から図６を用いて上述したようにして、新たな和の結果（Ｓ１）（Ｓ２）（Ｓ３）を生成する。
　出力情報生成部１５は、グラフ、隣接行列、フロンティア行列、積の結果、和の結果などを、一つ以上を出力装置に出力するために用いる出力情報を生成する。その後、出力情報生成部１５は、生成した出力情報を出力装置へ送信する。
［変形例１］
　生成部１１により選択された複数の頂点が同じ連結集合にある場合、選択された複数の頂点それぞれに異なるラベルが設定されるので、分類部１２は、同じ連結集合にある複数の頂点それぞれに対して異なるラベルを付すことになる。そうすると、実際のグラフと異なる分類がされてしまう。
　変形例１では、同じ連結集合にある複数の頂点それぞれに対して異なるラベルが設定された場合でも、同じ連結集合にある頂点のラベルは同じラベルに統一し、実際のグラフと同じ分類ができるようにする。
　変形例１について図８から図１１を用いて説明する。図８は、頂点の選択の一例について説明するための図である。図９、図１０、図１１は、変形例１の動作について説明するための図である。
　図８の例は、生成部１１が、始点として頂点４、７が選択された場合に、フロンティア行列（Ｆ１´）を生成した例である。
　図９の例は、分類部１２が、図２の隣接行列（Ｒ）と図８のフロンティア行列（Ｆ１´）との積の結果（Ｍ１´）を生成した例である。このとき、頂点４に隣接する頂点が頂点５、６で、頂点７に隣接する頂点が頂点５、６、８になるので、頂点５、６は重複する。そのような場合、分類部１２は、重複する頂点５、６に対応する要素に、頂点４に設定されたラベル「０１」と頂点７に設定されたラベル「１０」との論理和を表すラベル「１１」を付す。
　次に、図９の積の結果（Ｍ１´）をフロンティア行列（Ｆ２´）とする。図９の例では、積の結果（Ｍ１´）に、探索済みの頂点に対応する要素がないので、積の結果（Ｍ１´）を新たなフロンティア行列（Ｆ２´）として用いる。
　次に、図９の積の結果（Ｍ１´）と図８のフロンティア行列（Ｆ１´）との和の結果（Ｓ１´：第二の行列）を算出する。和の結果（Ｓ１´）は、探索済みの頂点を表すための行列である。したがって、図９の和の結果（Ｓ１´）には、すでに探索した頂点４、５、６、７、８に対応する要素にラベルが付される。
　図１０の例は、分類部１２が、図２の隣接行列（Ｒ）と図９のフロンティア行列（Ｆ２´）との積の結果（Ｍ２´）を生成した例である。このとき、頂点５に隣接する頂点が頂点４、７で、頂点６に隣接する頂点が頂点４、７になるので、頂点４、７については隣接する頂点が重複する。そのような場合、分類部１２は、重複する頂点４、７に対応する要素にラベル「１１」を付す。
　次に、分類部１２は、図１０の積の結果（Ｍ２´）と和の結果（Ｓ１´）とを用いてフロンティア行列（Ｆ３´）を生成する。図１０の例では、積の結果（Ｍ２´）には探索済みの頂点４、７、９に対応する要素にラベルがあるので、積の結果（Ｍ２´）から探索済みの頂点に対応する要素を除外する。そうすると、図１０に示すように、ラベルが付された頂点９に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ３´）が生成される。
　次に、分類部１２は、図１０の積の結果（Ｍ２´）と図２のフロンティア行列（Ｆ３´）との和の結果（Ｓ２´：第二の行列）を算出する。図１１の和の結果（Ｓ２´）には、すでに探索した頂点４から９に対応する要素にラベルが付される。このようにして、頂点４から９に対応する要素にすべてラベル「１１」が付されるまで続ける。
　変形例１によれば、同じ連結集合に複数の頂点が選択されても、同じ連結集合のレベルを同じラベルにできるので、頂点を分類することができる。
［変形例２］
　生成部１１により選択された複数の頂点が同じ連結集合にある場合、選択された複数の頂点それぞれに異なるラベルが設定されるので、分類部１２は、同じ連結集合にある複数の頂点それぞれに対して異なるラベルを付すことになる。そうすると、実際のグラフと異なる分類がされてしまう。
　変形例２では、同じ連結集合にある複数の頂点それぞれに対して異なるラベルが設定された場合でも、同じ連結集合にある頂点のラベルは同じラベルに統一し、実際のグラフと同じ分類ができるようにする。
　変形例２においては、分類部１２は、重複する頂点を検出した場合、重複した頂点の始点となる頂点が同じ連結集合にあることを表す連結情報を生成して記憶部に記憶する。また、分類部１２は、重複した頂点の始点のいずれかに対応するラベルを選択して、第二の行列の対応する要素に設定する。その後、分類部１２は、第二の行列のすべての要素にラベルが設定された後、連結情報に基づいて、同じ連結集合にある頂点に対応する要素のラベルを統一する。
　変形例２について図８、図１２から図１４を用いて説明する。図１２、図１３、図１４は、変形例２の動作の一例について説明するための図である。
　図８の例では、始点として頂点４、７が選択されたので、生成部１１は、フロンティア行列（Ｆ１´）を生成する。
　図１２の例は、分類部１２が、図２の隣接行列（Ｒ）と図８のフロンティア行列（Ｆ１´）との積の結果（Ｍ１´）を生成した例である。図１２の例では、頂点４に隣接する頂点が頂点５、６となり、頂点７に隣接する頂点が頂点５、６、８になるので、頂点５、６は重複している。すなわち、頂点４から７は同じ連結集合にある。
　そのような場合、積の結果（Ｍ１´）の頂点５、６に対応する要素に「１１」が付されるので、分類部１２は、頂点４、５、６、７が同じ連結集合にあることを表す連結情報を記憶部に記憶する。又は、分類部１２は、ラベル「０１」とラベル「１０」が付された頂点が同じ連結集合にあることを表す連結情報を記憶部に記憶してもよい。
　なお、分類部１２は、積の結果（Ｍ１´）の重複する頂点５、６に対応する要素には、頂点４に設定したラベル「０１」、又は、頂点７に設定したラベル「１０」を設定する。
　次に、図１２の積の結果（Ｍ１´）をフロンティア行列（Ｆ２″）とする。図１２の例では、積の結果（Ｍ１´）には探索済みの頂点に対応する要素がないので、積の結果（Ｍ１´）を新たなフロンティア行列（Ｆ２″）として用いる。
　次に、分類部１２は、図１２の積の結果（Ｍ１´）と図８のフロンティア行列（Ｆ１´）との和の結果（Ｓ１″：第二の行列）を算出する。図１２の和の結果（Ｓ１″）は、すでに探索した頂点４、５、６、７、８に対応する要素にラベルが付される。
　図１３の例は、分類部１２が、図２の隣接行列（Ｒ）と図１２のフロンティア行列（Ｆ２″）との積の結果（Ｍ２″）を生成した例である。図１３の例では、積の結果（Ｍ２″）には探索済みの頂点４、７、９に対応する要素にラベルがあるので、積の結果（Ｍ２″）から探索済みの頂点に対応する要素を除外する。そうすると、図１３に示すように、ラベルが付された頂点９に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ３″）が生成される。
　次に、分類部１２は、図１３の積の結果（Ｍ２″）と図２のフロンティア行列（Ｆ３″）との和の結果（Ｓ２″：第二の行列）を算出する。図１４の和の結果（Ｓ２″）には、すでに探索した頂点４から９に対応する要素にラベルが付される。
　次に、分類部１２は、和の結果（Ｓ２″）の頂点４から９に対してラベルが付されると、連結情報に基づいて、同じ連結集合の頂点に対応するラベルを同じラベルに統一する。例えば、図１３に示すように、頂点４に対応するラベル「０１」と頂点７に対応する「１０」との論理和である「１１」にする。
　変形例２によれば、同じ連結集合に複数の頂点が選択されても、同じ連結集合のレベルを同じラベルにできるので、頂点を分類することができる。
［装置動作］
　次に、本発明の実施形態、変形例１、２におけるグラフ探索装置の動作について図１５を用いて説明する。図１５は、グラフ探索装置の動作の一例を説明するための図である。以下の説明においては、適宜図１を参照する。また、本実施形態、変形例１、２では、グラフ探索装置を動作させることによって、グラフ探索方法が実施される。よって、本実施形態、変形例１、２におけるグラフ探索方法の説明は、以下のグラフ探索装置の動作説明に代える。
　図１５に示すように、最初に、取得部１３は、対象となるグラフに対して、グラフ探索をするために必要なデータを取得する（ステップＡ１）。具体的には、ステップＡ１において、取得部１３は、外部装置２０から送信されたデータを受信して、隣接行列生成部１４へと出力する。
　次に、隣接行列生成部１４は、対象となるグラフに対して、グラフ探索に必要なデータを用いて、頂点の隣接関係を表す隣接行列を生成する（ステップＡ２）。具体的には、ステップＡ２において、隣接行列生成部１４は、まず、グラフ探索に必要なデータを取得する。続いて、ステップＡ２において、隣接行列生成部１４は、対象とするグラフに含まれる複数の頂点と、頂点それぞれの隣接関係とを用いて、対象とするグラフに対応する隣接行列を生成する。隣接行列生成部１４は、例えば、上述した図２に示すような隣接行列（Ｒ）を生成する。
　次に、生成部１１は、グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する（ステップＡ３）。具体的には、ステップＡ３において、生成部１１は、まず、グラフに含まれる頂点から複数の頂点を選択する。
　頂点の選択は、例えば、利用者が任意に複数の頂点を選択してもよいし、生成部１１が複数の頂点を選択してもよい。なお、生成部１１が複数の頂点を選択する場合、生成部１１は、あらかじめ設定された頂点を選択してもよいし、頂点の数に基づいて選択してもよい。
　続いて、ステップＡ３において、生成部１１は、頂点の数と同じ行数のフロンティア行列の、選択された頂点に対応する要素に異なるラベルを設定する。生成部１１は、例えば、上述した図２に示すようなフロンティア行列（Ｆ１）を生成する。また、生成部１１は、選択された頂点の数に基づいて、ラベルのビット幅を決める。
　次に、分類部１２は、隣接行列とフロンティア行列との積の結果（第一の行列）から、グラフ探索済みの頂点を表す和の結果（第二の行列）を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成する（ステップＡ４）。その後、分類部１２は、積の結果と和の結果との和を算出し、新たな和の結果（第二の行列）を生成して頂点を分類する。
　具体的には、ステップＡ４において、分類部１２は、まず、隣接行列とフロンティア行列とを取得する。続いて、ステップＡ４において、分類部１２は、隣接行列とフロンティア行列との積の結果を算出する。
　続いて、ステップＡ４において、分類部１２は、和の結果を参照し、積の結果に探索済みの頂点がある場合、積の結果から探索済み頂点に対応する要素を除外して新たなフロンティア行列を生成する。生成部１１は、例えば、図４、図５を用いて上述したようにして、新たなフロンティア行列（Ｆ３）（Ｆ４）を生成する。
　続いて、ステップＡ４において、分類部１２は、積の結果と、和の結果との和を算出し、新たな和の結果を生成して頂点を分類する。生成部１１は、例えば、図３から図６を用いて上述したようにして、新たな和の結果（Ｓ１）（Ｓ２）（Ｓ３）を生成する。
　次に、出力情報生成部１５は、グラフ、隣接行列、フロンティア行列、積の結果、和の結果などを、一つ以上を出力装置に出力するために用いる出力情報を生成する（ステップＡ５）。その後、出力情報生成部１５は、生成した出力情報を出力装置へ送信する（ステップＡ６）。
［変形例１］
　図８から図１１を用いて、変形例１の動作について説明する。
　ステップＡ３において、始点として図８に示す頂点４、７が選択された場合、生成部１１は、フロンティア行列（Ｆ１´）を生成する。
　次に、ステップＡ４において、分類部１２は、図２の隣接行列（Ｒ）と図８のフロンティア行列（Ｆ１´）との積の結果（Ｍ１´）を生成する。このとき、頂点４に隣接する頂点が頂点５、６で、頂点７に隣接する頂点が頂点５、６、８になるので、頂点５、６は重複する。そのような場合、分類部１２は、重複する頂点５、６に対応する要素に、頂点４に設定されたラベル「０１」と頂点７に設定されたラベル「１０」との論理和を表すラベル「１１」を付す。
　続いて、ステップＡ４において、分類部１２は、図９の積の結果（Ｍ１´）をフロンティア行列（Ｆ２´）とする。図９の例では、積の結果（Ｍ１´）に、探索済みの頂点に対応する要素がないので、積の結果（Ｍ１´）を新たなフロンティア行列（Ｆ２´）として用いる。
　続いて、ステップＡ４において、分類部１２は、図９の積の結果（Ｍ１´）と図８のフロンティア行列（Ｆ１´）との和の結果（Ｓ１´：第二の行列）を算出する。和の結果（Ｓ１´）は、探索済みの頂点を表すための行列である。したがって、図９の和の結果（Ｓ１´）には、すでに探索した頂点４、５、６、７、８に対応する要素にラベルが付される。
　続いて、ステップＡ４において、分類部１２は、図２の隣接行列（Ｒ）と図９のフロンティア行列（Ｆ２´）との積の結果（Ｍ２´）を生成する。このとき、頂点５に隣接する頂点が頂点４、７で、頂点６に隣接する頂点が頂点４、７になるので、頂点４、７については隣接する頂点が重複する。そのような場合、分類部１２は、重複する頂点４、７に対応する要素にラベル「１１」を付す。
　続いて、ステップＡ４において、分類部１２は、図１０の積の結果（Ｍ２´）と和の結果（Ｓ１´）とを用いてフロンティア行列（Ｆ３´）を生成する。図１０の例では、積の結果（Ｍ２´）には探索済みの頂点４、７、９に対応する要素にラベルがあるので、積の結果（Ｍ２´）から探索済みの頂点に対応する要素を除外する。そうすると、図１０に示すように、ラベルが付された頂点９に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ３´）が生成される。
　続いて、ステップＡ４において、分類部１２は、図１０の積の結果（Ｍ２´）と図２のフロンティア行列（Ｆ３´）との和の結果（Ｓ２´：第二の行列）を算出する。図１１の和の結果（Ｓ２´）には、すでに探索した頂点４から９に対応する要素にラベルが付される。
［変形例２］
　図８、図１２から図１４を用いて、変形例２の動作について説明する。
　ステップＡ３において、始点として図８に示す頂点４、７が選択された場合、生成部１１は、フロンティア行列（Ｆ１´）を生成する。
　ステップ４において、分類部１２は、重複する頂点を検出した場合、重複した頂点の始点となる頂点が同じ連結集合にあることを表す連結情報を生成して記憶部に記憶する。また、分類部１２は、重複した頂点の始点のいずれかに対応するラベルを選択して、第二の行列の対応する要素に設定する。その後、分類部１２は、第二の行列のすべての要素にラベルが設定された後、連結情報に基づいて、同じ連結集合にある頂点に対応する要素のラベルを統一する。
　具体的には、ステップＡ４において、分類部１２は、まず、図２の隣接行列（Ｒ）と図８のフロンティア行列（Ｆ１´）との積の結果（Ｍ１´）を生成する。図１２の例では、頂点４に隣接する頂点が頂点５、６となり、頂点７に隣接する頂点が頂点５、６、８になるので、頂点５、６は重複している。すなわち、頂点４から７は同じ連結集合にある。
　そのような場合、積の結果（Ｍ１´）の頂点５、６に対応する要素に「１１」が付されるので、ステップＡ４において、分類部１２は、頂点４、５、６、７が同じ連結集合にあることを表す連結情報を記憶部に記憶する。又は、ステップＡ４において、分類部１２は、ラベル「０１」とラベル「１０」が付された頂点が同じ連結集合にあることを表す連結情報を記憶部に記憶してもよい。
　なお、ステップＡ４において、分類部１２は、積の結果（Ｍ１´）の重複する頂点５、６に対応する要素には、頂点４に設定したラベル「０１」、又は、頂点７に設定したラベル「１０」を設定する。
　続いて、ステップＡ４において、分類部１２は、図１２の積の結果（Ｍ１´）をフロンティア行列（Ｆ２″）とする。図１２の例では、積の結果（Ｍ１´）には探索済みの頂点に対応する要素がないので、積の結果（Ｍ１´）を新たなフロンティア行列（Ｆ２″）として用いる。
　続いて、ステップＡ４において、分類部１２は、図１２の積の結果（Ｍ１´）と図８のフロンティア行列（Ｆ１´）との和の結果（Ｓ１″：第二の行列）を算出する。図１２の和の結果（Ｓ１″）は、すでに探索した頂点４、５、６、７、８に対応する要素にラベルが付される。
　続いて、ステップＡ４において、分類部１２は、図２の隣接行列（Ｒ）と図１２のフロンティア行列（Ｆ２″）との積の結果（Ｍ２″）を生成する。図１３の例では、積の結果（Ｍ２″）には探索済みの頂点４、７、９に対応する要素にラベルがあるので、積の結果（Ｍ２″）から探索済みの頂点に対応する要素を除外する。そうすると、図１３に示すように、ラベルが付された頂点９に対応する要素が残り、それ以外の頂点に「００」が割り当てられた、新たなフロンティア行列（Ｆ３″）が生成される。
　続いて、ステップＡ４において、分類部１２は、図１３の積の結果（Ｍ２″）と図２のフロンティア行列（Ｆ３″）との和の結果（Ｓ２″：第二の行列）を算出する。図１４の和の結果（Ｓ２″）には、すでに探索した頂点４から９に対応する要素にラベルが付される。
　続いて、ステップＡ４において、分類部１２は、和の結果（Ｓ２″）の頂点４から９に対してラベルが付されると、連結情報に基づいて、同じ連結集合の頂点に対応するラベルを同じラベルに統一する。例えば、図１３に示すように、頂点４に対応するラベル「０１」と頂点７に対応する「１０」との論理和である「１１」にする。
［本実施形態の効果］
　以上のように本実施形態によれば、隣接行列とフロンティア行列とを用いて、複数の頂点を用いて分類するので、グラフ探索に要する時間を短縮することができる。
　また、従来は、プロセッサなどを用いてグラフ探索をする場合、一つの頂点を選択し、一つの選択した頂点に対してグラフ探索が終了してから、次の頂点を一つ選択して、順次グラフ探索をしていた。しかし、本実施形態においては、複数の頂点を選択して、並列にグラフ探索を実行するので、従来よりも、グラフ探索において必要とするステップ数を削減することができる。
　変形例１、２によれば、同じ連結集合に複数の頂点が選択されても、同じ連結集合のレベルを同じラベルにできるので、頂点を分類することができる。
［プログラム］
　本発明の実施形態におけるプログラムは、コンピュータに、図１５に示すステップＡ１からＡ６を実行させるプログラムであればよい。このプログラムをコンピュータにインストールし、実行することによって、本実施形態におけるグラフ探索装置とグラフ探索方法とを実現することができる。この場合、コンピュータのプロセッサは、取得部１３、隣接行列生成部１４、生成部１１、分類部１２、出力情報生成部１５として機能し、処理を行なう。
　また、本実施形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されてもよい。この場合は、例えば、各コンピュータが、それぞれ、取得部１３、隣接行列生成部１４、生成部１１、分類部１２、出力情報生成部１５のいずれかとして機能してもよい。
［物理構成］
　ここで、実施形態、変形例１、２におけるプログラムを実行することによって、グラフ探索装置を実現するコンピュータについて図１６を用いて説明する。図１６は、本発明の実施形態、変形例１、２におけるグラフ探索装置を実現するコンピュータの一例を示すブロック図である。
　図１６に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていてもよい。
　ＣＰＵ１１１は、記憶装置１１３に格納された、本実施形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）などの揮発性の記憶装置である。また、本実施形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであってもよい。なお、記録媒体１２０は、不揮発性記録媒体である。
　また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリなどの半導体記憶装置があげられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
　データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
　また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）などの汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ－ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体があげられる。
　なお、本実施形態におけるグラフ探索装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。さらに、グラフ探索装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
［付記］
　以上の実施形態に関し、更に以下の付記を開示する。上述した実施形態の一部又は全部は、以下に記載する（付記１）から（付記１０）により表現することができるが、以下の記載に限定されるものではない。
（付記１）
　グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、生成部と、
　前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、分類部と、
　を有することを特徴とするグラフ探索装置。
（付記２）
　付記１に記載のグラフ探索装置であって、
　前記分類部は、
　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
　ことを特徴とするグラフ探索装置。
（付記３）
　付記１又は２に記載のグラフ探索装置であって、
　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
　ことを特徴とするグラフ探索装置。
（付記４）
　付記１から３のいずれか一つに記載のグラフ探索装置であって、
　前記生成部と前記分類部とを、ベクトルプロセッサを用いて動作させる
　ことを特徴とするグラフ探索装置。
（付記５）
（ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、ステップと、
（ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、ステップと
　を有することを特徴とするグラフ探索方法。
（付記６）
　付記５に記載のグラフ探索方法であって、
　前記（ｂ）のステップにおいて、
　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
　ことを特徴とするグラフ探索方法。
（付記７）
　付記５又は６に記載のグラフ探索方法であって、
　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
　ことを特徴とするグラフ探索方法。
（付記８）
　コンピュータに、
（ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、ステップと、
（ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、ステップと、
　を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
（付記９）
　付記８に記載のコンピュータ読み取り可能な記録媒体であって、
　前記（ｂ）のステップにおいて、
　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
　ことを特徴とするコンピュータ読み取り可能な記録媒体。
（付記１０）
　付記８又は９に記載のコンピュータ読み取り可能な記録媒体であって、
　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
　ことを特徴とするコンピュータ読み取り可能な記録媒体。
　以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
　以上のように本発明によれば、グラフ探索に要する時間を短縮することができる。本発明は、グラフ探索が必要な分野において有用である。例えば、ＳＮＳの分析、電子地図上の地点をつなぐ道路の分析などに用いることができる。
　１０　グラフ探索装置
　１１　生成部
　１２　分類部
　１３　取得部
　１４　隣接行列生成部
　１５　出力情報生成部
　２０　外部装置
　３０　出力装置
１１０　コンピュータ
１１１　ＣＰＵ
１１２　メインメモリ
１１３　記憶装置
１１４　入力インターフェイス
１１５　表示コントローラ
１１６　データリーダ／ライタ
１１７　通信インターフェイス
１１８　入力機器
１１９　ディスプレイ装置
１２０　記録媒体
１２１　バス

Claims (10)

  1. 　グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、生成手段と、
    　前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、分類手段と、
    　を有することを特徴とするグラフ探索装置。
  2. 　請求項１に記載のグラフ探索装置であって、
    　前記分類手段は、
    　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
    　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
    　ことを特徴とするグラフ探索装置。
  3. 　請求項１又は２に記載のグラフ探索装置であって、
    　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
    　ことを特徴とするグラフ探索装置。
  4. 　請求項１から３のいずれか一つに記載のグラフ探索装置であって、
    　前記生成手段と前記分類手段とを、ベクトルプロセッサを用いて動作させる
    　ことを特徴とするグラフ探索装置。
  5. （ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成し、
    （ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する
    　ことを特徴とするグラフ探索方法。
  6. 　請求項５に記載のグラフ探索方法であって、
    　前記（ｂ）において、
    　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
    　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
    　ことを特徴とするグラフ探索方法。
  7. 　請求項５又は６に記載のグラフ探索方法であって、
    　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
    　ことを特徴とするグラフ探索方法。
  8. 　コンピュータに、
    （ａ）グラフに含まれる頂点の隣接関係に基づいて複数の頂点を選択し、選択した前記頂点に対応する要素ごとに異なるラベルを設定したフロンティア行列を生成する、ステップと、
    （ｂ）前記グラフに含まれる頂点の隣接関係を表す隣接行列と前記フロンティア行列とを用いて、頂点を分類する、ステップと、
    　を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
  9. 　請求項８に記載のコンピュータ読み取り可能な記録媒体であって、
    　前記（ｂ）のステップにおいて、
    　前記隣接行列と前記フロンティア行列との積である第一の行列から、グラフ探索済みの頂点を表すための第二の行列を参照し、探索済み頂点に対応する要素を除外して、新たなフロンティア行列を生成し、
    　前記第一の行列と前記第二の行列との和を算出し、新たな第二の行列を生成して頂点を分類する
    　ことを特徴とするコンピュータ読み取り可能な記録媒体。
  10. 　請求項８又は９に記載のコンピュータ読み取り可能な記録媒体であって、
    　前記ラベルは、始点となる頂点の数に基づいてビット幅を決める
    　ことを特徴とするコンピュータ読み取り可能な記録媒体。
PCT/JP2019/047708 2019-12-05 2019-12-05 グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体 Ceased WO2021111606A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2021562409A JP7497734B2 (ja) 2019-12-05 2019-12-05 グラフ探索装置、グラフ探索方法、及びプログラム
PCT/JP2019/047708 WO2021111606A1 (ja) 2019-12-05 2019-12-05 グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体
US17/779,653 US20220414077A1 (en) 2019-12-05 2019-12-05 Graph searching apparatus, graph searching method, and computer-readable recording medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2019/047708 WO2021111606A1 (ja) 2019-12-05 2019-12-05 グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体

Publications (1)

Publication Number Publication Date
WO2021111606A1 true WO2021111606A1 (ja) 2021-06-10

Family

ID=76222502

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2019/047708 Ceased WO2021111606A1 (ja) 2019-12-05 2019-12-05 グラフ探索装置、グラフ探索方法、及びコンピュータ読み取り可能な記録媒体

Country Status (3)

Country Link
US (1) US20220414077A1 (ja)
JP (1) JP7497734B2 (ja)
WO (1) WO2021111606A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113987643A (zh) * 2021-10-27 2022-01-28 南京林业大学 一种基于辅助点的机场滑行道模型构建方法

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3798179B2 (ja) * 1999-05-14 2006-07-19 富士通株式会社 パターン抽出装置及び文字切り出し装置
US9082082B2 (en) * 2011-12-06 2015-07-14 The Trustees Of Columbia University In The City Of New York Network information methods devices and systems
CN108062551A (zh) * 2017-06-28 2018-05-22 浙江大学 一种基于邻接矩阵的图特征提取系统、图分类系统和方法
CN108520275A (zh) * 2017-06-28 2018-09-11 浙江大学 一种基于邻接矩阵的连接信息规整系统、图特征提取系统、图分类系统和方法
WO2019023500A1 (en) * 2017-07-26 2019-01-31 The Trustees Of Dartmouth College PERCEPTUAL APPARATUS IMPLEMENTED BY COMPUTER
US11853903B2 (en) * 2017-09-28 2023-12-26 Siemens Aktiengesellschaft SGCNN: structural graph convolutional neural network
US10482375B2 (en) * 2017-11-02 2019-11-19 Palo Alto Research Company Incorporated Deep graph representation learning
US12248877B2 (en) * 2018-05-23 2025-03-11 Movidius Ltd. Hybrid neural network pruning

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
BHAGAT, SMRITI ET AL.: "Applying Link-based Classification to Label Biogs", PROCEEDINGS OF THE JOINT 9TH WEBKDD AND 1ST SNA-KDD 2007 WORKSHOP ON WEB MINING AND SOCIAL NETWORK ANALYSIS (WEBKDD/SNA-KDD'07, 12 August 2007 (2007-08-12), pages 92 - 101, XP058211863, DOI: 10.1145/1348549.1348560 *
BULUC, AYDIN ET AL.: "Design of the GraphBLAS API for C", PROCEEDINGS OF THE 2017 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW 2017, 2 June 2017 (2017-06-02), pages 643 - 652, XP033113746, DOI: 10.1109/IPDPSW.2017.117 *
LU, HUIWEI ET AL.: "Reducing Communication in Parallel Breadth-First Search on Distributed Memory Systems", PROCEEDINGS OF THE 2014 IEEE 17TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND ENGINEERING, 21 December 2014 (2014-12-21), pages 1261 - 1268, XP032730289, ISBN: 978-1-4799-7981-3, DOI: 10.1109/CSE.2014.243 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113987643A (zh) * 2021-10-27 2022-01-28 南京林业大学 一种基于辅助点的机场滑行道模型构建方法

Also Published As

Publication number Publication date
US20220414077A1 (en) 2022-12-29
JPWO2021111606A1 (ja) 2021-06-10
JP7497734B2 (ja) 2024-06-11

Similar Documents

Publication Publication Date Title
JP6542909B2 (ja) ファイル操作方法及び装置
US20170103214A1 (en) Testing insecure computing environments using random data sets generated from characterizations of real data sets
US20130347118A1 (en) License verification method and apparatus, and computer readable storage medium storing program therefor
US11928095B2 (en) Image analysis interface
CN114036171B (zh) 应用数据管理方法、装置、计算机设备和存储介质
US9311348B2 (en) Method and system for implementing an array using different data structures
JP6281491B2 (ja) テキストマイニング装置、テキストマイニング方法及びプログラム
JP7131620B2 (ja) データ解析支援装置、データ解析支援方法、及びプログラム
JP2023553220A (ja) マルチインスタンスプロセスのためのプロセスマイニング
JP7497734B2 (ja) グラフ探索装置、グラフ探索方法、及びプログラム
WO2021255859A1 (ja) 推論装置、推論方法、及びコンピュータ読み取り可能な記録媒体
US10740070B2 (en) Locating features in a layered software application
JP7711845B2 (ja) システム検証装置、システム検証方法、及びプログラム
CN116089072A (zh) 业务应用的调整方法、装置、计算机设备和存储介质
JP2020126499A (ja) 情報可視化装置、情報可視化方法、及びプログラム
JP2018163505A (ja) 検索プログラム、情報処理装置および検索方法
CN113723436A (zh) 数据的处理方法、装置、计算机设备和存储介质
JP7782729B2 (ja) 情報処理装置、方法およびプログラム
JPWO2017175375A1 (ja) データクレンジングシステム、方法、及び、プログラム
JP7708216B2 (ja) コード変換装置、コード変換方法、及びプログラム
CN117194721B (zh) 生成图数据的方法、装置及计算机设备
WO2018193707A1 (ja) 情報処理装置、プログラム、情報処理方法及びデータ構造
WO2020008631A1 (ja) 観測事象判定装置、観測事象判定方法、及びコンピュータ読み取り可能な記録媒体
KR102289411B1 (ko) 가중치 기반의 피처 벡터 생성 장치 및 방법
JP7218856B2 (ja) 学習器生成装置、学習器の生産方法、およびプログラム

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19955031

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021562409

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 19955031

Country of ref document: EP

Kind code of ref document: A1