This module provide a set of graph concepts to form a graph interface

exception core.graph.interface.graph.GraphError

Bases: exceptions.Exception

base class of all graph exceptions

exception core.graph.interface.graph.InvalidEdge

Bases: core.graph.interface.graph.GraphError, exceptions.KeyError

exception raised when a wrong edge id is provided

exception core.graph.interface.graph.InvalidVertex

Bases: core.graph.interface.graph.GraphError, exceptions.KeyError

exception raised when a wrong vertex id is provided

class core.graph.interface.graph.ICopyGraph

Bases: object

allow the graph to be copied

copy()

make a shallow copy of the graph, for a deep copy use the constructor __init__

class core.graph.interface.graph.IEdgeListGraph

Bases: object

Definition of a graph seen as a list of edges

edges(vid=None)

retrieve the edges linked to a specified vertex, all if vid is None

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

in_edges(vid)

retrieve the edges linked to a specified vertex, oriented inside the vertex

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

nb_edges(vid=None)

number of edges linked to a specified vertex, total number if vid is None

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

nb_in_edges(vid)

number of edges linked to a specified vertex, oriented inside vertex

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

nb_out_edges(vid)

number of edges linked to a specified vertex, oriented outside vertex

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

out_edges(vid)

retrieve the edges linked to a specified vertex, oriented outside the vertex

Parameters:vid (vid) -- id of the reference vertex, default=None Return type:iter of eid

class core.graph.interface.graph.IExtendGraph

Bases: object

allow the graph to be extended by another graph

extend(graph)

add the specified graph to self, create new vid and eid

Parameters:graph (Graph) -- the graph to add Returns:two dictionnary specifying correspondence between graph id and self id Return type:({vid:vid},{eid:eid})

class core.graph.interface.graph.IGraph

Bases: object

Directed graph definition

edge(source, target)

find the matching edges with same source and same target return None if it don't succeed

Parameters:

• source : id of the source vertex
• target : id of the target vertex

Types:

• source : vid
• target : vid

Return type:

eid|iter of eid|None

has_edge(eid)

test wether an edge belong to the graph

Parameters:eid (eid) -- edge id to test Return type:bool

has_vertex(vid)

test wether a vertex belong to the graph

Parameters:vid (vid) -- vertex id to test Return type:bool

is_valid()

test the validity of the graph

Return type:bool

source(eid)

retrieve the source of an edge

Parameters:eid (eid) -- id of the edge Return type:vid

target(eid)

retrieve the target of an edge

Parameters:eid (eid) -- id of the edge Return type:vid

class core.graph.interface.graph.IMutableEdgeGraph

Bases: object

definition of graph edition methods for edges

add_edge(edge=(None, None), eid=None)

add an edge to the graph, if eid is not provided create a new eid

Parameters:

• edge : a tuple (vertex source,vertex target)
• eid : the id of the created edge

Types:

• edge : (vid,vid)
• eid : eid

Returns:

the id of the newly created edge

Return type:

eid

clear_edges()

remove all the edges of the graph don't change references to objects

remove_edge(eid)

remove a specified edge from the graph

Parameters:eid (eid) -- id of the edge to remove

class core.graph.interface.graph.IMutableVertexGraph

Bases: object

definition of graph edition methods for vertices

add_vertex(vid=None)

add a vertex to the graph, if vid is not provided create a new vid

Parameters:vid (vid) -- the id of the vertex to add, default=None Returns:the id of the created vertex Return type:vid

clear()

remove all vertices and edges don't change references to objects

remove_vertex(vid)

remove a specified vertex of the graph remove all the edges attached to it

Parameters:vid (vid) -- the id of the vertex to remove

class core.graph.interface.graph.IVertexListGraph

Bases: object

interface of a graph seen as a vertex list

in_neighbors(vid)

iterator on the neighbors of vid where edges are directed from neighbor to vid

Parameters:vid (vid) -- id of the reference vertex Return type:iter of vid

nb_in_neighbors(vid)

number of neighbors such as edges are directed from neighbor to vid

Parameters:vid (vid) -- id of the reference vertex Return type:int

nb_neighbors(vid)

number of neighbors regardless of the orientation of the edge

Parameters:vid (vid) -- id of the reference vertex Return type:int

nb_out_neighbors(vid)

number of neighbors such as edges are directed from vid to neighbor

Parameters:vid (vid) -- id of the reference vertex Return type:int

nb_vertices()

return the total number of vertices

Return type:int

neighbors(vid)

iterator on the neighbors of vid regardless of the orientation of the edge

Parameters:vid (vid) -- id of the reference vertex Return type:iter of vid

out_neighbors(vid)

iterator on the neighbors of vid where edges are directed from vid to neighbor

Parameters:vid (vid) -- id of the reference vertex Return type:iter of vid

vertices()

iterator on vertices

Return type:iter of vid