algorithm - 如何从一个图中获取所有子图？

Question

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

如果可能的话，没有外部库。谢谢！

Answer 1

More or less that would be something along these lines:

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

EDIT: Fixed indentation of 'edges.insert' line

EDIT: Removed duplicated graphs

Answer 2

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

Answer 3

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

// 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);
}
}