如何获取图中的所有子图？

Question

如何用伪代码从图中获取固定大小的所有子图？ （暴力）

如果可能的话，无需外部库。谢谢！

Answer 1

或多或少是这样的：

GenerateSubgraphs(Graph G):
    powerV = powerset(G.V)
    powerE = powerset(G.E)
    subgraphs = {}
    foreach V in powerV:
        foreach E in powerE:
            accept = true
            foreach edge in E:
                if edge.u not in V or edge.v not in V:
                    accept = false
            if accept:
                subgraphs.insert((V, E))
    return subgraphs

编辑：修复了“edges.insert”行的缩进

编辑：删除了重复的图表

Answer 2

由于图只有边和顶点，因此找到顶点的所有可能的子集并在它们上构造边的所有可能的子集。

Answer 3

如果您使用增强子图，我有一个以下解决方案来迭代所有子图并准备其向量。

// declare the list types
vector<SubGraph*> m_vecSubgraphContainer;
vector<SubGraph*> m_vecBFSOrderedSubgraphs; 

// construct container of subgraph lists in the vector
m_vecSubgraphContainer.push_back(&gInputGraph);

m_vecBFSOrderedSubgraphs.push_back(&gInputGraph);
iterateChildrenGraphs(m_vecBFSOrderedSubgraphs);

// iterating the subgraphs
for(vector<SubGraph*>::iterator itrSubgraph = m_vecSubgraphContainer.begin();
    itrSubgraph != m_vecSubgraphContainer.end();
    ++itrSubgraph)
{
    // for empty graph add dummy node to that graph
    int iNumVertices = num_vertices(**itrSubgraph);
    if(iNumVertices == 0)
    {
        VertexDescriptor vVertex = m_boostGraphWrapper.addVertex(**itrSubgraph, Enum::InvisibleNode);
        // This dummy node will set the size of cluster
        // set height = 80 nd width = 80;
        int iDummyNodeHeight = 80;
        int iDummyNodeWidth = 80;
        m_boostGraphWrapper.setVertexHeight(vVertex,**itrSubgraph, iDummyNodeHeight);
        m_boostGraphWrapper.setVertexWidth(vVertex, **itrSubgraph, iDummyNodeWidth);
    }
}

void CircularLayoutGenerator::iterateChildrenGraphs(vector<SubGraph *> &subgraphQueue)
{
/*
    we have used queue because it will contains reference of subgraphs.
    adding all the subgraphs in queue to iterate one by one in circular way.
*/

// define local queue which will contains the childrens of main graph
vector<SubGraph*> SubgraphSequence;

try
{
    // To iterate input queue which will contain graph reference
    for( vector<SubGraph*>::iterator itrSubgraphQueue = subgraphQueue.begin();
         itrSubgraphQueue != subgraphQueue.end();
         itrSubgraphQueue++)
    {
        // Finding the children upto deep level
        SubGraph::children_iterator itrSubgraph, itrSubgraphEnd;
        for (boost::tie(itrSubgraph, itrSubgraphEnd) = (**itrSubgraphQueue).children();
             itrSubgraph != itrSubgraphEnd;
             ++itrSubgraph)
        {
            // Add children in the global queue container
            m_vecSubgraphContainer.push_back(&(*itrSubgraph));

            // Add children in the local queue conatainer
            SubgraphSequence.push_back(&(*itrSubgraph));
        }
    }
}

// To iterarte the local queue again if ant children is present
if(!SubgraphSequence.empty())
{
    // Recursive call to iterate children
    iterateChildrenGraphs(SubgraphSequence);
}
}