0
$\begingroup$

I'd like to know that how can I find circuit(basic), simple path, closed path of these edges:

Example:

V={V, R, F, P, W}
E={(V, R), (R, V), (R, F), (F, V), (V, W), (W, V), (W, P), (P, F)} 

Please mention all the steps as straight forward as possible. How can I find out that how many Circuits, cycles, closed paths, simple paths, ... with a specific length does it have?(and display the edges of that circuit, cycle, closed path, simple path ...)

For example: display circuits of 2 edges? answer should be: {(V, R), (R, V)}, {(V, W), (V, W)}

Thanks

$\endgroup$
3
  • 4
    $\begingroup$ Combinatorica would have been the method of choice in the past, but Graph[] is now built in. Have you looked at its documentation? $\endgroup$ – J. M.'s ennui May 12 '20 at 16:30
  • $\begingroup$ I have just graphed it, but how to find the circuit, simple path, closed path...? $\endgroup$ – Haley May 12 '20 at 18:13
  • 5
    $\begingroup$ Please show what you tried. When you are asking for help, it is best to try to meet us halfway. Include code to construct the graph. Define the concepts you want computed. Do search the documentation before asking, try the functions you find, and ask about the specific problems you encountered when trying to use them. $\endgroup$ – Szabolcs May 12 '20 at 19:35
1
$\begingroup$

First of all a graph edge in Mathematica is not defined by parentheses. You can use the command DirectedEdge[u,v] for an edge from the vertex u to another vertex v. Or you can use the command Rule[u,v]. For a two sided edge you can use TwoWayRule[u,v], for an undirected edge you can use UndirectedEdge[u,v]. Or you can use the keyboard, type u, then "Esc" key, then type ue (abbreviation of undirected edge), then press "Esc" key again. For directed edge use de instead of ue, or you can just type u->v. I also prefer to not use Capital letters for names of objects unless I really need and I'm sure it is not reserved for anything. So I changed your vertices names to small letters as well. To ask Mathematica to find a cycle in your graph just use the commend FindCycle[] and put name of your graph inside the brackets. To restrict it to cycles of a fixed length such as 2, just add the option {2} (without eyebrows, it will search for cycles with length at most equal to 2). Then Mathematica gives you only one cycle of interest. If you want to receive a list containing all of such cycles, add the option All. To ask Mathematica to highlight the cycle or any subgraph of your graph, just use the command Highlight and give names of your graph and the subgraph as its arguments. In below you can see how I did things I mentioned above on your graph.

vertices={v,r,f,p,w};
edges={DirectedEdge[v,r],DirectedEdge[r,v],DirectedEdge[r,f],DirectedEdge[f,v],DirectedEdge[v,w],DirectedEdge[w,v],DirectedEdge[w,p],DirectedEdge[p,f]};
graph=Graph[vertices,edges]
subgraph=FindCycle[graph,{2}]
HighlightGraph[graph,subgraph]
subgraphList=FindCycle[graph,{2},All]

To see the results in Mathematica itself, you can look at the following image.

enter image description here

$\endgroup$
0
$\begingroup$

Assuming a directed graph in which there's an edge connecting each vertex pair in a list, it's easy to convert the vertex list to edges (to make undirected edges, use UndirectedEdge). Use the list of edges to make a graph.

edges = DirectedEdge[##] & @@@ {{V,R}, {R,V}, {R,F}, {F,V}, {V,W}, {W,V}, {W,P}, {P,F}};
g = Graph[edges, VertexLabels->Automatic, ImageSize->Small]

graph from list of edges

Get vertex and edge lists from the graph with VertexList[g] and EdgeList[g].

Finding circuits of 2 edges is simple. Highlight the list of cycles on the graph with HighlightGraph. Use Grid and Partition to arrange the highlighted graphs into rows and columns, a technique we'll use later to display larger numbers of graphs.

edgeList = Sort@FindCycle[g, {2}, All]

circuits of 2 edges

Grid[Partition[HighlightGraph[g, #] &/@ edgeList, UpTo[3]], Frame->All]

graph of cycles

Find and display all cycles in the graph with FindCycle[g, Infinity, All].

edgeList = FindCycle[g, Infinity, All];
Grid[Partition[HighlightGraph[g, #] &/@ edgeList, UpTo[3]], Frame->All]

all cycles for a graph

Some graph manipulation functions, such as FindHamiltonianPath return a list of vertices, but we need a list of directed edges to display a highlighted graph. For example, to convert the FindHamiltonianPath vertex list into pairs of directed edges, use DirectedEdge[##] &@@@ Subsequences[FindHamiltonianPath[g], {2}].

edgeList = DirectedEdge[##] &@@@ Subsequences[FindHamiltonianPath[g], {2}];
HighlightGraph[g, edgeList], ImageSize->Small]

Hamiltonian path

FindPath returns lists of vertices, so we'll need to convert them to lists of edges following the Hamiltonian path example. FindPath can locate all simple paths between two vertices. For example, to find paths from vertex R to vertex P, use FindPath[g,R,P,Infinity,All].

edgeList = DirectedEdge[##] &@@@ Subsequences[#,{2}] &/@ FindPath[g,R,P,Infinity,All];
Grid[Partition[HighlightGraph[g, #] &/@ edgeList, UpTo[3]], Frame->All]

paths between two vertices

We can use the same method to find all simple paths between all edges, but first we need a list of each pair of vertices. Make the list with Sort@Permutations[VertexList[g], {2}]. Use the list of vertex pairs to make a grid of graphs that displays all paths between every pair of vertices (large grid of 28 graphs omitted).

edgeList = DirectedEdge[##] &@@@ Subsequences[#, {2}]
  &/@Flatten[FindPath[g, ##, Infinity, All]
  &@@@Sort@Permutations[VertexList[g], {2}], 1];
Grid[Partition[HighlightGraph[g, #] &/@ edgeList, UpTo[3]], Frame->All]

Using the edgeList, it's easy to choose only the paths of given length. For example, here's how to display all the paths with 4 edges:

Grid[Partition[HighlightGraph[g,#] &/@ Select[edgeList, Length[#]==4&], UpTo[3]], Frame->All]

paths with 4 edges

We can use edgeList to make a summary of the number of edges in the 28 paths:

pathList = KeySort@GroupBy[edgeList,Length];
TableForm[Transpose[{Keys[pathList],Length/@Values[pathList]}],
  TableHeadings->{None,{"edges","number of paths"}}]
edges  number of paths
1      8
2      9
3      8
4      3
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.