Graph

class pydatastructs.Graph(*args, **kwargs)

Represents generic concept of graphs.

Parameters

• implementation (str) –

  The implementation to be used for storing graph in memory. It can be figured out from type of the vertices(if passed at construction). Currently the following implementations are supported,

  ’adjacency_list’ -> Adjacency list implementation.

  ’adjacency_matrix’ -> Adjacency matrix implementation.

  By default, ‘adjacency_list’.

• vertices (GraphNode(s)) – For AdjacencyList implementation vertices can be passed for initializing the graph.

Examples

>>> from pydatastructs.graphs import Graph
>>> from pydatastructs.utils import AdjacencyListGraphNode
>>> v_1 = AdjacencyListGraphNode('v_1', 1)
>>> v_2 = AdjacencyListGraphNode('v_2', 2)
>>> g = Graph(v_1, v_2)
>>> g.add_edge('v_1', 'v_2')
>>> g.add_edge('v_2', 'v_1')
>>> g.is_adjacent('v_1', 'v_2')
True
>>> g.is_adjacent('v_2', 'v_1')
True
>>> g.remove_edge('v_1', 'v_2')
>>> g.is_adjacent('v_1', 'v_2')
False
>>> g.is_adjacent('v_2', 'v_1')
True

References

1

https://en.wikipedia.org/wiki/Graph_(abstract_data_type)

Note

Make sure to create nodes (AdjacencyListGraphNode or AdjacencyMatrixGraphNode) and them in your graph using Graph.add_vertex before adding edges whose end points require either of the nodes that you added. In other words, Graph.add_edge doesn’t add new nodes on its own if the input nodes are not already present in the Graph.

is_adjacent(node1, node2)

Checks if the nodes with the given with the given names are adjacent to each other.

neighbors(node)

Lists the neighbors of the node with given name.

add_vertex(node)

Adds the input vertex to the node, or does nothing if the input vertex is already in the graph.

remove_vertex(node)

Removes the input vertex along with all the edges pointing towards it.

add_edge(source, target, cost=None)

Adds the edge starting at first parameter i.e., source and ending at the second parameter i.e., target.

get_edge(source, target)

Returns GraphEdge object if there is an edge between source and target otherwise None.

remove_edge(source, target)

Removes the edge starting at first parameter i.e., source and ending at the second parameter i.e., target.

__module__ = 'pydatastructs.graphs.graph'