68 |
68 |
69 ///Adds a Petersen graph to \c G. |
69 ///Adds a Petersen graph to \c G. |
70 ///\return The nodes and edges of the generated graph. |
70 ///\return The nodes and edges of the generated graph. |
71 |
71 |
72 template<typename Graph> |
72 template<typename Graph> |
73 PetStruct<Graph> addPetersen(Graph &G,int num=5) |
73 PetStruct<Graph> addPetersen(Graph &G,int num = 5) |
74 { |
74 { |
75 PetStruct<Graph> n; |
75 PetStruct<Graph> n; |
76 |
76 |
77 for(int i=0;i<num;i++) { |
77 for(int i=0;i<num;i++) { |
78 n.outer.push_back(G.addNode()); |
78 n.outer.push_back(G.addNode()); |
79 n.inner.push_back(G.addNode()); |
79 n.inner.push_back(G.addNode()); |
80 } |
80 } |
81 |
81 |
82 for(int i=0;i<num;i++) { |
82 for(int i=0;i<num;i++) { |
83 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); |
83 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); |
84 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5])); |
84 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num])); |
85 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5])); |
85 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num])); |
86 } |
86 } |
87 return n; |
87 return n; |
|
88 } |
|
89 |
|
90 /// \brief Adds to the graph the reverse pair of all edge. |
|
91 /// |
|
92 /// Adds to the graph the reverse pair of all edge. |
|
93 /// |
|
94 template<class Graph> void bidirGraph(Graph &G) |
|
95 { |
|
96 typedef typename Graph::Edge Edge; |
|
97 typedef typename Graph::EdgeIt EdgeIt; |
|
98 |
|
99 std::vector<Edge> ee; |
|
100 |
|
101 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); |
|
102 |
|
103 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) |
|
104 G.addEdge(G.head(*p),G.tail(*p)); |
|
105 } |
|
106 |
|
107 |
|
108 /// \brief Checks the bidirectioned Petersen graph. |
|
109 /// |
|
110 /// Checks the bidirectioned Petersen graph. |
|
111 /// |
|
112 template<class Graph> void checkBidirPetersen(Graph &G, int num = 5) |
|
113 { |
|
114 typedef typename Graph::Node Node; |
|
115 |
|
116 typedef typename Graph::EdgeIt EdgeIt; |
|
117 typedef typename Graph::NodeIt NodeIt; |
|
118 |
|
119 checkGraphNodeList(G, 2 * num); |
|
120 checkGraphEdgeList(G, 6 * num); |
|
121 |
|
122 for(NodeIt n(G);n!=INVALID;++n) { |
|
123 checkGraphInEdgeList(G, n, 3); |
|
124 checkGraphOutEdgeList(G, n, 3); |
|
125 } |
88 } |
126 } |
89 |
127 |
90 ///Structure returned by \ref addSymPetersen(). |
128 ///Structure returned by \ref addSymPetersen(). |
91 |
129 |
92 ///Structure returned by \ref addSymPetersen(). |
130 ///Structure returned by \ref addSymPetersen(). |