際際滷

際際滷Share a Scribd company logo

Pcg2012 presentation

Marlon Etheredge
Marlon Etheredge

This document discusses an algorithm for fast exact graph matching using adjacency matrices. The algorithm represents graphs as adjacency matrices and subgraphs as patterns of node types and their connections. It recursively searches a target graph's adjacency matrix to find matches for patterns extracted from a subset graph. Benchmark results show it outperforms other graph matching algorithms like Ullmann's algorithm for smaller graphs, and performs similarly to VF2 for larger graphs. The algorithm allows flexible matching of complex graph structures in real-time for applications like procedurally generated games.

1 of 18
Download to read offline
Fast Exact Graph Matching Using Adjacency Matrices Marlon Etheredge Amsterdam University of Applied Sciences marlon.etheredge@hva.nl May 29, 2012
About Me Marlon Etheredge Student Amsterdam University of Applied Sciences Specialization in Game Technology Senior Software Engineer Realvine BV The Netherlands Freelance Owner Game Studio MangoDown! Catch-22, Winner Global Game Jam 2012 The Netherlands
About This Research DroidRacers Pre-graduation project Strong focus on Procedurally Generated Content Builds on work by Joris Dormans Used a na即 algorithm for graph isomorphism in a project 脹ve Tried to 鍖nd a more convenient way to solve this problem
DroidRacers In鍖nite Racing Game Played on public screen Controllable by Android Devices Scan the QRCode in the game screen to become a participant in the game Constantly changing game state and skill set of players Players can join or leave an active game The game should be altered according to these changes Procedural Content Race tracks Power ups Goals Etc.
The Problem: Genetic vs Graph Based Procedural Content Requirement of realtime alternation of structures within the game Evolutionary algorithms require an arbitrary number of generations Undesired with the quick and direct way of transformations we demand Graph Based Procedural Content o鍖ers us fast and direct modi鍖cation of structures within the game Practically any structure within the game may be represented by a graph Allows for the modi鍖cations of a lot of structures within the game
The Problem: Graph Isomorphism Graph Based Procedural Content requires fast realtime Graph Transformation Fast realtime algorithm for solving the Graph Isomorphism problem Existing well-known algorithms including: VF2 Mainly focuses on large graphs Ullmann Too slow for usage in our project R. Heckel Exponential processing time Need for a fast algorithm still o鍖ering full 鍖exibility
The Problem: Example A game of any kind might encapsulate the abstract structure as presented in the 鍖gure below A node within this graph might be any entity within the game, a connection de鍖nes a connection between the two entities We might want to replace the highlighted structure in the 鍖gure with another structure to adjust our game according to a particular case Subset in graph C6 B5 A9 E7 A10 B8 A1 B2 D3 D4 The subset matched in the graph
Na即 Search Operation 脹ve Describing subgraph A by: An as a set of nodes existing in A Aout as a set of outgoing edges Ain as a set of incoming edges Aout An , Ain An Describing target graph G by: Gout as a set of outgoing edges Gin as a set of incoming edges Gout Gn , Gin Gn A search operation would recursively search every node in Gout for a node in Aout, which would cause exponential processing time as well as undesired levels of recursion
Our Algorithm: Adjacency Matrices Uses adjacency matrices Adjacency matrix generation by trivial function For every connection in set set in a two dimensional by index of 鍖rst node and index of second node, a one Matrices should store connection count for rows and columns, convenient to store this at the end of the row or column C1 E2 B3 A4 A5 B6 l 錚 錚 C1 C1 0 0 0 0 0 0 0 B6 A5 A4 E2 E2 錚 1 錚 0 1 0 0 0 2錚件７ B3 B3 錚 0 錚 0 0 0 0 0 0錚件７ Pattern A4 錚 0 錚 1 0 0 0 0 1錚件７ A5 錚 0 錚 0 0 1 0 0 1錚件７ B6 錚 0 0 0 0 1 0 1錚 l 1 1 1 1 1 0 0
Our Algorithm: Patterns Map containing a key and one or more value entries Key described the node type that requires the entries in the values of the map Basically a representation of a row, using a node types as storage type and node type that required connections as key value Patterns are constructed from the subset graph adjacency matrix Used to scan the adjacency matrix of the target graph, to test if edges exist for a speci鍖c node Set of patterns condenses more narrow when more matches are found E {C , B} C1 B6 A5 A4 E2 B{A} B3 A{A} Pattern A{E }
Our Algorithm: Explained Convert both the target graph as the subset graph into adjacency matrices Extract patterns from the subset graph adjacency matrix Sort the set of patterns according to the number of requirements in the pattern Recursively search trough the node set of the target graph, adding all accepted requirements as matches In case we have found all requirements for the current pattern, mark the current node as an actual match and mark the current pattern as used Recursively search through next patterns
Flexibility: Complex Search Cases More complex search cases Example, in this graph the search operation should return multiple matches, both the upper set of nodes as the lower set of nodes Such a case is hard to successfully return in a traditional search algorithm, since every connection that is entered needs to be stored and later searched again for the case of multiple equal branches Results in loss of performance on many equal branches Our algorithm handles such a case naturally, since both branches are already pushed inside the list of matches that are searched recursively B2 A5 A1 B3 B2 A0 A0 A1 B4 B3
Flexibility: Advanced Node Types Along with solving more complex cases of graph matching, our algorithm allows for the matching of more complex node types For instance Wildcard: A node type that allows for any graph structure positioned at the wildcard node in a subgraph to be accepted by the search operation Exclusion: Node type that accepts nodes that are not of the not-node type positioned at the not-node in a subgraph. Times: Node type that allows for any graph structure described by the structure in the subgraph positioned at the time node in a subgraph to be accepted by the search operation one or times These cases are implemented by simply overriding any method that contains the equal logic that is used within the search operation
Benchmark: Method Ran worst case scenario search operations on increasingly complex graphs Worst case where every node in the graph should be visited prior to completing the full search operation (number of nodes in matches is equal to the number of nodes in the graph) Implementations in C++, benchmarked against Ullmanns algorithm and VF2 (both from the VFLib library) Timing using standard C++ timing functions
Benchmark: Results Time (seconds 100 Ullmann 10-1 Our algorithm 10-2 VF2 10-3 10-4 Nodes 10-5 10 100 1000 Faster at low node count, with tipping point between 100 and 100 nodes Above 1000 nodes the implementation of our algorithm sticks close to the VF2 implementation
Conclusion Subgraph searching allows to solve various problems in computer science in a neat and fast way and allows for search/replace operations to be performed Our algorithm allows to solve the graph isomorphism problem in realtime while still o鍖ering full 鍖exibility In the domain of game development this technique allows us to perform operations on graph-based game design structures Opening new possibilities to introduce new ways of procedurally generated games and procedurally generated gameplay; game mechanics may be altered and introduced in-game Allowing for new games with more dynamic gameplay
Further Application and Research Focus on graph-based procedurally generated games Graph transformation using neural network with input from player Allowing for completely dynamic gameplay, gameplay is adjusted according to the complete style of a player Graph isomorphism in parallel computing, CUDA implementation, allowing for even faster search operations and even more complex structures
Thank You Very Much Thank you! Marlon Etheredge marlon.etheredge@gmail.com http://marlonetheredge.name/

More Related Content

Pcg2012 presentation

  • 1. Fast Exact Graph Matching Using Adjacency Matrices Marlon Etheredge Amsterdam University of Applied Sciences marlon.etheredge@hva.nl May 29, 2012
  • 2. About Me Marlon Etheredge Student Amsterdam University of Applied Sciences Specialization in Game Technology Senior Software Engineer Realvine BV The Netherlands Freelance Owner Game Studio MangoDown! Catch-22, Winner Global Game Jam 2012 The Netherlands
  • 3. About This Research DroidRacers Pre-graduation project Strong focus on Procedurally Generated Content Builds on work by Joris Dormans Used a na即 algorithm for graph isomorphism in a project 脹ve Tried to 鍖nd a more convenient way to solve this problem
  • 4. DroidRacers In鍖nite Racing Game Played on public screen Controllable by Android Devices Scan the QRCode in the game screen to become a participant in the game Constantly changing game state and skill set of players Players can join or leave an active game The game should be altered according to these changes Procedural Content Race tracks Power ups Goals Etc.
  • 5. The Problem: Genetic vs Graph Based Procedural Content Requirement of realtime alternation of structures within the game Evolutionary algorithms require an arbitrary number of generations Undesired with the quick and direct way of transformations we demand Graph Based Procedural Content o鍖ers us fast and direct modi鍖cation of structures within the game Practically any structure within the game may be represented by a graph Allows for the modi鍖cations of a lot of structures within the game
  • 6. The Problem: Graph Isomorphism Graph Based Procedural Content requires fast realtime Graph Transformation Fast realtime algorithm for solving the Graph Isomorphism problem Existing well-known algorithms including: VF2 Mainly focuses on large graphs Ullmann Too slow for usage in our project R. Heckel Exponential processing time Need for a fast algorithm still o鍖ering full 鍖exibility
  • 7. The Problem: Example A game of any kind might encapsulate the abstract structure as presented in the 鍖gure below A node within this graph might be any entity within the game, a connection de鍖nes a connection between the two entities We might want to replace the highlighted structure in the 鍖gure with another structure to adjust our game according to a particular case Subset in graph C6 B5 A9 E7 A10 B8 A1 B2 D3 D4 The subset matched in the graph
  • 8. Na即 Search Operation 脹ve Describing subgraph A by: An as a set of nodes existing in A Aout as a set of outgoing edges Ain as a set of incoming edges Aout An , Ain An Describing target graph G by: Gout as a set of outgoing edges Gin as a set of incoming edges Gout Gn , Gin Gn A search operation would recursively search every node in Gout for a node in Aout, which would cause exponential processing time as well as undesired levels of recursion
  • 9. Our Algorithm: Adjacency Matrices Uses adjacency matrices Adjacency matrix generation by trivial function For every connection in set set in a two dimensional by index of 鍖rst node and index of second node, a one Matrices should store connection count for rows and columns, convenient to store this at the end of the row or column C1 E2 B3 A4 A5 B6 l 錚 錚 C1 C1 0 0 0 0 0 0 0 B6 A5 A4 E2 E2 錚 1 錚 0 1 0 0 0 2錚件７ B3 B3 錚 0 錚 0 0 0 0 0 0錚件７ Pattern A4 錚 0 錚 1 0 0 0 0 1錚件７ A5 錚 0 錚 0 0 1 0 0 1錚件７ B6 錚 0 0 0 0 1 0 1錚 l 1 1 1 1 1 0 0
  • 10. Our Algorithm: Patterns Map containing a key and one or more value entries Key described the node type that requires the entries in the values of the map Basically a representation of a row, using a node types as storage type and node type that required connections as key value Patterns are constructed from the subset graph adjacency matrix Used to scan the adjacency matrix of the target graph, to test if edges exist for a speci鍖c node Set of patterns condenses more narrow when more matches are found E {C , B} C1 B6 A5 A4 E2 B{A} B3 A{A} Pattern A{E }
  • 11. Our Algorithm: Explained Convert both the target graph as the subset graph into adjacency matrices Extract patterns from the subset graph adjacency matrix Sort the set of patterns according to the number of requirements in the pattern Recursively search trough the node set of the target graph, adding all accepted requirements as matches In case we have found all requirements for the current pattern, mark the current node as an actual match and mark the current pattern as used Recursively search through next patterns
  • 12. Flexibility: Complex Search Cases More complex search cases Example, in this graph the search operation should return multiple matches, both the upper set of nodes as the lower set of nodes Such a case is hard to successfully return in a traditional search algorithm, since every connection that is entered needs to be stored and later searched again for the case of multiple equal branches Results in loss of performance on many equal branches Our algorithm handles such a case naturally, since both branches are already pushed inside the list of matches that are searched recursively B2 A5 A1 B3 B2 A0 A0 A1 B4 B3
  • 13. Flexibility: Advanced Node Types Along with solving more complex cases of graph matching, our algorithm allows for the matching of more complex node types For instance Wildcard: A node type that allows for any graph structure positioned at the wildcard node in a subgraph to be accepted by the search operation Exclusion: Node type that accepts nodes that are not of the not-node type positioned at the not-node in a subgraph. Times: Node type that allows for any graph structure described by the structure in the subgraph positioned at the time node in a subgraph to be accepted by the search operation one or times These cases are implemented by simply overriding any method that contains the equal logic that is used within the search operation
  • 14. Benchmark: Method Ran worst case scenario search operations on increasingly complex graphs Worst case where every node in the graph should be visited prior to completing the full search operation (number of nodes in matches is equal to the number of nodes in the graph) Implementations in C++, benchmarked against Ullmanns algorithm and VF2 (both from the VFLib library) Timing using standard C++ timing functions
  • 15. Benchmark: Results Time (seconds 100 Ullmann 10-1 Our algorithm 10-2 VF2 10-3 10-4 Nodes 10-5 10 100 1000 Faster at low node count, with tipping point between 100 and 100 nodes Above 1000 nodes the implementation of our algorithm sticks close to the VF2 implementation
  • 16. Conclusion Subgraph searching allows to solve various problems in computer science in a neat and fast way and allows for search/replace operations to be performed Our algorithm allows to solve the graph isomorphism problem in realtime while still o鍖ering full 鍖exibility In the domain of game development this technique allows us to perform operations on graph-based game design structures Opening new possibilities to introduce new ways of procedurally generated games and procedurally generated gameplay; game mechanics may be altered and introduced in-game Allowing for new games with more dynamic gameplay
  • 17. Further Application and Research Focus on graph-based procedurally generated games Graph transformation using neural network with input from player Allowing for completely dynamic gameplay, gameplay is adjusted according to the complete style of a player Graph isomorphism in parallel computing, CUDA implementation, allowing for even faster search operations and even more complex structures
  • 18. Thank You Very Much Thank you! Marlon Etheredge marlon.etheredge@gmail.com http://marlonetheredge.name/