Graph

Inherits: Resource < Reference < Object

A general-purpose mixed graph.

Description

A graph which allows to add both undirected (associative) and directed edges, with possibility of having multiple edges between the same pair of vertices.

func _ready():
    var graph = Graph.new()

    var a = graph.add_vertex("a")
    var b = graph.add_vertex("b")
    var c = graph.add_vertex("c")

    var ab = graph.add_edge(a, b)

    print(graph.has_edge(a, b)) # Prints True
    print(graph.has_edge(a, c)) # Prints False

All graph’s vertices and edges can be traversed the following way:

for v in graph.get_vertices():
    print(v)

for e in graph.get_edges():
    print(e)

You can also use a built-in (GDScript) iterator to traverse all vertices (may be slower):

for v in graph:
    print(v)

It is possible to extend GraphVertex and GraphEdge via script, but you should also override _create_vertex and _create_edge virtual methods to make the Graph instantiate the correct instances internally.

The graph can be searched by using an iterator (using either depth-first or breadth-first search algorithm):

var G = graph.iterator
G.initialize(root)

while G.has_next():
    var v = G.next()
    print(v)

For performance reasons, the graph uses unordered hashmap data structure, so insertion order of vertices and edges should not be assumed to be the same. Adding or removing vertices/edges while iterating the graph may lead to undefined behavior.

Properties

Dictionary data {"edges": [  ],"vertices": [  ]}
GraphIterator iterator  

Property Descriptions

Default {"edges": [  ],"vertices": [  ]}

Graph data, which contains all vertices and edges.

The vertices are stored in a single Array where values and IDs (unsigned int) are stored consecutively.

The edges represent an Array of edge data. The edge data is represented by an Array which stores the following fields:

unsigned int: ID of vertex a

unsigned int: ID of vertex b

Variant: Value (can be anything).

bool: Whether the edge is directed or not.

Setter set_iterator(value)
Getter get_iterator()

An iterator used for traversing the graph’s vertices. The default iterator is based on depth-first search algorithm. You can extend GraphIterator class via script to customize the algorithm.

If set to null, the default iterator is used.

Method Descriptions

  • Object _create_edge ( ) virtual

Must return an instance of GraphEdge.

  • Object _create_vertex ( ) virtual

Must return an instance of GraphVertex.

Adds a directed edge between a and b vertices. The value could represent a weight of the edge, or other attributes. The following expressions are not equivalent:

graph.has_edge(a, b)  # Prints True
graph.has_edge(b, a)  # Prints False

Adds an undirected (associative) edge between a and b vertices. The value could represent a weight of the edge, or other attributes. The following instructions are equivalent:

graph.has_edge(a, b)  # Prints True
graph.has_edge(b, a)  # Prints True

Adds a new vertex to the graph. The value represents the data or attribute of that vertex.

  • void clear ( )

Removes all vertices and edges from the graph.

  • void clear_edges ( )

Removes all edges from the graph while retaining all original vertices.

Returns an array of vertices representing a connected component in an undirected graph starting from arbitrary vertex root.

Returns the first found edge between a and b vertices. There may be multiple edges between vertices. If you need to find a specific edge, use get_edges instead.

Returns the first found vertex that contains a specified value.

Returns a Dictionary of all connected components in the graph. The keys consist of a set of vertices called representatives, while values contain all members Array of vertices of that representative:

var representatives = graph.get_connected_components()
for r in representatives:
    print("Representative: ", r)
    var members = representatives[r]
    for m in members:
        print("Member: ", m)

All members represent a connected component. A representative is considered as a member of the connected component. A connected component may consist of a single vertex.

  • int get_edge_count ( ) const

Returns the total number of edges in this graph.

Returns a list of GraphEdges between a and b vertices. If both endpoints are null, then the method returns all edges in the graph instead.

  • int get_vertex_count ( ) const

Returns the total number of vertices in this graph.

  • Array get_vertices ( ) const

Returns a list of GraphVertex elements in this graph.

Returns whether any edge exists between a and b vertices.

Returns whether the graph contains the specified vertex.

  • bool is_strongly_connected ( )

Returns true if there exist at least one path connecting any two vertices. Applies both to undirected and directed graphs.

  • Array minimum_spanning_tree ( ) const

Returns a minimum spanning tree (MST) of this graph using Kruskal’s algorithm. An MST is represented as an Array of GraphEdges in this graph, from which you can create a new Graph, if you need to.

The GraphEdge.value is interpreted as a float weight, which is up to you to define.

In order to obtain a maximum spanning tree, you can inverse the weights, for example:

var a = graph.add_vertex(Vector2(0, 0))
var b = graph.add_vertex(Vector2(100, 100))
var w = a.value.distance_to(b.value) # Euclidean distance.
graph.add_edge(a, b, -w) # Notice negative weight.

Note: there may exist several MSTs if some edges have equal weight. If weights are not configured, the method will eliminate all edges that cause cycles (a tree is an acyclic graph).

Removes an edge from the graph. If the graph is simple, you could find an edge with find_edge first, and then remove it.

Alternatively, you can also remove the edge by calling Object.free on it.

Removes the specified vertex from the graph. All edges that are connected to the vertex will be automatically deleted.

Alternatively, you can also remove the vertex by calling Object.free on it.

  • void set_iterator_bfs ( )

Use breadth-first search iterator.

  • void set_iterator_dfs ( )

Use depth-first search iterator (default).

Returns a shortest path tree starting at the root vertex using Dijkstra’s algorithm. This solves the Single-Source Shortest Path (SSSP) problem, which allows to find the shortest paths between a given vertex to all other vertices in the graph. The algorithm is structurally equivalent to the breadth-first search, except that this uses a priority queue to choose the next vertex based on GraphEdge.value weights interpreted as float values. The weight of each edge should not be negative for the Dijkstra’s algorithm to work properly.

The tree is represented as a Dictionary containing the following keys:

backtrace: A Dictionary which contains an exhaustive information that allows to reconstruct the shortest path. The keys hold current GraphVertex, and values contain previous GraphVertex. Therefore, the shortest path between the source to any other connected vertex can be obtained in the following way:

# Find the shortest path tree starting from the root vertex of interest.
var root = Random.pick(graph.get_vertices())
var tree = graph.shortest_path_tree(root)

# Pick any target vertex.
var current = Random.pick(graph.get_vertices())

# Extract shortest path.
var shortest_path = []
while true:
    shortest_path.append(current)
    var previous = tree.backtrace[current]
    if not previous:
        break # Reached source vertex (root).
    current = previous

# Invert the path for source-to-target order.
shortest_path.invert()

distance: A Dictionary which contains the total distance (sum of edge weights) between source and target. The key is the GraphVertex, the value is float.

edges: An Array of all GraphEdges reachable from the root vertex. Since there may be multiple edges between vertices, the edges with the minimum weight are collected only.