Ask Your Question
1

can we use BFS and DFS algorithm in sagemath?

asked 2019-01-09 05:18:58 -0600

Nagarjun gravatar image

hello, I want to color the vertices of graphs using greedy or BFS algorithm. can do that in sagemath?

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2019-01-10 18:34:48 -0600

tmonteil gravatar image

updated 2019-01-10 18:35:38 -0600

You can do BFS and DFS as follows:

sage: G = graphs.PetersenGraph()
sage: G.plot()
sage: list(G.breadth_first_search(start=3))
[3, 2, 4, 8, 1, 7, 0, 9, 5, 6]
sage: list(G.depth_first_search(start=3))
[3, 8, 6, 9, 7, 5, 0, 4, 1, 2]

What you get is the ordered list of vertices visited in both searches, starting from vertex 3.

Regarding coloring, i am not sure about your exact question. If you want to provide colors to the vertices to show the order of visit, you can try somthing like:

sage: G.plot(vertex_colors={rainbow(40)[i]:[v] for i,v in enumerate(G.breadth_first_search(start=3))})

With more striking example:

sage: G = graphs.Grid2dGraph(10,10)
sage: G.plot()
sage: G.plot(vertex_colors={rainbow(500)[i]:[v] for i,v in enumerate(G.breadth_first_search(start=(0,0)))})
sage: sage: G.plot(vertex_colors={rainbow(500)[i]:[v] for i,v in enumerate(G.depth_first_search(start=(0,0)))})
edit flag offensive delete link more
0

answered 2019-01-10 12:58:26 -0600

slelievre gravatar image

updated 2019-01-10 13:02:54 -0600

In SageMath, if you define a graph G (for example G = Graph()), then G.coloring? gives the documentation of the coloring method for G, and G.coloring?? gives the source code.

Reading the documentation reveals two choices are offered: using the "dancing link algorithm" or using "mixed linear integer programming".

See also SageMath documentation for graph coloring.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-01-09 05:18:58 -0600

Seen: 114 times

Last updated: Jan 10